【块套块/块套树】排队

传送塔: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;
}