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
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
Sample Output
1
2
1
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操作中abs(c)<=Maxlongint
Source
【分析】
我可以吐槽一下数据很水吗？1A了
表示整体二分大法好，离线第K大都不怕。
区间修改用线段树和树状数组都可以水。
/*
明代杨慎
《临江仙·滚滚长江东逝水》 滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#define LOCAL
const int INF = 0x7fffffff;
const int MAXN = + ;
using namespace std;
//整体二分+树状数组的区间修改！
struct QUESTION{
int l, r;
int k, s, cur, type;
}q[MAXN];
int id[MAXN];
int Max, Min, n, m, Ans[MAXN];
int c[][MAXN];//0是普通和，1是全部和
int tmp[MAXN], q1[MAXN], q2[MAXN], cnt; int lowbit(int x) {return x & -x;}
int sum(int k, int x){
int cnt = ;
while (x > ){
cnt += c[k][x];
x -= lowbit(x);
}
return cnt;
}
void add(int k, int x, int val){
while (x <= n){
c[k][x] += val;
x += lowbit(x);
}
return;
}
//得到一个点真实的前缀和
int get(int x){
if (x == )
printf("");
return sum(, x) - sum(, x) * (n - x);
}
//整体二分
void solve(int l, int r, int L, int R){
if (l > r || L == R) return; int mid = (L + R) >> ;
for (int i = l; i <= r; i++){
//区间加
if (q[id[i]].type == && q[id[i]].k >= mid){//注意是区间第k大
int a = q[id[i]].l, b = q[id[i]].r;
add(, a, );
add(, b + , -);
add(, a, n - a + );
add(, b + , - (n - (b + ) + ));
}else if (q[id[i]].type == ) tmp[id[i]] = get(q[id[i]].r) - get(q[id[i]].l - );
}
//清楚标记
for (int i = l; i <= r; i++){
if (q[id[i]].type == && q[id[i]].k >= mid){
int a = q[id[i]].l, b = q[id[i]].r;
add(, a, -);
add(, b + , );
add(, a, -(n - a + ));
add(, b + , (n - (b + ) + ));
}
}
int l1 = , l2 = ;
//q1放右边,q2放左边
for (int i = l; i <= r; i++){
if (q[id[i]].type == ){
//这个要放在右边
if (q[id[i]].cur + tmp[id[i]] > q[id[i]].k - ){
q1[++l1] = id[i];
Ans[q[id[i]].s] = mid;
}else{
q[id[i]].cur += tmp[id[i]];
q2[++l2] = id[i];
}
}else{
if (q[id[i]].k >= mid) q1[++l1] = id[i];
else q2[++l2] = id[i];
}
} for (int i = ; i <= l2; i++) id[i + l - ] = q2[i];
for (int i = ; i <= l1; i++) id[i + l2 + l - ] = q1[i];
solve(l, l + l2 - , L, mid);
solve(l + l2, r, mid + , R);
}
void init(){
memset(c, , sizeof(c));
scanf("%d%d", &n, &m);
cnt = ;//cnt用来记录询问问题个数
Min = INF, Max = -INF;
for (int i = ; i <= m; i++){
int t;
scanf("%d", &t);
if (t == ){//插入操作
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
q[i].type = ;
q[i].l = l; q[i].r = r;
q[i].k = x; q[i].s = ;
q[i].cur = ;
Max = max(Max, x);
Min = min(Min, x);
}else if (t == ){//询问操作
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
q[i].type = ;
q[i].l = l; q[i].r = r;
q[i].k = x; q[i].cur = ;
q[i].s = ++cnt;//注意这里x是第k大
}
}
for (int i = ; i <= m; i++) id[i] = i;
//printf("%d %d\n", Max, Min);
} int main(){
int T; init();
solve(, m, Min, Max + );
for (int i = ; i <= cnt; i++) printf("%d\n", Ans[i]);
return ;
}