BZOJ 3110

传送门

整体二分
树套树

首先强调以下这道题是 真·第$k$

整体二分

这道题有时间先后顺序限制,所以排序时不能把顺序打乱,所以要另外开一个数组用来排序并对它二分答案

因为是区间修改嘛,我又不会区间修改的高端树状数组,就只能用线段树了…每次$Solve$都清空整棵树好像会超时,于是我打了删除标记 然后就掉坑里爬不出来了

二分排过序的那个数组,然后依次处理从$head$到$tail$的操作(一定要注意先后顺序),有以下几种情况

  • 若是添加,且添加的数$\geq mid$,说明这个数对右边一半的影响都相同,只需要减去它的影响就行了,但它对左边一半的影响不相同,所以扔到左边(因为第$k$大嘛所以数组顺序是从大到小的)
  • 若是添加,且添加的数$<mid$,它对左边一半就没有任何影响了,但对右边有影响,所以扔到右边
  • 若询问区间内的数的个数$<k$,说明还不够多,扔到右边再多加几个
  • 若询问区间内的数的个数$\geq k$,说明已经够了,扔到左边

这样就把$head$到$tail$的操作分成了两块互不影响且符合时间轴顺序的操作,继续递归到底就能得出答案


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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
program bzoj_3110;
var s:array[0..100000]of record l,r,lc,rc,size,plus:longint; clear:boolean; end;
q,q1,q2:array[1..50000]of record cas,l,r,k,p,cur:longint; end;
ans,a:array[1..50000]of longint;
n,m,i,tot,t,len:longint;
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;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure pushdown(t:longint);
begin
if s[t].clear then
begin
if (s[t].lc<>0)and(s[t].rc<>0) then
begin
s[s[t].lc].size:=0;
s[s[t].lc].plus:=0;
s[s[t].lc].clear:=true;
s[s[t].rc].size:=0;
s[s[t].rc].plus:=0;
s[s[t].rc].clear:=true;
s[t].clear:=false;
end;
end;
if s[t].plus<>0 then
begin
if (s[t].lc<>0)and(s[t].rc<>0) then
begin
inc(s[s[t].lc].size,s[t].plus*(s[s[t].lc].r-s[s[t].lc].l+1));
inc(s[s[t].lc].plus,s[t].plus);
inc(s[s[t].rc].size,s[t].plus*(s[s[t].rc].r-s[s[t].rc].l+1));
inc(s[s[t].rc].plus,s[t].plus);
end;
s[t].plus:=0;
end;
end;
procedure build(var t:longint;l,r:longint);
var mid:longint;
begin
inc(tot);
t:=tot;
s[t].l:=l;
s[t].r:=r;
s[t].lc:=0;
s[t].rc:=0;
s[t].plus:=0;
s[t].clear:=false;
s[t].size:=0;
if l=r then exit;
mid:=(l+r)>>1;
build(s[t].lc,l,mid);
build(s[t].rc,mid+1,r);
end;
procedure cover(t,l,r:longint);
var mid:longint;
begin
if (s[t].clear)or(s[t].plus<>0) then pushdown(t);
if (l<=s[t].l)and(r>=s[t].r) then
begin
inc(s[t].size,s[t].r-s[t].l+1);
inc(s[t].plus);
pushdown(t);
exit;
end;
mid:=(s[t].l+s[t].r)>>1;
if l<=mid then cover(s[t].lc,l,r);
if r>mid then cover(s[t].rc,l,r);
s[t].size:=s[s[t].lc].size+s[s[t].rc].size;
end;
function query(t,l,r:longint):longint;
var ans,mid:longint;
begin
if (s[t].plus<>0)or s[t].clear then pushdown(t);
if (l<=s[t].l)and(r>=s[t].r) then exit(s[t].size);
mid:=(s[t].l+s[t].r)>>1;
ans:=0;
if l<=mid then inc(ans,query(s[t].lc,l,r));
if r>mid then inc(ans,query(s[t].rc,l,r));
exit(ans);
end;
procedure solve(l,r,hd,tl:longint);
var i,mid,l1,l2,t:longint;
begin
if hd>tl then exit;
if l=r then
begin
for i:=hd to tl do if q[i].cas=2 then ans[q[i].p]:=l;
exit;
end;
s[1].clear:=true;
s[1].size:=0;
s[1].plus:=0;
pushdown(1);
mid:=(l+r)>>1;
l1:=0;
l2:=0;
for i:=hd to tl do
if q[i].cas=2 then
begin
t:=query(1,q[i].l,q[i].r);
if q[i].cur+t>=q[i].k then
begin
inc(l1);
q1[l1]:=q[i];
end else
begin
inc(q[i].cur,t);
inc(l2);
q2[l2]:=q[i];
end;
end else
if q[i].k>=a[mid] then
begin
inc(l1);
q1[l1]:=q[i];
cover(1,q[i].l,q[i].r)
end else
begin
inc(l2);
q2[l2]:=q[i];
end;
for i:=1 to l1 do q[hd+i-1]:=q1[i];
for i:=1 to l2 do q[hd+l1+i-1]:=q2[i];
if l1<>0 then solve(l,mid,hd,hd+l1-1);
if l2<>0 then solve(mid+1,r,hd+l1,tl);
end;
begin
readln(n,m);
len:=0;
for i:=1 to m do with q[i] do
begin
readln(cas,l,r,k);
p:=i;
cur:=0;
if cas=1 then
begin
inc(len);
a[len]:=k;
end;
end;
qsort(1,len);
tot:=0;
build(t,1,n);
solve(1,len,1,m);
for i:=1 to m do if ans[i]<>0 then writeln(a[ans[i]]);
end.

树套树

两层线段树,第一层是按$c$建的权值线段树,每次加入操作把所有包含$c$的第一层线段树的节点的子线段树的$[a,b]$覆盖

第二层需要动态开点,否则MLE…

查询时直接在第一层线段树上二分即可


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
program bzoj_3110;
var s1:array[0..100000]of record lc,rc,subtree:longint; end;
s2:array[0..18000000]of record lc,rc,size,plus:longint; end;
n,m,i,cas,a,b,c,tot1,tot2,t:longint;
procedure new(var t:longint);
begin
inc(tot2);
t:=tot2;
end;
procedure build(var t:longint;l,r:longint);
var mid:longint;
begin
inc(tot1);
t:=tot1;
new(s1[t].subtree);
if l=r then exit;
mid:=(l+r)>>1;
build(s1[t].lc,mid+1,r);
build(s1[t].rc,l,mid);
end;
procedure pushdown(t,l,r:longint);
var mid:longint;
begin
if (l<>r)and(s2[t].lc=0) then new(s2[t].lc);
if (l<>r)and(s2[t].rc=0) then new(s2[t].rc);
if (s2[t].lc<>0)and(s2[t].rc<>0) then
begin
mid:=(l+r)>>1;
inc(s2[s2[t].lc].size,s2[t].plus*(mid-l+1));
inc(s2[s2[t].lc].plus,s2[t].plus);
inc(s2[s2[t].rc].size,s2[t].plus*(r-mid));
inc(s2[s2[t].rc].plus,s2[t].plus);
end;
s2[t].plus:=0;
end;
procedure modify(var t:longint;a,b,l,r:longint);
var mid:longint;
begin
if t=0 then new(t);
mid:=(a+b)>>1;
if s2[t].plus<>0 then pushdown(t,a,b);
if (l<=a)and(r>=b) then
begin
inc(s2[t].size,b-a+1);
s2[t].plus:=1;
exit;
end;
if l<=mid then modify(s2[t].lc,a,mid,l,r);
if r>mid then modify(s2[t].rc,mid+1,b,l,r);
s2[t].size:=s2[s2[t].lc].size+s2[s2[t].rc].size;
end;
procedure insert(t,l,r,a,b,c:longint);
var mid:longint;
begin
modify(s1[t].subtree,1,n,a,b);
if l=r then exit;
mid:=(l+r)>>1;
if c>mid then insert(s1[t].lc,mid+1,r,a,b,c) else insert(s1[t].rc,l,mid,a,b,c);
end;
function query(t,l,r,a,b:longint):longint;
var ans,mid:longint;
begin
mid:=(l+r)>>1;
if s2[t].plus<>0 then pushdown(t,l,r);
if (a<=l)and(b>=r) then exit(s2[t].size);
ans:=0;
if a<=mid then inc(ans,query(s2[t].lc,l,mid,a,b));
if b>mid then inc(ans,query(s2[t].rc,mid+1,r,a,b));
exit(ans);
end;
function ask(t,l,r,a,b,c:longint):longint;
var p,mid:longint;
begin
if l=r then exit(l);
p:=query(s1[s1[t].lc].subtree,1,n,a,b);
mid:=(l+r)>>1;
if c<=p then exit(ask(s1[t].lc,mid+1,r,a,b,c)) else exit(ask(s1[t].rc,l,mid,a,b,c-p));
end;
begin
readln(n,m);
tot1:=0;
tot2:=0;
build(t,1,n);
for i:=1 to m do
begin
readln(cas,a,b,c);
if cas=1 then insert(1,1,n,a,b,c) else writeln(ask(1,1,n,a,b,c));
end;
end.

为啥锚记挂了…明明2150还可以用呢…