维护 $n$ 个可重集，初始都是空集，有 $m$ 个操作：
1 l r c：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中2 l r c：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。
树套树
对于多维度信息，我们可以使用树套树维护。
顾名思义，即建一棵树，而这个树上的每一个节点都包含一棵树。而这两棵树，维护的往往是不同维度的信息。
同时，外层树不能使用懒标记，因为你不能高效地将更新上传；外层树只能写标记永久化，内层树可以使用懒标记。
以线段树套线段树为例。
一般的空间都不支持我们开 $n$ 棵完整的线段树，因此我们一般内层树都是动态开点线段树。对于外层，可以写动态开点，也可以离散化后写普通线段树。
单次修改/查询复杂度 $\mathcal O\left(\log^2n\right)$。
Luogu P3332 [ZJOI2013] K 大数查询
需要查询第 $k$ 大，可以权值线段树上二分。
又受到 $[l,r]$ 限制，因此可以权值线段树套区间线段树维护。
外层权值线段树可以离散化，并且需要标记永久化。
需要注意的是，内层区间线段树需要从各自的根节点开始访问，而不是 $1$。
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
171
172
173
174
175
176
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=5e4,M=5e4;
struct operation{
int op,l,r,x;
}q[M+1];
int n,m,len,tmp[M+1];
void discrete(){
for(int i=1;i<=m;i++){
if(q[i].op==1){
tmp[++len]=q[i].x;
}
}
sort(tmp+1,tmp+len+1);
len=unique(tmp+1,tmp+len+1)-tmp-1;
for(int i=1;i<=m;i++){
if(q[i].op==1){
q[i].x=lower_bound(tmp+1,tmp+len+1,q[i].x)-tmp;
}
}
}
int size;
struct node{
int l,r;
ll value,tag;
int lChild,rChild;
int size(){
return r-l+1;
}
}t[(N<<2|1)*80+1];
struct segTree{
struct inside{
int l,r;
int root;
int create(node x){
t[++size]=x;
return size;
}
void build(int l,int r){
root=create({l,r});
}
void up(int p){
t[p].value=t[t[p].lChild].value+t[t[p].rChild].value;
}
void down(int p){
int mid=t[p].l+t[p].r>>1;
if(!t[p].lChild){
t[p].lChild=create({t[p].l,mid});
}
if(!t[p].rChild){
t[p].rChild=create({mid+1,t[p].r});
}
if(t[p].tag){
t[t[p].lChild].value+=t[t[p].lChild].size()*t[p].tag;
t[t[p].lChild].tag+=t[p].tag;
t[t[p].rChild].value+=t[t[p].rChild].size()*t[p].tag;
t[t[p].rChild].tag+=t[p].tag;
t[p].tag=0;
}
}
void add(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
t[p].value+=t[p].size()*x;
t[p].tag+=x;
return;
}
down(p);
if(l<=t[t[p].lChild].r){
add(t[p].lChild,l,r,x);
}
if(t[t[p].rChild].l<=r){
add(t[p].rChild,l,r,x);
}
up(p);
}
void add(int l,int r,int x){
add(root,l,r,x);
}
ll query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].value;
}
down(p);
int ans=0;
if(l<=t[t[p].lChild].r){
ans=query(t[p].lChild,l,r);
}
if(t[t[p].rChild].l<=r){
ans+=query(t[p].rChild,l,r);
}
return ans;
}
ll query(int l,int r){
return query(root,l,r);
}
}T[N<<2|1];
void build(int p,int l,int r){
T[p]={l,r};
T[p].build(1,n);
if(l==r){
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void add(int p,int x,int l,int r){
if(T[p].l==T[p].r){
T[p].add(l,r,1);
return;
}
T[p].add(l,r,1);
if(x<=T[p<<1].r){
add(p<<1,x,l,r);
}else{
add(p<<1|1,x,l,r);
}
}
int query(int p,int l,int r,int k){
if(T[p].l==T[p].r){
return T[p].l;
}
ll pl=T[p<<1|1].query(l,r);
if(pl<k){
return query(p<<1,l,r,k-pl);
}else{
return query(p<<1|1,l,r,k);
}
}
}T;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>q[i].op>>q[i].l>>q[i].r>>q[i].x;
}
discrete();
T.build(1,1,len);
for(int i=1;i<=m;i++){
switch(q[i].op){
case 1:
T.add(1,q[i].x,q[i].l,q[i].r);
break;
case 2:
cout<<tmp[T.query(1,q[i].l,q[i].r,q[i].x)]<<'\n';
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
