Bzoj 3295: [Cqoi2011]动态逆序对 分块,树状数组,逆序对

3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 2886  Solved: 924
[Submit][Status][Discuss]

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

Source

 题解：

分块＋树状数组＋逆序对

好像正解是CDQ分治 QAQ

然而不会。。。

胡搞了一个分块，记录一下每个数出现的位置。然后，考虑到每次删除，对答案有影响的只有当前这个数前头比它大的个数，和后头比他小的个数。所以就分块统计有多少个。但是，如何删除呢？

我是在更新完答案后，把当前的这个数放成－1。然后对于统计这个数前头比它大的数的个数没有影响(因为－1比任何数都小，不会被统计上)。但对于后头比它小的个数就不一样了。但，－1比任何数都小，所以它一定在每个排好序的块的最前端的一段。我们只需要二分去找第一个不是－1的位置，然后就可以统计了。（各种二分。。。）

至于速度嘛，rank榜上倒数。。。QAQ赶快去学CDQ分治。。。

 #include<bits/stdc++.h>
 using namespace std;
 #define MAXN 100010
 #define LL long long
 int pos[MAXN],BIT[MAXN],a[MAXN],b[MAXN],wz[MAXN],block,n;
 LL ans;
 int read()
 {
     int s=,fh=;char ch=getchar();
     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
     return s*fh;
 }
 int Lowbit(int o){return o&(-o);}
 void Update(int o,int o1)
 {
     while(o<=n)
     {
         BIT[o]+=o1;
         o+=Lowbit(o);
     }
 }
 int Sum(int o)
 {
     int sum=;
     while(o>)
     {
         sum+=BIT[o];
         o-=Lowbit(o);
     }
     return sum;
 }
 void cl(int k)
 {
     int l=(k-)*block+,r=min(k*block,n),i;
     for(i=l;i<=r;i++)b[i]=a[i];
     sort(b+l,b+r+);
 }
 int ef(int k,int k1)//在第k块中寻找大于k1的第一个位置.
 {
     int l=(k-)*block+,r=min(k*block,n),ans1;
     ans1=-;
     while(l<=r)
     {
         int mid=(l+r)/;
         if(b[mid]>k1){ans1=mid;r=mid-;}
         else l=mid+;
     }
     return ans1;
 }
 int ef1(int k,int k1)
 {
     int l=(k-)*block+,r=min(k*block,n),ans1;
     ans1=-;
     while(l<=r)
     {
         int mid=(l+r)/;
         if(b[mid]<k1){ans1=mid;l=mid+;}
         else r=mid-;
     }
     return ans1;
 }
 void calc1(int l,int r,int D)
 {
     if(l>r)return;
     int L=pos[l],R=pos[r],i,pd;
     if(L==R)
     {
         for(i=l;i<=r;i++)if(a[i]>D&&a[i]!=-)ans--;
         return;
     }
     for(i=l;i<=L*block;i++)if(a[i]>D&&a[i]!=-)ans--;
     for(i=L+;i<=R-;i++)
     {
         pd=ef(i,D);
         if(pd!=-)ans-=(LL)(min(i*block,n)-pd+);
     }
     //ans-=(ef(i,D)-ef(i,0)+1);
     for(i=(R-)*block+;i<=r;i++)if(a[i]>D&&a[i]!=-)ans--;
 }
 void calc2(int l,int r,int D)
 {
     if(l>r)return;
     int L=pos[l],R=pos[r],i,pd,pd1;
     if(L==R)
     {
         for(i=l;i<=r;i++)if(a[i]<D&&a[i]!=-)ans--;
         return;
     }
     for(i=l;i<=L*block;i++)if(a[i]<D&&a[i]!=-)ans--;
     for(i=L+;i<=R-;i++)
     {
         //ans-=(ef1(i,D)-ef(i,0)+1);
         pd=ef1(i,D);
         if(b[pd]!=-)
         {
             pd1=ef(i,);
             if(pd!=-)
             {
                 if(pd1==-)pd1=;
                 ans-=(LL)(pd-pd1+);
             }
         }
     }
     for(i=(R-)*block+;i<=r;i++)if(a[i]<D&&a[i]!=-)ans--;
 }
 int main()
 {
     freopen("inverse.in","r",stdin);
     freopen("inverse.out","w",stdout);
     int m,i,M,del;
     n=read();m=read();
     for(i=;i<=n;i++)a[i]=read(),wz[a[i]]=i;
     block=(int)sqrt(n);
     for(i=;i<=n;i++)pos[i]=(int)(i-)/block+;
     if(n%block==)M=n/block;
     else M=n/block+;
     memset(BIT,,sizeof(BIT));ans=;
     for(i=n;i>=;i--)
     {
         ans+=Sum(a[i]-);
         Update(a[i],);
     }
     for(i=;i<=M;i++)cl(i);
     for(i=;i<=m;i++)
     {
         del=read();
         printf("%lld\n",ans);
         calc1(,wz[del]-,del);//去寻找 从位置1到要删除的数前一个位置 中有多少个数大于要删除的数,并把个数减去.
         calc2(wz[del]+,n,del);//去寻找 从要删除的数后一个位置到位置n 中有多少个数小于要删除的数,并把个数减去.
         a[wz[del]]=-;
         cl(pos[wz[del]]);
         //printf("%d\n",ans);
     }
     fclose(stdin);
     fclose(stdout);
     return ;
 }