BZOJ - 3295 动态逆序对 (树状数组套treap)

题目链接

思路和bzoj2141差不多，不过这道题的数据更强一些，线段树套treapT了，树状数组套treap卡过~~

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=1e5+,inf=0x3f3f3f3f;

 int rt[N],n,m,n2,ch[N*][],val[N*],siz[N*],rd[N*],tot,a[N],b[N];

 ll ans;

 void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}

 int newnode(int x) {int u=++tot; siz[u]=,val[u]=x,rd[u]=rand(),ch[u][]=ch[u][]=; return u;}

 void rot(int& u,int f) {

     int v=ch[u][f];

     ch[u][f]=ch[v][f^],ch[v][f^]=u;

     pu(u),pu(v),u=v;

 }

 void ins(int& u,int x) {

     if(!u) {u=newnode(x); return;}

     int f=x>val[u];

     ins(ch[u][f],x);

     if(rd[ch[u][f]]>rd[u])rot(u,f);

     if(u)pu(u);

 }

 void del(int& u,int x) {

     if(val[u]==x) {

         if(!ch[u][]||!ch[u][])u=ch[u][]|ch[u][];

         else {

             int f=rd[ch[u][]]>rd[ch[u][]];

             rot(u,f),del(ch[u][f^],x);

         }

     } else del(ch[u][x>val[u]],x);

     if(u)pu(u);

 }

 int ask(int u,int x) {

     int ret=;

     for(; u; u=ch[u][x>=val[u]])if(x>=val[u])ret+=siz[ch[u][]]+;

     return ret;

 }

 void add(int u,int x,int dx) {for(; u<=n; u+=u&-u)dx==?ins(rt[u],x):del(rt[u],x);}

 int get1(int u,int x) {int ret=; for(; u; u-=u&-u)ret+=ask(rt[u],x-); return ret;}

 int get2(int u,int x) {int ret=; for(; u; u-=u&-u)ret+=siz[rt[u]]-ask(rt[u],x); return ret;}

 int main() {

     srand(time());

     scanf("%d%d",&n,&m),n2=n;

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)b[a[i]]=i;

     for(int i=n; i>=; --i)ans+=get1(n,a[i]),add(i,a[i],);

     while(m--) {

         printf("%lld\n",ans);

         int x;

         scanf("%d",&x);

         int t1=get2(b[x]-,x),t2=get1(n,x)-get1(b[x],x);

         ans-=t1+t2;

         add(b[x],x,-);

         n2--;

     }

     return ;

 }