【BZOJ 3295】 [Cqoi2011]动态逆序对

3295: [Cqoi2011]动态逆序对Time Limit:10 SecMemory Limit:128 MBSubmit:1373Solved:465[Submit][Status][Discuss]Description

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

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

Sample Input

5 4153425142

Sample Output

5221样例解释(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

CDQ分治+树状数组

orz PoPoQQQ（解题方法和代码都是copy他的。。）

首先我们可以用树状数组求出初始解；

并求出cnt[i]，表示i所在的逆序对数：1.在他之前插入了比他大的 2.在他之后插入了比他小的

（注意：为了避免每次都清空树状数组，我们可以用一个时间戳）

但是删除一个数x之后，不能单纯的只减去cnt[x]，因为如果逆序对是(x,y)，y在之前被删除了，那么之前就已经减过这个逆序对了，这次再减就导致多减了一次。

因此每次在减掉cnt[x]的时候还要加上f[i]：

表示当前要删的数字与之前已经删过的数字构成了几对逆序对。

（这是一个三维的问题了：时间，位置，权值）

我们用CDQ分治来求f[i]。

q[i].x,q[i].y,q[i].pos分别表示删除的数字，删除数字所在的位置，被删除的时间。

按照q[i].y升序排序，递归处理完(l,mid)之后，计算(l,mid)对(mid+1,r)的影响（此时只剩下权值一维）：

还是分两种情况：1.在他之前比他大的 2.在他之后比他小的

然后就可以递归解决(mid+1,r)了。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>#include <cmath>#define LL long long#define M 100005using namespace std;LL ans=0,f[M],cnt[M];int t[M],n,m,ti[M],now=0,a[M],b[M];struct query{int x,y,pos;}q[M],nq[M];int lowbit(int x){return x&(-x);}int Getsum(int x,int k){int ans=0;for (int i=x;i&&i<=n;i+=lowbit(i)*k)if (ti[i]==now)ans+=t[i];return ans;}void Push_up(int x,int k){for (int i=x;i&&i<=n;i+=lowbit(i)*k){if (ti[i]!=now)ti[i]=now,t[i]=0;t[i]+=1;}}bool cmp(query a,query b){return a.y<b.y;}void CDQ(int l,int r){if (l==r){printf("%lld\n",ans);ans=ans-cnt[q[l].y]+f[l];return;}int mid=(l+r)>>1;int l1=l,l2=mid+1;for (int i=l;i<=r;i++)if (q[i].pos<=mid)nq[l1++]=q[i];elsenq[l2++]=q[i];memcpy(q+l,nq+l,sizeof(q[0])*(r-l+1));CDQ(l,mid);now++;int j=l;for (int i=mid+1;i<=r;i++){for (;j<=mid&&q[j].y<q[i].y;j++)Push_up(q[j].x,-1);f[q[i].pos]+=Getsum(q[i].x,1);}now++;j=mid;for (int i=r;i>mid;i–){for (;j>=l&&q[j].y>q[i].y;j–)Push_up(q[j].x,1);f[q[i].pos]+=Getsum(q[i].x,-1);}CDQ(mid+1,r);l1=l,l2=mid+1;for (int i=l;i<=r;i++)if ((q[l1].y<q[l2].y||l2>r)&&l1<=mid)nq[i]=q[l1++];else nq[i]=q[l2++];memcpy(q+l,nq+l,sizeof(q[0])*(r-l+1));}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]=i;for (int i=1;i<=n;i++){cnt[i]=Getsum(a[i],1);Push_up(a[i],-1);ans+=cnt[i];}now++;for (int i=n;i;i–){cnt[i]+=Getsum(a[i],-1);Push_up(a[i],1);}for (int i=1;i<=m;i++){scanf("%d",&q[i].x);q[i].y=b[q[i].x];q[i].pos=i;}sort(q+1,q+1+m,cmp);CDQ(1,m);return 0;}

勇敢的冷静的理智的去接受失败，有时不但是必要的，而且是很有必要的。