有 N 个位置，M 个操作。每个位置可以同时存储多个数。

操作有两种，每次操作:

如果是 1 a b c 的形式，表示在第 a 个位置到第 b 个位置，每个位置加入一个数 c。
如果是 2 a b c 的形式，表示询问从第 a 个位置到第 b 个位置，第 c 大的数是多少。
输入格式
第一行包含两个整数 N,M。

接下来 M 行，每行包含一条指令，形如 1 a b c 或 2 a b c。

输出格式
输出每个询问的结果，每个结果占一行。

数据范围
1≤N,M≤50000,
1≤a≤b≤N,
1 操作中的 c 的绝对值不超过 N,
2 操作中 c 满足 1≤c≤231−1。

思路：
开权值线段树 ，权值线段树上的每个点对应题目所给的位置，然后就是区间修改和区间查询了，然后如果传统全开线段树的话 空间N^2，这里我们用动态开点，空间优化到NlogNlogN

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=50010,P=N*16*16,M=4*N;
struct node{
   
	int l;
	int r;
	int add;
	int sum;
}tr[P];
int n,m;
int T[M],L[M],R[M];
struct qr{
   
	int op,a,b,c;
}q[N];
int idx;
vector<int>nums;
int get(int x)
{
   
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
int intersection(int a,int b,int c,int d)
{
   
	return min(b,d)-max(a,c)+1;
}
void build(int u,int l,int r)
{
   
	T[u]=++idx,L[u]=l,R[u]=r;
	if(l==r)	return ;
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}


void update(int u,int l,int r,int pl,int pr)
{
   
	tr[u].sum+=intersection(l,r,pl,pr);
	if(l>=pl && r<=pr)
	{
   
		tr[u].add++;
		return ;
	}
	int mid=l+r>>1;
	if(pl<=mid)
	{
   
		if(!tr[u].l) tr[u].l=++idx;
		update(tr[u].l,l,mid,pl,pr);
	}
	if(pr>mid)
	{
   
		if(!tr[u].r) tr[u].r=++idx;
		update(tr[u].r,mid+1,r,pl,pr);
	}

}
void change(int u,int a,int b,int c)
{
   
	update(T[u],1,n,a,b);
	if(L[u]==R[u])
		return ;
	int mid=L[u]+R[u]>>1;
	if(c<=mid)	change(u<<1,a,b,c);
	else	change(u<<1|1,a,b,c);
}
int get_sum(int u,int l,int r,int pl,int pr,int add)
{
   
	if(l>=pl && r<=pr)
	{
   
		return tr[u].sum+(r-l+1)*add;
	}
	add+=tr[u].add;
	int res=0;
	int mid=l+r>>1;
	if(pl<=mid)
	{
   
		if(tr[u].l)
			res+= get_sum(tr[u].l,l,mid,pl,pr,add);
		else
			res+=add*intersection(l,mid,pl,pr);
	}


	if(pr>mid)
	{
   
		if(tr[u].r)
			res+=get_sum(tr[u].r,mid+1,r,pl,pr,add);
		else
			res+=add*intersection(mid+1,r,pl,pr);
	}
	return res;

}
int query(int u,int a,int b,int k)
{
   
	if(L[u]==R[u])
		return R[u];
	int c=get_sum(T[u<<1|1],1,n,a,b,0);
	if(k<=c)
		return query(u<<1|1,a,b,k);
	else
		return query(u<<1,a,b,k-c);
}
int main()
{
   
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
   
		int op,a,b,c;
		cin>>op>>a>>b>>c;
		q[i]={
   op,a,b,c};
		if(op==1)
			nums.push_back(c);
	}
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	build(1,0,nums.size()-1);
	for(int i=0;i<m;i++)
	{
   
		int op=q[i].op,a=q[i].a,b=q[i].b,c=q[i].c;
		if(op==1)
		{
   
			change(1,a,b,get(c));
		}
		else
		{
   
			cout<<nums[query(1,a,b,c)]<<endl;
		}
	}
	return 0;
}
// 2 5
// 1 1 2 1
// 1 1 2 2
// 2 1 1 2
// 2 1 1 1
// 2 1 2 3