BZOJ 3289

传送门

莫队尼玛26s才过

因为这题没给数据范围,树状数组不知道开多大,所以先离散化一下 P党程序里写了俩快排真长…TAT

首先还是分块+排序,节省转移时的消耗,然后转移时要注意这些:

  • 修改区间左端点就查询比左端点的数小的,右端点就查询比右端点的数大的(逆序对判断条件:$i<j且a[i]>a[j]$)

  • 当前区间向询问的区间转移时要注意for循环的顺序,一定是当前区间端点向询问区间端点逐个转移,否则有的情况会考虑不到(例如样例这样)

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
140
141
142
143
program bzoj_3289;
type qu=record l,r,id,ans:longint; end;
var bit,pos,bl,a,s:array[1..50000]of longint;
ask:array[1..50000]of qu;
n,q,i,block,tot,cnt:longint;
function c(x:longint):longint;
begin
exit(x and -x);
end;
function sml(a,b:qu):boolean;
begin
if bl[a.l]=bl[b.l] then exit(a.r<b.r);
exit(a.l<b.l);
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:qu;
begin
i:=l;
j:=r;
mid:=ask[(l+r)>>1];
repeat
while sml(ask[i],mid) do inc(i);
while sml(mid,ask[j]) do dec(j);
if i<=j then
begin
p:=ask[i];
ask[i]:=ask[j];
ask[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 qsort_(l,r:longint);
var i,j,mid,p:longint;
begin
i:=l;
j:=r;
mid:=a[(l+r)>>1];
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
p:=pos[i];
pos[i]:=pos[j];
pos[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;
function query(p:longint):longint;
begin
query:=0;
while p>0 do
begin
inc(query,bit[p]);
dec(p,c(p));
end;
end;
procedure modify(p,d:longint);
begin
while p<=cnt do
begin
inc(bit[p],d);
inc(p,c(p));
end;
end;
procedure solve;
var i,j,l,r:longint;
begin
fillchar(bit,sizeof(bit),0);
l:=1;
r:=0;
tot:=0;
for i:=1 to q do
begin
for j:=l to ask[i].l-1 do
begin
dec(tot,query(s[j]-1));
modify(s[j],-1);
end;
for j:=l-1 downto ask[i].l do
begin
inc(tot,query(s[j]-1));
modify(s[j],1);
end;
for j:=r+1 to ask[i].r do
begin
inc(tot,query(cnt)-query(s[j]));
modify(s[j],1);
end;
for j:=r downto ask[i].r+1 do
begin
dec(tot,query(cnt)-query(s[j]));
modify(s[j],-1);
end;
l:=ask[i].l;
r:=ask[i].r;
ask[i].ans:=tot;
end;
end;
begin
readln(n);
block:=trunc(sqrt(n));
for i:=1 to n do bl[i]:=(i-1) div block+1;
for i:=1 to n do read(a[i]);
for i:=1 to n do pos[i]:=i;
qsort_(1,n);
cnt:=0;
for i:=1 to n do
begin
if (i=1)or(a[i]<>a[i-1]) then inc(cnt);
s[pos[i]]:=cnt;
end;
readln(q);
for i:=1 to q do with ask[i] do
begin
readln(l,r);
id:=i;
end;
qsort(1,q);
for i:=1 to q do pos[ask[i].id]:=i;
solve;
for i:=1 to q do writeln(ask[pos[i]].ans);
end.