题目描述
有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
输出
输出每个询问的结果
样例输入
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
样例输出
1
2
1
题解
本蒟蒻并不会写整体二分，所以写了树套树
17.12.23 UPD：比树套树优雅到不知哪里去了的整体二分题解
其实这道题想到方法的话实现起来还是非常容易的。
注意题目中说的是“每个位置加入一个数c”，不是“加上”，也就是说不必支持修改，但必须支持插入。
所以需要选择权值线段树或Treap。
如果把权值线段树或Treap放在内层，区间线段树放在外层，那么会不方便查询（详见 bzoj3194 中子任务2），时间复杂度为O(nlog^3n)，TLE；同时也不便于修改。
所以不能把权值线段树或Treap放在内层，必须放在外层，外层就只能选择权值线段树。
把权值线段树放在外层，区间线段树放在内层的话，每个最内层节点表示区间内权值在指定范围内的数的个数。
这样修改时在外层查找对应区间，在内层区间+1，使用lazy标记可以保证时间复杂度。
查询时查的是第k大，所以需要先确定范围。如果权值线段树的右子树对应的区间线段树的区间和（线段树区间查询）大于等于k，即右半部分权值中含有k大数，则在右边查找；否则在左边查找。
注意要把两棵树分开（表示代码可能分的不太清楚。。。），千万不要弄混。
在我的代码中，外层权值线段树是用一般的完全二叉树储存方式(x<<1,x<<1|1)，而内层区间线段树是用动态开点的储存方式。
而这里的pushdown、update和query这前三个函数是内层区间线段树的函数；modify、solve是外层权值线段树的函数。
另外，数据经加强后会有负数，所以应把原数+n+1处理。
另外，本题会爆int，而long long可能会TLE，最好是用unsigned int。
#include <cstdio>
#include <algorithm>
#define N 1000010
#define M 20000010
using namespace std;
int n , root[N] , ls[M] , rs[M] , tot;
unsigned sum[M] , tag[M];
void pushdown(int l , int r , int x)
{
if(tag[x])
{
int mid = (l + r) >> 1;
if(!ls[x]) ls[x] = ++tot;
if(!rs[x]) rs[x] = ++tot;
sum[ls[x]] += (mid - l + 1) * tag[x] , tag[ls[x]] += tag[x];
sum[rs[x]] += (r - mid) * tag[x] , tag[rs[x]] += tag[x];
tag[x] = 0;
}
}
void update(int b , int e , int l , int r , int &x)
{
if(!x) x = ++tot;
if(b <= l && r <= e)
{
sum[x] += (r - l + 1) , tag[x] ++ ;
return;
}
pushdown(l , r , x);
int mid = (l + r) >> 1;
if(b <= mid) update(b , e , l , mid , ls[x]);
if(e > mid) update(b , e , mid + 1 , r , rs[x]);
sum[x] = sum[ls[x]] + sum[rs[x]];
}
unsigned query(int b , int e , int l , int r , int x)
{
if(b <= l && r <= e) return sum[x];
pushdown(l , r , x);
int mid = (l + r) >> 1;
unsigned ans = 0;
if(b <= mid) ans += query(b , e , l , mid , ls[x]);
if(e > mid) ans += query(b , e , mid + 1 , r , rs[x]);
return ans;
}
void modify(int b , int e , int p , int l , int r , int x)
{
update(b , e , 1 , n , root[x]);
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) modify(b , e , p , l , mid , x << 1);
else modify(b , e , p , mid + 1 , r , x << 1 | 1);
}
int solve(int b , int e , unsigned a , int l , int r , int x)
{
if(l == r) return l;
int mid = (l + r) >> 1;
unsigned tmp = query(b , e , 1 , n , root[x << 1 | 1]);
if(tmp >= a) return solve(b , e , a , mid + 1 , r , x << 1 | 1);
else return solve(b , e , a - tmp , l , mid , x << 1);
}
int main()
{
int m , opt , x , y , z;
unsigned t;
scanf("%d%d" , &n , &m);
while(m -- )
{
scanf("%d%d%d" , &opt , &x , &y);
if(opt == 1) scanf("%d" , &z) , modify(x , y , z + n + 1 , 1 , 2 * n + 1 , 1);
else scanf("%u" , &t) , printf("%d\n" , solve(x , y , t , 1 , 2 * n + 1 , 1) - n - 1);
}
return 0;
}