[CF 61E]Enermy is weak[线段树求二重逆序数]

题意:

求单调下降的三元组的个数. 三个元素不一定要连续.

思路:

转化为求二重逆序数:

线段树求出逆序数, 再求逆序数序列的逆序数.

#include 
#include 
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