[CQOI2011]动态逆序对

所谓的动态的逆序对,就是要你按时间的顺序维护一下逆序对数量.我们不妨在原有的二维前提下增加一维time,那么题目就成了一个的三维偏序问题.我们把添加数,删除数都看成操作.然后进行分治处理,然后我们来看下咋算,对于每个操作id,我们都统计下答案,假定我现在要删除一个元素,那我们应该付出多少代价呢?对于这个数而言,假定我们是按值进行的排序,前面序号比它大的答案都得-,后面那些序号比它小的也得-.然后它自身是要删除的.即树状数组也得-.执行完这个以后,这个值对于后面的数一定是没有影响的,因为后面即+了这个值,又-了这个值.然后就没了.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct vv{
    int v,a,b,id,cnt;//v表示+-1.a表示一维,b表示二维,id表示操作种类,cnt表示每种的答案
}w[N<<1];
int pos[N],x;//方便执行删除操作?...?
long long ans[N],sum[N];
int n,m;
int lowbit(int x)   {return x&(-x);}
void add(int pos,int val)
{
    while(pos<=n)
    {
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int res=0;
    while(pos)
    {
        res+=sum[pos];
        pos-=lowbit(pos);
    }
    return res;
}

bool cmp(vv x,vv y)
{
    return x.b<y.b;
}

void cdq(int l,int r)
{
    if(l==r)    return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    sort(w+l,w+mid+1,cmp);
    sort(w+mid+1,w+r+1,cmp);
    //询问区间满足条件数.第二维大于,第三维小于.
    int j=l;
    for(int i=mid+1;i<=r;i++)
    {
        while(j<=mid&&w[j].b<=w[i].b) { add(w[j].a,w[j].v);j++; }
        ans[w[i].id]+=w[i].v*(query(n)-query(w[i].a));
    }
    for(int i=l;i<j;i++)    add(w[i].a,-w[i].v);
    //询问区间满足条件数.第二维小于,第三维大于.
    j=mid;
    for(int i=r;i>=mid+1;i--)
    {
        while(j>=l&&w[j].b>=w[i].b) { add(w[j].a,w[j].v);j--; }
        ans[w[i].id]+=w[i].v*(query(w[i].a-1));
    }
    for(int i=mid;i>j;i--)    add(w[i].a,-w[i].v);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i].b);
        w[i].a=i;
        pos[w[i].b]=i;
        w[i].id=0;
        w[i].v=1;
    }int s=n;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        w[++s].a=pos[x];
        w[s].id=i;
        w[s].v=-1;
        w[s].b=x;
    }//输入即time
    cdq(1,s);
    for(int i=1;i<m;i++)
    {
        ans[i]+=ans[i-1];
    }
    for(int i=0;i<m;i++)    printf("%lld\n",ans[i]);
    return 0;
}