前置技能
当然是线段树啦！
应用及实现
线段树可以维护一个序列。当需要维护一个矩阵（即二维平面）内的数值，或者有什么奇怪的区间操作时，就需要用到二维线段树，也就是线段树“套上”线段树。
当维护一个矩阵时，先建一颗“外面的”线段树来维护一维，对于每个“外面的”线段树的节点，建一颗“里面的”线段树来维护第二维。因为博主太懒没有写过这里就直接贴大佬的Blog好了。
模板
当维护区间奇怪操作时，一般的套路是外面套权值线段树，里面套区间线段树。比如说BZOJ3110（洛谷P3332）这道题，它要求我们维护n个位置，修改操作
因为插入的权值≤maxlongint，总操作≤50000次，因此需要离散。 但是因为数据太水所以不离散也能过尽管BZOJ说加强了数据我也不知道怎么回事
对于插入操作，单点修改权值线段树，区间修改区间线段树（区间线段树维护的是当前区间这个数出现的次数）。
对于查询操作，类似二分的在权值线段树上递归，每次统计这个权值线段树右子树对应的区间线段树在询问区间内的区间和。如果答案（ans）≥当前排名就递归右子树的第k大，否则递归左子树的第k-ans大。
代码（好像离散比不离散在BZOJ上快了近一秒钟）：
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define N 50005
using namespace std;
typedef long long LL;
struct intree{ int ls,rs; LL s,lz; }t[N<<8];
struct query{ int f,l,r; LL w; }q[N];
int n,m,nd,num,rt[N<<8];
LL a[N];
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
if (l==r) return EOF; return *l++;
}
inline LL _read(){
int x=0,f=1; char ch=readc();
while (!isdigit(ch)) { if (ch=='-') f=-1; ch=readc(); }
while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
return x*f;
}
inline void writec(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) writec(x/10); putchar(x%10+'0');
}
inline void _write(int x){ writec(x),putchar('\n'); }
inline void nsrt(int &x,int l,int r,int p,int q){
if (!x) x=++nd; t[x].s+=(LL)q-p+1;
if (l>=p&&r<=q) return (void)++t[x].lz;
int mid=l+r>>1;
if (q<=mid) return nsrt(t[x].ls,l,mid,p,q);
if (p>mid) return nsrt(t[x].rs,mid+1,r,p,q);
nsrt(t[x].ls,l,mid,p,mid),nsrt(t[x].rs,mid+1,r,mid+1,q);
}
inline void build(int x,int l,int r,int p,int q,int w){
nsrt(rt[x],1,n,p,q);
if (l==r) return; int mid=l+r>>1;
if (w<=mid) build(x<<1,l,mid,p,q,w);
else build(x<<1|1,mid+1,r,p,q,w);
}
inline LL srch(int x,int l,int r,int p,int q){
if (!x) return 0; int mid=l+r>>1;
if (l>=p&&r<=q) return t[x].s;
LL ans=t[x].lz*(LL)(q-p+1);
if (q<=mid) return ans+srch(t[x].ls,l,mid,p,q);
if (p>mid) return ans+srch(t[x].rs,mid+1,r,p,q);
return ans+srch(t[x].ls,l,mid,p,mid)+srch(t[x].rs,mid+1,r,mid+1,q);
}
inline int ef(int x,int l,int r,int p,int q,LL w){
if (l==r) return l; int mid=l+r>>1;
LL pd=srch(rt[x<<1|1],1,n,p,q);
if (pd<w) return ef(x<<1,l,mid,p,q,w-pd);
return ef(x<<1|1,mid+1,r,p,q,w);
}
inline int calc(LL x){
return lower_bound(a+1,a+num+1,x)-a-1;
}
int main(){
n=_read(),m=_read();
for (int i=1;i<=m;i++){
q[i].f=_read(),q[i].l=_read(),q[i].r=_read(),q[i].w=_read();
if (q[i].f==1) a[++num]=q[i].w;
}
sort(a+1,a+num+1),num=unique(a+1,a+num+1)-a-1;
for (int i=1;i<=m;i++)
if (q[i].f==1)
build(1,1,num,q[i].l,q[i].r,calc(q[i].w)+1);
else _write(a[ef(1,1,num,q[i].l,q[i].r,q[i].w)]);
return 0;
}