BZOJ

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还可以用呢…