题目传送门
维护 \(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\)。
//#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;
}