题意:
求单调下降的三元组的个数. 三个元素不一定要连续.
思路:
转化为求二重逆序数:
线段树求出逆序数, 再求逆序数序列的逆序数.
#include <cstdio>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
typedef long long ll;
const int maxn = 1000005;
ll sum[maxn<<2];
typedef struct stru{
int id;
int val;
}stru;
stru x[maxn];
int rev[maxn];
bool cmpid(stru a,stru b)
{
return a.id < b.id;
}
bool cmpval(stru a,stru b)
{
return a.val < b.val;
}
void PushUP(int rt)
{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt)
{
sum[rt] = 0;
if (l == r) return ;
int m = (l + r) >> 1;
build(lson);
build(rson);
}
void update(int p,int l,int r,int rt)
{
if (l == r)
{
sum[rt] ++;
return ;
}//更新的方法是在p位置上加1,于是向上的节点依次加1
int m = (l + r) >> 1;
if (p <= m) update(p , lson);
else update(p , rson);
PushUP(rt);
}
void updaterev(int id,int p,int l,int r,int rt)
{
if (l == r)
{
sum[rt] = rev[id];
//printf("x[%d] %d rev[%d] %I64d\n",id,x[id],id,rev[id]);
return ;
}//更新的方法是在p位置上加1,于是向上的节点依次加1
int m = (l + r) >> 1;
if (p <= m) updaterev(id, p , lson);
else updaterev(id, p , rson);
PushUP(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R)
{
return sum[rt];
}
int m = (l + r) >> 1;
ll ret = 0;
if (L <= m) ret += query(L , R , lson);
if (R > m) ret += query(L , R , rson);
return ret;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&x[i].val);
x[i].id = i;
}
sort(x,x+n,cmpval);
for(int i=0;i<n;i++) x[i].val = i;
sort(x,x+n,cmpid);
build(0 , n-1 , 1);
for (int i = 0; i < n; i ++)
{
///算法:将元素依次插入线段树,每个数的逆序对数为比它大的已经插入的数的个数
rev[i] = query(x[i].val+1 , n-1 , 0 , n-1 , 1);///每个数的逆序数
update(x[i].val , 0 , n-1 , 1);
}
///需要求比x[i]大的数的逆序数之和!!!
ll ans = 0;
build(0, n-1, 1);
for(int i=0;i<n;i++)
{
ans += query(x[i].val+1 , n-1 , 0, n-1 , 1);///已经插入的数的逆序数之和
updaterev(i, x[i].val , 0, n-1 , 1);
}
printf("%I64d\n",ans);
return 0;
}