【BZOJ3295】[Cqoi2011]动态逆序对

Description

对于序列A，它的逆序对数定义为满足

i<

j，且A

_i>A

_j的数对(

i,

j)的个数。给1到

n的一个排列，按照某种顺序依次删除

m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数

n和

m，即初始元素的个数和删除的元素个数。以下

n行每行包含一个1到

n之间的正整数，即初始排列。以下

m行每行一个正整数，依次为每次删除的元素。

Output

输出包含

m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4

1

5

3

4

2

5

1

4

2

Sample Output

5

2

2

1

样例解释

(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

题解：cdq分治裸题。

我们将区间按下标分成两半，在每一半内按删除时间排序，对于每个数，我们希望找到所有删除时间大于等于它的数与他形成的逆序对，用树状数组搞定即可，注意：既要找i<j且vi>vj的也要找j>i且vj<vi的。并且当删除时间相同时（即都没被删除时）不要计算重复。

给这题用树套树过的大佬跪了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;int n,m,now;const int maxn=100010;struct node{	int tim,pos,v,ans;}p[maxn];int s[maxn],vis[maxn],q[maxn];ll ans[maxn];bool cmpp(node a,node b){	return a.pos
          
           b.pos):(a.tim>b.tim);}void updata(int x){	for(int i=x;i<=n;i+=i&-i)	{		if(vis[i]
           
            '9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f;}void solve(int l,int r){ if(l==r) return ; int mid=l+r>>1,h1=l,h2=mid+1; sort(p+l,p+mid+1,cmpt),sort(p+mid+1,p+r+1,cmpt); now++; while(h1<=mid||h2<=r) { if(h2<=r&&(h1>mid||p[h2].tim>=p[h1].tim)) updata(p[h2].v),h2++; else p[h1].ans+=query(p[h1].v-1),h1++; } now++,h1=l,h2=mid+1; while(h1<=mid||h2<=r) { if(h2<=r&&(h1>mid||p[h2].tim>=p[h1].tim)) p[h2].ans+=h1-l-query(p[h2].v),h2++; else updata(p[h1].v),h1++; } sort(p+l,p+mid+1,cmpp),sort(p+mid+1,p+r+1,cmpp); solve(l,mid),solve(mid+1,r);}int main(){ n=rd(),m=rd(); int i,a; for(i=1;i<=n;i++) p[i].pos=i,p[i].v=rd(),p[i].tim=m+1,q[p[i].v]=i; for(i=1;i<=m;i++) a=rd(),p[q[a]].tim=i; solve(1,n); sort(p+1,p+n+1,cmpp); for(i=1;i<=n;i++) ans[p[i].tim]+=p[i].ans; for(i=m;i>=1;i--) ans[i]+=ans[i+1]; for(i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0;}