Description：

有 $N$ 个位置， $M$ 个操作。操作有两种，1、在第 $a$ 个位置到第 $b$ 个位置，每个位置加入一个数；2、询问从第 $a$ 个位置到第 $b$ 个位置，第 $C$ 大的数是多少。

$1\le n,m \le 50000$

Solution：

离散化数组一定不要用错！！！

离散化 $+$ 权值线段树套区间线段树。区间线段树维护这些权值在区间上的和。在权值线段树上左右走的过程相当于二分，每次在区间线段树上查询区间和，并判断右边是否够 $C$ 个，如果够，向右走，如果不够，向左走。加入时在从加入权值所在的叶子节点到根的路径上的线段树中区间加。空间开不下，于是区间线段树可以动态开点，因为实际用不到很多点，动态开点的线段树需要标记永久化。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define INF 0x3f3f3f3f3f3f3f3f

typedef long long ll;

struct query

{

	int type,l,r;

	ll k;

}q[MAXN];

ll a[MAXN];

int tot = 0,cnt = 0;

ll to[MAXN];

map<ll,int> fr;

namespace seg

{

	struct node

	{

		int lc,rc;

		ll tag,sum;

	}t[MAXN * 500];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		t[rt].sum = 0;

		return;

	}

	void add(int &rt,int L,int R,int l,int r)

	{

		if(rt == 0){rt = newnode();t[rt].sum = 0;}

		t[rt].sum += (ll)(R - L + 1);

		if(L <= l && r <= R){t[rt].tag += 1;return;}

		if(R <= mid){add(t[rt].lc,L,R,l,mid);return;}

		if(L > mid){add(t[rt].rc,L,R,mid + 1,r);return;}

		add(t[rt].lc,L,mid,l,mid);add(t[rt].rc,mid + 1,R,mid + 1,r);

		return;

	}

	ll query(int rt,int L,int R,int l,int r)

	{

		if(rt == 0)return 0;

		if(L <= l && r <= R)return t[rt].sum;

		if(R <= mid)return query(t[rt].lc,L,R,l,mid) + (ll)(R - L + 1) * t[rt].tag;

		if(L > mid)return query(t[rt].rc,L,R,mid + 1,r) + (ll)(R - L + 1) * t[rt].tag;

		return query(t[rt].lc,L,mid,l,mid) + query(t[rt].rc,mid + 1,R,mid + 1,r) + (ll)(R - L + 1) * t[rt].tag;

	}

}

namespace val

{

	struct node

	{

		int lc,rc;

		int root;

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	void build(int &rt,int l,int r)

	{

		rt = newnode();seg::build(t[rt].root,1,n);

		if(l == r)return;

		build(t[rt].lc,l,mid);

		build(t[rt].rc,mid + 1,r);

		return;

	}

	void add(int rt,int L,int R,int k,int l,int r)

	{

		seg::add(t[rt].root,L,R,1,n);

		if(l == r)return;

		if(k <= mid)add(t[rt].lc,L,R,k,l,mid);

		else add(t[rt].rc,L,R,k,mid + 1,r);

		return;

	}

	ll query(int rt,int L,int R,ll k,int l,int r)

	{

		if(l == r)return to[l];

		ll s = seg::query(t[t[rt].rc].root,L,R,1,n);

		if(s >= k)return query(t[rt].rc,L,R,k,mid + 1,r);

		else return query(t[rt].lc,L,R,k - s,l,mid);

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)scanf("%d%d%d%lld",&q[i].type,&q[i].l,&q[i].r,&q[i].k);

	for(int i = 1;i <= m;++i)if(q[i].type == 1)a[++tot] = q[i].k;

	sort(a + 1,a + 1 + tot);

	a[0] = -INF;cnt = 0;

	for(int i = 1;i <= tot;++i)if(a[i] != a[i - 1]){to[++cnt] = a[i];fr[a[i]] = cnt;}

	val::build(val::root,1,cnt);

	for(int i = 1;i <= m;++i)

	{

		if(q[i].type == 1)val::add(val::root,q[i].l,q[i].r,fr[q[i].k],1,cnt);

		else printf("%lld\n",val::query(val::root,q[i].l,q[i].r,q[i].k,1,cnt));

	}

	return 0;

}