题目大意：有一些位置。这些位置上能够放若干个数字。

如今有两种操作。

1.在区间l到r上加入一个数字x

2.求出l到r上的第k大的数字是什么

思路：这样的题一看就是树套树，关键是怎么套，怎么写。（话说我也不会来着。。）最easy想到的方法就是区间线段树套一个权值线段树。可是区间线段树上的标记就会变得异常复杂。所以我们就反过来套，用权值线段树套区间线段树。

这样改动操作在外线段树上就变成了单点改动。外线段树就不用维护标记了。在里面的区间线段树上维护标记就easy多了。详细实现见代码。

CODE：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAX 50010

#define CNT (r - l + 1)

using namespace std;

int total,asks;

struct ValSegTree{

	ValSegTree *son[2];

	int cnt,c;

	ValSegTree() {

		son[0] = son[1] = NULL;

		cnt = c = 0;

	}

	void PushDown(int k) {

		if(son[0] == NULL)	son[0] = new ValSegTree();

		if(son[1] == NULL)	son[1] = new ValSegTree();

		if(c) {

			son[0]->cnt += c * (k - (k >> 1));

			son[0]->c += c;

			son[1]->cnt += c * (k >> 1);

			son[1]->c += c;

			c = 0;

		}

	}

	void Modify(int l,int r,int x,int y) {

		if(l == x && r == y) {

			cnt += CNT;

			c++;

			return ;

		}

		PushDown(CNT);

		int mid = (l + r) >> 1;

		if(y <= mid)	son[0]->Modify(l,mid,x,y);

		else if(x > mid)	son[1]->Modify(mid + 1,r,x,y);

		else {

			son[0]->Modify(l,mid,x,mid);

			son[1]->Modify(mid + 1,r,mid + 1,y);

		}

		cnt = son[0]->cnt + son[1]->cnt;

	}

	int Ask(int l,int r,int x,int y) {

		if(!cnt)	return 0;

		if(l == x && r == y)	return cnt;

		PushDown(CNT);

		int mid = (l + r) >> 1;

		if(y <= mid)	return son[0]->Ask(l,mid,x,y);

		if(x > mid)		return son[1]->Ask(mid + 1,r,x,y);

		int left = son[0]->Ask(l,mid,x,mid);

		int right = son[1]->Ask(mid + 1,r,mid + 1,y);

		return left + right;

	}

};

struct IntSegTree{

	IntSegTree *son[2];

	ValSegTree *root;

	IntSegTree() {

		son[0] = son[1] = NULL;

		root = new ValSegTree();

	}

	void Modify(int l,int r,int _l,int _r,int x) {

		root->Modify(1,total,_l,_r);

		if(l == r)	return ;

		int mid = (l + r) >> 1;

		if(son[0] == NULL)	son[0] = new IntSegTree();

		if(son[1] == NULL)	son[1] = new IntSegTree();

		if(x <= mid)	son[0]->Modify(l,mid,_l,_r,x);

		else	son[1]->Modify(mid + 1,r,_l,_r,x);

	}

	int Ask(int l,int r,int _l,int _r,int k) {

		if(l == r)	return l;

		int mid = (l + r) >> 1;

		if(son[0] == NULL)	son[0] = new IntSegTree();

		if(son[1] == NULL)	son[1] = new IntSegTree();

		int temp = son[1]->root->Ask(1,total,_l,_r);

		if(k > temp)	return son[0]->Ask(l,mid,_l,_r,k - temp);

		else	return son[1]->Ask(mid + 1,r,_l,_r,k);

	}

}root;

int main()

{

	cin >> total >> asks;

	for(int flag,x,y,z,i = 1;i <= asks; ++i) {

		scanf("%d%d%d%d",&flag,&x,&y,&z);

		if(flag == 1)	root.Modify(1,total,x,y,z);

		else	printf("%d\n",root.Ask(1,total,x,y,z));

	}

	return 0;

}