Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
Input
第一行N，M
接下来M行，每行形如1 a b c或2 a b c
Output
输出每个询问的结果
Sample Input
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
Sample Output
2
1
HINT
【样例说明】
第一个操作 后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。 第二个操作 后位置 1
的数有 1 、 2 ，位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是
1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3
大的数是 1 。
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint
Source
Solution
树套树。。。说难不难，说简单不简单。曾经花了一星期理解内外线段树的关系。。。一直不理解怎么“套”一棵树的
树套树的一般做法是用两个树形结构，外层代表区间，内层代表该区间下的权值信息或其它的什么
相当于一个二维矩阵，一维是区间信息一维是权值信息。
嘛，其实就是外层线段树纪录它对应的内层线段树的节点编号，内层线段树纪录该区间下与某权值范围的的结点信息
为了省空间，需用动态开点的姿势。在这里给各位提个醒：这道题开2000000就好。
嗯= =其实就是把线段树update和query写两遍233
蛋碎了一地。数组开大MLE，数组开小RE。
这道题外层区间内层权值有点麻烦，所以换一种思路：外层权值线段树内层区间线段树。递归查询某一段权值范围内有多少数，若个数小于询问数则向左子树递归，否则向右子树递归。
= =
好吧我的确给别人讲不懂 _(:з」∠)_
代码常熟大地飞起。标记永久化是什么可以吃吗
yky大爷讲了一种奥妙丛丛的压缩空间的方法：把结构体里的变量压缩为x位整型。因为好像存和要用unsigned int于是干脆用long long。具体用法看代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct seg1
{
ll l:, r:, sum:, lazy:;
}p1[];
struct operation
{
ll op, l, r, val;
}op[];
ll n, p2[], ptot, cd[], ctot, ql, qr, val; void push_up(ll o, ll l, ll r)
{
p1[o].sum = p1[p1[o].l].sum + p1[p1[o].r].sum + p1[o].lazy * (r - l + );
} void push_down(ll o, ll l, ll r)
{
ll mid = (l + r) >> ;
if(!p1[o].l) p1[o].l = ++ptot;
if(!p1[o].r) p1[o].r = ++ptot;
if(p1[o].lazy)
{
p1[p1[o].l].lazy += p1[o].lazy;
p1[p1[o].r].lazy += p1[o].lazy;
p1[p1[o].l].sum += p1[o].lazy * (mid - l + );
p1[p1[o].r].sum += p1[o].lazy * (r - mid);
p1[o].lazy = ;
}
} void update1(ll o, ll l, ll r)
{
ll mid = (l + r) >> ;
if(ql <= l && r <= qr)
{
p1[o].sum += r - l + , p1[o].lazy++;
return;
}
push_down(o, l, r);
if(ql <= mid) update1(p1[o].l, l, mid);
if(mid < qr) update1(p1[o].r, mid + , r);
push_up(o, l, r);
} void update2(ll o, ll l, ll r)
{
ll mid = (l + r) >> ;
if(!p2[o]) p2[o] = ++ptot;
update1(p2[o], , n);
if(l == r) return;
if(val <= mid) update2(o << , l, mid);
else update2(o << | , mid + , r);
} ll query1(ll o, ll l, ll r)
{
ll mid = (l + r) >> , cnt = ;
if(ql <= l && r <= qr) return p1[o].sum;
push_down(o, l, r);
if(ql <= mid) cnt = query1(p1[o].l, l, mid);
if(mid < qr) cnt += query1(p1[o].r, mid + , r);
return cnt;
} ll query2(ll o, ll l, ll r, ll rk)
{
ll mid = (l + r) >> ;
if(l == r) return l;
if(!p2[o]) p2[o] = ++ptot;
val = query1(p2[o << | ], , n);
if(val < rk) return query2(o << , l, mid, rk - val);
return query2(o << | , mid + , r, rk);
} int main()
{
ll m;
scanf("%lld%lld", &n, &m);
for(ll i = ; i <= m; i++)
{
scanf("%lld%lld%lld%lld", &op[i].op, &op[i].l, &op[i].r, &op[i].val);
if(op[i].op == ) cd[++ctot] = op[i].val;
}
sort(cd + , cd + ctot + );
for(int i = ; i <= m; i++)
if(op[i].op == )
op[i].val = lower_bound(cd + , cd + ctot + , op[i].val) - cd;
for(ll i = ; i <= m; i++)
if(op[i].op == )
{
ql = op[i].l, qr = op[i].r, val = op[i].val;
update2(, , ctot);
}
else
{
ql = op[i].l, qr = op[i].r;
printf("%lld\n", cd[query2(, , ctot, op[i].val)]);
}
return ;
}