【块套块/块套树】排队

分块

传送塔：BZOJ2141

题意：说白了就是支持交换顺序的逆序对

思路（这道题思路好特么多啊，此处只提供与分块有关的）：

  • 常规逆序对的解法就是$O(nlogn)$的，所以如果想每次重新求那应该是没什么戏（如果有直接求的请来教我）；
  • 于是只能先求出初始答案，然后计算变化量；
  • 初始答案是不是一个树状数组就没了呀？
  • 然后我特么sb了一下，离散化的时候把大的数离散成小的，这样逆序对就变成了顺序对， （所以下面的讨论基于这个奇特（sb）的离散化）
  • 然后如果$a_i,a_j$交换，那么区间$[1,i-1],[j+1,n]$的元素贡献是不变的，只要求出区间$[i+1,j-1]$的贡献即可。鉴于这道题有相同元素，最好特判一下。然后令区间$[i+1,j-1]$中比$a_i$大，比$a_i$小，比$a_j$大，比$a_j$小的数的个数分别为$b_1,b_2,b_3,b_4$，那么$\delta_{ans}=-b_1+b_2+b_3-b_4$（注意我这公式是经过某种奇特（sb）离散化的）。
  • 如果直接使用树状数组维护的话，我可能不会，因为要同时维护区间和权值；
  • 如果用带修主席树，我可能也不会；
  • 如果用树套树，可能是挺好写的（如果可以的话应该是一层维护区间，一层维护权值），然而我并没有写过；
  • 如果用分块，那就美滋滋了：
    • 先撕烤块套树的做法：把原序列的区间分成若干块，每块用一个树状数组维护权值，整块的点就用树状数组，零散的点就直接暴力数，这样单次修改应该是$O(logn)$的，单次查询应该是$O(\sqrt n\times logn)$的，似乎已经可以跑卡过去了；
    • 再撕烤以下刚才做法的不足：似乎修改很快但查询很慢，因为 外层分块后查询必定是要查询$\sqrt n$块的，而修改只要1块 。于是考虑换一个数据结构，如果用普通分块维护区间内比一个数小的数的个数，那么似乎单次修改是$O(1)$的，单次查询是$O(n)$的，药丸啊；但如果用用分块维护前缀区间中的个数呢？那么单次修改和查询是$O(\sqrt n)$的。然后就更稳辣！

注意：

  • 一定要认真看题，此题有重复元素。我就是因为看了某题解然后看题时太瞎导致浪费了1h。
  • 似乎大于一个数的元素可以由特殊方法得到，不用单独维护哦（请独立思考或看代码）

附上块套块实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 30010
#define BASE 150
#define getblock(x) (((x)-1)/BASE+1)
int n,m,ans,x,y,a[N],b[N],bit[N],pre[150][N],block[150][150];
void add(int x){for (int i=x;i<=n;i+=i&(-i)) bit[i]++;}
void change(int B,int k,int x){
	int Bk=getblock(k);
	for (int i=k;i<=Bk*BASE;i++) pre[B][i]+=x;
	for (int i=Bk;i<=getblock(n);i++) block[B][i]+=x;
}
int ask(int l,int r,int k){
	if (l>r) return 0;
	int Bl=getblock(l),Br=getblock(r),sum=0,Bk=getblock(k);
	if (Bl==Br){
		for (int i=l;i<=r;i++){
			if (a[i]<k) sum++; if (a[i]<=k) sum++;
		}
	}
	else{
		for (int i=l;i<=Bl*BASE;i++){
			if (a[i]<k) sum++; if (a[i]<=k) sum++;
		}
		for (int i=(Br-1)*BASE+1;i<=r;i++){
			if (a[i]<k) sum++; if (a[i]<=k) sum++;
		}
		Bk=getblock(k-1);
		for (int i=Bl+1;i<Br;i++) sum+=block[i][Bk-1]+pre[i][k-1];
		Bk=getblock(k);
		for (int i=Bl+1;i<Br;i++) sum+=block[i][Bk-1]+pre[i][k];
	}
	return sum-(r-l+1);
}
	
int query(int x){
	int sum=0;
	for (int i=x;i;i-=i&(-i)) sum+=bit[i];
	return sum;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){scanf("%d",&a[i]); b[i]=a[i];}
	sort(b+1,b+n+1);
	for (int i=1;i<=n;i++) a[i]=n-(lower_bound(b+1,b+n+1,a[i])-b)+1;
	for (int i=1;i<=n;i++){ans+=query(a[i]-1); add(a[i]);}
	printf("%d\n",ans);
	for (int i=1;i<=n;i++){
		int B=getblock(i);
		change(B,a[i],1);
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y); if (x>y) swap(x,y);
		if (a[x]==a[y]){printf("%d\n",ans); continue;}
		int Bx=getblock(x),By=getblock(y);
		ans+=ask(x+1,y-1,a[x]);
		ans-=ask(x+1,y-1,a[y]);
		if (a[x]>a[y]) ans++; else ans--;
		change(Bx,a[x],-1); change(Bx,a[y],1);
		change(By,a[x],1); change(By,a[y],-1);
		printf("%d\n",ans); swap(a[x],a[y]);
	}
	
	return 0;
}