BZOJ2141排队——分块+二维树状数组-阿南达文事网

BZOJ2141排队——分块+二维树状数组

Description
排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家
乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍
高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足ihj的(i,j)数量。幼儿
园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿
姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。
Input
第一行为一个正整数n，表示小朋友的数量；
第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；
第三行为一个正整数m，表示交换操作的次数；
以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的小朋友。
1≤m≤210^3，1≤n≤2104，1≤hi≤109，ai≠bi，1≤ai,bi≤n。
Output

输出文件共m行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。
Sample Input
【样例输入】

130 150 140

2 3

1 3

Sample Output
1

【样例说明】

未进行任何操作时，(2,3)满足条件；

操作1结束后，序列为130 140 150，不存在满足ihj的(i,j)对；

操作2结束后，序列为150 140 130,(1,2)，(1,3)，(2,3)共3对满足条件的(i,j)

这道题显然是二维树状数组，交换的时候就查询两个点中间的值即可。唉，等等，怎么N这么大呀？开二维树状数组直接MLE飞起，那么怎么做呢？我们考虑分块优化

将小朋友每 ( n ) \sqrt(n) ( n)个分为一块，我们将每一块的下标看做二维树状数组里的 x x x，离散之后的值看做 y y y，那么这样树状数组的内存复杂度就是 n l o g n nlogn nlogn，也就可以了。

但是因为分块，所以操作会稍微复杂一些。如果两个点在同一个块里，那么直接暴力修改即可。

如果不同在同一块里，先把两边端点块里暴力修改，中间的块就可以直接用二维树状数组修改了。

可能会有同学不知道怎么维护，那这里顺带讲一下，会的可以直接跳过：先删去原来的数的贡献，再加上新进的数的贡献。对于 l l l位置，贡献是后面大于等于它的数的个数，而 r r r位置的贡献就是它前面小于等于它的点的个数。最后的答案就是总共的对数（也就是 n ∗ ( n − 1 ) / 2 n*(n-1)/2 n∗(n−1)/2）减去目前的贡献。

#include<bits/stdc++.h>
#define MAXN 20005
using namespace std;
int read(){char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
int n,m,block,cnt,tot,ans,num,bl[MAXN],sum[505][MAXN],pos[MAXN];
struct node{int num,id;bool operator<(const node x)const{return num<x.num;}
}a[MAXN];
int lowbit(int x){return x&-x;}
void add(int p,int x,int ad){for(int i=p;i<=num;i+=lowbit(i))for(int j=x;j<=cnt;j+=lowbit(j))sum[i][j]+=ad;
}
int getsum(int p,int x){int res=0;if(p*x<=0) return 0;for(int i=p;i;i-=lowbit(i))for(int j=x;j;j-=lowbit(j))res+=sum[i][j];return res;
}
int calc(int x,int y,int u,int v){if(x>y) return 0;return getsum(y,v)-getsum(y,u-1)-getsum(x-1,v)+getsum(x-1,u-1); 
}
int main()
{n=read();block=sqrt(n);tot=n*(n-1)/2;for(int i=1;i<=n;i++) a[i].num=read(),a[i].id=i;sort(a+1,a+1+n);a[0].num=-1;for(int i=1;i<=n;i++) if(a[i].num!=a[i-1].num) pos[a[i].id]=++cnt;else pos[a[i].id]=cnt;for(int i=1;i<=n;i++) bl[i]=i/block+1;num=bl[n];for(int i=1;i<=n;i++){ans+=getsum(bl[i],pos[i]);add(bl[i],pos[i],1);}m=read();printf("%d\n",tot-ans);for(int i=1;i<=m;i++){int l=read(),r=read();if(l>r) swap(l,r);if(bl[l]==bl[r]){add(bl[l],pos[l],-1);add(bl[l],pos[r],1);add(bl[r],pos[r],-1);add(bl[r],pos[l],1);for(int j=l+1;j<=r-1;j++){if(pos[l]<=pos[j]) ans--;if(pos[r]<=pos[j]) ans++;if(pos[l]>=pos[j]) ans++;if(pos[r]>=pos[j]) ans--;}if(pos[l]<pos[r]) ans--;if(pos[l]>pos[r]) ans++;swap(pos[l],pos[r]);}else{for(int j=l+1;j<=n;j++){if(bl[j]!=bl[l]) break;if(pos[j]>=pos[l]) ans--;if(pos[j]>=pos[r]) ans++;if(pos[j]<=pos[r]) ans--;if(pos[j]<=pos[l]) ans++;}for(int j=r-1;j;j--){if(bl[j]!=bl[r]) break;if(pos[j]<=pos[r]) ans--;if(pos[j]<=pos[l]) ans++;if(pos[j]>=pos[l]) ans--;if(pos[j]>=pos[r]) ans++;}add(bl[r],pos[r],-1);add(bl[r],pos[l],1);add(bl[l],pos[l],-1);add(bl[l],pos[r],1);ans-=calc(bl[l]+1,bl[r]-1,pos[l],cnt);ans+=calc(bl[l]+1,bl[r]-1,pos[r],cnt);ans-=calc(bl[l]+1,bl[r]-1,1,pos[r]);ans+=calc(bl[l]+1,bl[r]-1,1,pos[l]);if(pos[l]<pos[r]) ans--;if(pos[l]>pos[r]) ans++;swap(pos[l],pos[r]);            }printf("%d\n",tot-ans);}return 0;
}