BZOJ 1901

不稳定的传送门

ZOJ传送门

想+写一上午,调一下午…关键是这题的离散化好恶心啊尼玛,一堆数组绕着绕着就晕了…QAQ

首先扯一个会MLE的解法

对于普通的不带修改的主席树,$root[i]$记载的是从$1$到$i$的所有更改

然后拿树状数组分组一下,让$root[i]$记载从$i-lowbit(i)$到$i$的所有更改,这样建树或修改的时间复杂度$O(n(\log_2n)^2)$

但是呢…这样的空间复杂度有点受不了…大概是$O(n(\log_2n)^2+m(\log_2n)^2)$,毫无疑问MLE 何况ZOJ卡了32M内存尼玛

正确的姿势是初始的建树按照正常的主席树建,然后每个修改再在树状数组套的主席树里改,这样的时间空间复杂度大概$O(n\log_2n+2m(\log_2n)^2)$,可以开得下了

如果开到最大情况大概是$6240000*3\approx 70M$,但实际的数据没出全是修改的情况,我只用$2240000$就够了…


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
program bzoj_1901;
var root,bit:array[0..50000]of longint;
s:array[0..2240000]of record lc,rc,size:longint; end;
q:array[1..10000]of record query:boolean; a,b,k:longint; end;
a,p,b:array[1..60000]of longint;
low:array[1..2,0..16]of longint;
n,m,i,tot,len,l,lb:longint;
c:char;
function lowbit(x:longint):longint;
begin
exit(x and -x);
end;
procedure calc_low(p,t:longint);
begin
while p>0 do
begin
inc(low[t,0]);
low[t,low[t,0]]:=bit[p];
dec(p,lowbit(p));
end;
end;
procedure qsort(l,r:longint);
var i,j,mid,t: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
t:=a[i];
a[i]:=a[j];
a[j]:=t;
t:=p[i];
p[i]:=p[j];
p[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure modify(var t:longint;base,l,r,p,d:longint);
var mid:longint;
begin
inc(tot);
t:=tot;
s[t]:=s[base];
inc(s[t].size,d);
if l=r then exit;
mid:=(l+r)>>1;
if p<=mid then modify(s[t].lc,s[base].lc,l,mid,p,d)
else modify(s[t].rc,s[base].rc,mid+1,r,p,d);
end;
function query(a,b,l,r,k:longint):longint;
var i,t,mid:longint;
begin
if l=r then exit(l);
mid:=(l+r)>>1;
t:=s[s[b].lc].size-s[s[a].lc].size;
for i:=1 to low[1,0] do dec(t,s[s[low[1,i]].lc].size);
for i:=1 to low[2,0] do inc(t,s[s[low[2,i]].lc].size);
if t>=k then
begin
for i:=1 to low[1,0] do low[1,i]:=s[low[1,i]].lc;
for i:=1 to low[2,0] do low[2,i]:=s[low[2,i]].lc;
exit(query(s[a].lc,s[b].lc,l,mid,k));
end else
begin
for i:=1 to low[1,0] do low[1,i]:=s[low[1,i]].rc;
for i:=1 to low[2,0] do low[2,i]:=s[low[2,i]].rc;
exit(query(s[a].rc,s[b].rc,mid+1,r,k-t));
end;
end;
begin
tot:=0;
readln(n,m);
for i:=1 to n do read(a[i]);
readln;
len:=n;
for i:=1 to m do
begin
read(c);
if c='Q' then readln(q[i].a,q[i].b,q[i].k) else
begin
readln(q[i].a,q[i].k);
inc(len);
a[len]:=q[i].k;
q[i].b:=len;
end;
q[i].query:=(c='Q');
end;
for i:=1 to len do p[i]:=i;
qsort(1,len);
l:=0;
for i:=1 to len do
begin
if (i=1)or(a[i]<>a[i-1]) then inc(l);
b[p[i]]:=l;
a[l]:=a[i];
end;
root[0]:=1;
tot:=1;
for i:=1 to n do modify(root[i],root[i-1],1,l,b[i],1);
for i:=1 to m do if q[i].query then
begin
fillchar(low,sizeof(low),0);
calc_low(q[i].a-1,1);
calc_low(q[i].b,2);
writeln(a[query(root[q[i].a-1],root[q[i].b],1,l,q[i].k)]);
end else
begin
lb:=q[i].a;
while lb<=n do
begin
modify(bit[lb],bit[lb],1,l,b[q[i].a],-1);
modify(bit[lb],bit[lb],1,l,b[q[i].b],1);
inc(lb,lowbit(lb));
end;
b[q[i].a]:=b[q[i].b];
end;
end.

因为写裸题又被ZYK大爷D了 QAQ