首页 > 代码库 > BZOJ 3295 【Cqoi2011】 动态逆序对
BZOJ 3295 【Cqoi2011】 动态逆序对
Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
HINT
N<=100000 M<=50000
这道题做法很多……但是我来做这道题只是为了练CDQ分治的……
首先，我们可以考虑当删除一个数之后逆序对数减少了多少。不难发现，减少的逆序对数就是 这个数 前面比它小的数的个数 加上 后面比它大的数的个数。
那么，如果我们强行把最后数列中剩下的数也删掉，那么我们就得到了n个操作，用(xi,yi,zi)表示操作i是在时刻z把y位置上值为x的数给删掉。
于是，对于一个操作i，这个操作减少的逆序对数为 xj<xi,yj<yi,zj>zi 以及 xj>xi,yj>yi,zj>zi 的j的个数。
其实这就是一个三维偏序。对于两个式子分别在CDQ分治的时候扫一遍即可。 大概的思路就是排序一维，分治时归并一维，剩下一维再用树状数组来维护。
下面贴代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 7 #define maxn 100010 8 9 using namespace std;10 typedef long long llg;11 12 struct data{13 int x,y,b;14 bool operator < (const data &h)const{return x>h.x;}15 }s[maxn],ss[maxn];16 int c[maxn],n,m,a[maxn],ans[maxn];17 bool w[maxn]; llg ana;18 19 int getint(){20 int w=0;bool q=0;21 char c=getchar();22 while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar();23 if(c==‘-‘) c=getchar(),q=1;24 while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar();25 return q?-w:w;26 }27 28 void add(int x,int y){while(x<=n) c[x]+=y,x+=x&(-x);}29 int sum(int x){30 int t=0;31 while(x) t+=c[x],x-=x&(-x);32 return t;33 }34 35 void solve(int l,int r){36 if(l>=r) return;37 int mid=l+r>>1,now=l,kk=l-1,k1=l,k2=mid+1;38 solve(l,mid); solve(mid+1,r);39 for(int i=mid+1;i<=r;i++){40 while(s[now].y<s[i].y && now<=mid) add(s[now].b,1),now++;41 ans[s[i].b]+=sum(n)-sum(s[i].b);42 }43 for(int i=l;i<now;i++) add(s[i].b,-1);44 now=r;45 for(int i=mid;i>=l;i--){46 while(s[now].y>s[i].y && now>mid) add(s[now].b,1),now--;47 ans[s[i].b]+=sum(n)-sum(s[i].b);48 }49 for(int i=now+1;i<=r;i++) add(s[i].b,-1);50 while(k1<=mid && k2<=r)51 if(s[k1].y<s[k2].y) ss[++kk]=s[k1++];52 else ss[++kk]=s[k2++];53 while(k1<=mid) ss[++kk]=s[k1++];54 while(k2<=r) ss[++kk]=s[k2++];55 for(int i=l;i<=r;i++) s[i]=ss[i];56 }57 58 int main(){59 File("a");60 n=getint(); m=getint();61 for(int i=1;i<=n;i++) a[getint()]=i;62 for(int i=1;i<=m;i++){63 s[i].x=getint(); s[i].b=i;64 s[i].y=a[s[i].x]; w[s[i].x]=1;65 }66 for(int i=1,t=m;i<=n;i++)67 if(!w[i]){68 s[++t].x=i; s[t].b=t;69 s[t].y=a[s[t].x];70 }71 sort(s+1,s+n+1); solve(1,n);72 for(int i=1;i<=n;i++) ana+=ans[i];73 for(int i=1;i<=m;i++){74 printf("%lld\n",ana);75 ana-=ans[i];76 }77 }
BZOJ 3295 【Cqoi2011】 动态逆序对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。