BZOJ 2141

传送门

正常的解法是树套树然而我不会 所以写了个分块

假设现在要交换$l$与$r$,使答案发生变化的只会出现在$l$之后$r$之前也就是$l,r$之间,只需要查询区间中的变化就行了

对于$(l,r)$中的一个$i$,若$h_i>h_l$或$h_i<h_r$,交换后会分别产生一对新的逆序对,逆序对减少时同理

这样就得到了暴力的方法,每次循环这个区间,判断$4$种情况即可

把序列分块,每块建个树状数组,对于每次修改,区间两边不满一块的暴力,整块的直接在树状数组里查

这题有元素重复的情况,离散化的时候需要注意一下

有空了把树套树的坑填了


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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
program bzoj_2141;
type rec=record x,id:longint; end;
arr=array[1..20000]of longint;
var bit:array[0..150]of arr;
ll,rr:array[1..150]of longint;
t:array[1..20000]of rec;
a:array[1..20000]of longint;
n,m,i,x,y,size,ans,tot,block:longint;
procedure swap(var a,b:longint);
var p:longint;
begin
p:=a;
a:=b;
b:=p;
end;
function c(x:longint):longint;
begin
exit(x and -x);
end;
procedure modify(var b:arr;p,d:longint);
begin
while p<=tot do
begin
inc(b[p],d);
inc(p,c(p));
end;
end;
function query(var b:arr;p:longint):longint;
begin
query:=0;
while p>0 do
begin
inc(query,b[p]);
dec(p,c(p));
end;
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:rec;
begin
i:=l;
j:=r;
mid:=t[(l+r)>>1];
repeat
while t[i].x<mid.x do inc(i);
while t[j].x>mid.x do dec(j);
if i<=j then
begin
p:=t[i];
t[i]:=t[j];
t[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure update(t,l,r:longint);
begin
dec(ans,ord(t<l)+ord(t>r));
inc(ans,ord(t>l)+ord(t<r));
end;
procedure solve;
var l,r,i:longint;
begin
if x>y then swap(x,y);
l:=(x-1) div size+1;
r:=(y-1) div size+1;
if l<>r then
begin
for i:=x+1 to rr[l] do update(a[i],a[x],a[y]);
for i:=ll[r] to y-1 do update(a[i],a[x],a[y]);
for i:=l+1 to r-1 do
begin
dec(ans,query(bit[i],a[x]-1));
inc(ans,query(bit[i],a[y]-1));
inc(ans,query(bit[i],tot)-query(bit[i],a[x]));
dec(ans,query(bit[i],tot)-query(bit[i],a[y]));
end;
end else for i:=x+1 to y-1 do update(a[i],a[x],a[y]);
if a[x]<a[y] then inc(ans) else if a[x]>a[y] then dec(ans);
writeln(ans);
modify(bit[l],a[x],-1);
modify(bit[l],a[y],1);
modify(bit[r],a[y],-1);
modify(bit[r],a[x],1);
swap(a[x],a[y]);
end;
begin
readln(n);
for i:=1 to n do
begin
read(t[i].x);
t[i].id:=i;
end;
qsort(1,n);
tot:=0;
for i:=1 to n do
begin
if (i=1)or(t[i].x<>t[i-1].x) then inc(tot);
a[t[i].id]:=tot;
end;
ans:=0;
size:=trunc(sqrt(n));
block:=n div size;
for i:=1 to n do
begin
inc(ans,query(bit[0],tot)-query(bit[0],a[i]));
modify(bit[0],a[i],1);
modify(bit[(i-1)div size+1],a[i],1);
end;
writeln(ans);
for i:=1 to block do
begin
ll[i]:=(i-1)*size+1;
rr[i]:=i*size;
end;
if n mod size<>0 then
begin
inc(block);
ll[block]:=rr[block-1]+1;
rr[block]:=n;
end;
readln(m);
for i:=1 to m do
begin
readln(x,y);
solve;
end;
end.