首页 > 代码库 > 【分块】bzoj3295 [Cqoi2011]动态逆序对
【分块】bzoj3295 [Cqoi2011]动态逆序对
考虑每次删除pos位置一个数x后，所造成的的影响就是，逆序对的个数少了在1~pos-1中大于x的数的个数加上pos+1~n中小于x的数的个数。
那么我们需要的操作就只有查询区间内比某数大（小）的个数。
↑，分块经典操作，每个块里维护一个有序表。
由于有删除，最好每个块用一个vector。
对于原数列怎么办呢？只需要弄一个vis数组，vis[i]表示i位置的数已经删除即可。（要找到v在原数列中的位置的话，在其所在块暴力即可。）
查询时对整块二分，对要删的元素所在块分成两段暴力。
O(n*sqrt(n)*log2(sqrt(n)))
【觉得我已经丧心病狂了，bzoj的树套树题只会用分块水怎么办啊，一旦不是总时限不就T了吗……QAQ】
P.S.请用long long。
1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 bool vis[100001]; 7 int n,m,a[100001],sum,num[100001],sz,l[400],r[400],v; 8 long long ans; 9 vector<int>b[400];10 vector<int>::iterator it;11 int Res,Num;char C,CH[12];12 inline int G()13 {14 Res=0;C=‘*‘; 15 while(C<‘0‘||C>‘9‘)C=getchar();16 while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}17 return Res;18 }19 inline void P(long long x)20 {21 Num=0;if(!x){putchar(‘0‘);puts("");return;}22 while(x>0)CH[++Num]=x%10,x/=10;23 while(Num)putchar(CH[Num--]+48);24 puts("");25 }26 void makeblock()27 {28 sz=sqrt((double)n*log2(n));29 for(sum=1;sum*sz<n;sum++)30 {31 l[sum]=(sum-1)*sz+1;32 r[sum]=sum*sz;33 for(int i=l[sum];i<=r[sum];i++) num[i]=sum,b[sum].push_back(a[i]);34 sort(b[sum].begin(),b[sum].end());35 }36 l[sum]=sz*(sum-1)+1; r[sum]=n;37 for(int i=l[sum];i<=r[sum];i++) {num[i]=sum; b[sum].push_back(a[i]);}38 sort(b[sum].begin(),b[sum].end());39 }40 int D[100001];inline int lowbit(const int &x){return x&(-x);}41 inline int getsum(int x){int res=0;while(x>0){res+=D[x];x-=lowbit(x);}return res;}42 inline void add(int x,const int &d){while(x<=n){D[x]+=d;x+=lowbit(x);}}43 void Get_First_Ans()44 {for(int i=1;i<=n;i++){add(a[i],1);ans+=(long long)i-getsum(a[i]);}}45 int Get_Pos(const int &v,const int &L,const int &R)46 {for(int i=L;i<=R;i++) if(!vis[i] && a[i]==v) return i;}47 void update()48 {49 for(int i=1;i<=sum;i++)50 {51 it=lower_bound(b[i].begin(),b[i].end(),v);52 if(*it==v)53 {54 int p=Get_Pos(v,l[i],r[i]); vis[p]=true;55 for(int j=1;j<i;j++) ans-=(long long)(b[j].end()-upper_bound(b[j].begin(),b[j].end(),v));56 for(int j=l[i];j<p;j++) if(!vis[j] && a[j]>v) ans--;57 for(int j=i+1;j<=sum;j++) ans-=(long long)(lower_bound(b[j].begin(),b[j].end(),v)-b[j].begin());58 for(int j=p+1;j<=r[i];j++) if(!vis[j] && a[j]<v) ans--;59 b[i].erase(it);60 break;61 }62 }63 }64 int main()65 {66 n=G();m=G();67 for(int i=1;i<=n;i++) a[i]=G();68 Get_First_Ans();69 makeblock();70 for(int i=1;i<=m;i++)71 {72 v=G(); P(ans);73 update();74 }75 return 0;76 }
【分块】bzoj3295 [Cqoi2011]动态逆序对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。