首页 > 代码库 > 【BZOJ3295】【CQOI2011】动态逆序对

【BZOJ3295】【CQOI2011】动态逆序对

2024-09-05 02:24:29   217人阅读

cdq分治经典例题，然而智商掉线傻逼错误坑了两天

原题：

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

N<=100000 M<=50000

 

此题修改和询问绑定完全离线，可以直接倒序变成插入，然后就是三维数星星辣(? ?????)?

x为下标，y为值，z为时间轴，x排序，z_cdq分治，y树状数组

不用搞两次cdq分治，每次按x递增查找比y大的，然后按x递减查找比y小的

注意当x递增的时候查找的是比y大的，因为虽然x是递增，但是修改上去的都是比当前x小的

然后我先计算贡献再把小于mid的放左边大于mid的放右边然后进入下一层的做法是没有问题的

问题在于我傻逼题中删除的是值我删的是下标技术分享

注意longlong

代码：

技术分享 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<vector>
 8 using namespace std;
 9 #define ll long long
10 int read(){int z=0,mark=1;  char ch=getchar();
11     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mark=-1;  ch=getchar();}
12     while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘;  ch=getchar();}
13     return z*mark;
14 }
15 struct cdd{int x,y,z;}a[110000],q[110000];
16 int n,m,b[110000];  int N;
17 bool usd[110000];  int tt=0;
18 ll e[110000];  int lbt[110000];
19 ll ans[110000];
20 int re[110000];
21 void gtlbt(){for(int i=1;i<=n;++i)  lbt[i]=i&-i;}
22 void mdf(int x,int y){while(x<=n)  e[x]+=y,x+=lbt[x];}
23 ll qr(int x){ll bwl=0;  while(x)  bwl+=e[x],x-=lbt[x];  return bwl;}
24 void cdq(int l,int r){
25     if(l==r)  return ;
26     int md=(l+r)>>1;
27     for(int i=l;i<=r;++i){
28         if(a[i].z>md)  mdf(a[i].y,1);
29         else  ans[a[i].z]+=qr(n)-qr(a[i].y);
30     }
31     for(int i=l;i<=r;++i)if(a[i].z>md)  mdf(a[i].y,-1);
32     for(int i=r;i>=l;--i){
33         if(a[i].z>md)  mdf(a[i].y,1);
34         else  ans[a[i].z]+=qr(a[i].y);
35     }
36     for(int i=l;i<=r;++i)if(a[i].z>md)  mdf(a[i].y,-1);
37     int t1=l,t2=md+1;
38     for(int i=l;i<=r;++i)  q[(a[i].z<=md?t1:t2)++]=a[i];
39     for(int i=l;i<=r;++i)  a[i]=q[i];
40     cdq(l,md),cdq(md+1,r);
41 }
42 bool cmp(cdd x,cdd y){return x.x<y.x;}
43 int main(){//freopen("ddd.in","r",stdin);
44     memset(usd,0,sizeof(usd));
45     cin>>n>>m;  N=n-m;
46     gtlbt();
47     for(int i=1;i<=n;++i)  b[i]=read(),re[b[i]]=i;
48     for(int i=1;i<=m;++i)  a[++tt].y=read(),a[i].x=re[a[i].y],a[i].z=i,usd[a[i].x]=true;
49     for(int i=1;i<=n;++i)if(!usd[i])  a[++tt].x=i,a[tt].y=b[i],a[tt].z=tt;
50     sort(a+1,a+n+1,cmp);
51     cdq(1,n);
52     for(int i=n;i>1;--i)  ans[i-1]+=ans[i];
53     for(int i=1;i<=m;++i)  printf("%I64d\n",ans[i]);
54     return 0;
55 }
View Code

 

【BZOJ3295】【CQOI2011】动态逆序对


联系
我们