http://www.lydsy.com/JudgeOnline/problem.php?id=3110
题意：……
思路：其实和之前POJ那道题差不多，只不过是换成区间更新，而且是第k大不是第k小，第k大是降序的第k个，在二分询问的时候需要注意和第k小的不同细节。
树状数组比线段树快了几倍，所以说树状数组区间更新区间查询是一个值得学的姿势啊。
看了一下别人的，可以把插入时候的值换成n - x + 1，那么就可以变成找第k小了，输出的时候还要换回来。
线段树：
//9028 kb 7484 ms
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50010
#define lson rt<<1, l, m
#define rson rt<<1|1, m + 1, r
typedef long long LL;
struct P {
int type, l, r, id; LL val;
P () {}
P (int type, int l, int r, LL val, int id) : type(type), l(l), r(r), val(val), id(id) {}
} q[N], lq[N], rq[N], qq[N];
LL tree[N<<], lazy[N<<], ans[N];
int n; void pushup(int rt) { tree[rt] = tree[rt<<|] + tree[rt<<]; } void pushdown(int rt, int len) {
if(lazy[rt]) {
lazy[rt<<] += lazy[rt]; lazy[rt<<|] += lazy[rt];
tree[rt<<] += lazy[rt] * (len - (len >> )); tree[rt<<|] += lazy[rt] * (len >> );
lazy[rt] = ;
}
} void update(int rt, int l, int r, int L, int R, int val) {
if(L <= l && r <= R) {
tree[rt] += (r - l + ) * val; // 居然漏了+1
lazy[rt] += val; return ;
}
pushdown(rt, r - l + );
int m = (l + r) >> ;
if(L <= m) update(lson, L, R, val);
if(m < R) update(rson, L, R, val);
pushup(rt);
} LL query(int rt, int l, int r, int L, int R) {
if(L <= l && r <= R) return tree[rt];
pushdown(rt, r - l + );
int m = (l + r) >> ;
LL ans = ;
if(L <= m) ans += query(lson, L, R);
if(m < R) ans += query(rson, L, R);
return ans;
} void Solve(int l, int r, int lask, int rask) {
if(rask < lask || r < l) return ;
if(l == r) { for(int i = lask; i <= rask; i++) if(q[i].type == ) ans[q[i].id] = l; return ; }
int mid = (l + r) >> , lcnt = , rcnt = ;
for(int i = lask; i <= rask; i++) {
if(q[i].type == ) {
if(mid >= q[i].val) { // 第k大 = 降序第k个,只更新比当前二分的答案大的
lq[++lcnt] = q[i];
} else {
rq[++rcnt] = q[i];
update(, , n, q[i].l, q[i].r, );
}
} else {
LL num = query(, , n, q[i].l, q[i].r);
if(num >= q[i].val) rq[++rcnt] = q[i];
else {
q[i].val -= num;
lq[++lcnt] = q[i];
}
}
}
for(int i = lask; i <= rask; i++) if(q[i].type == && mid < q[i].val) update(, , n, q[i].l, q[i].r, -);
for(int i = ; i <= lcnt; i++) q[i+lask-] = lq[i];
for(int i = ; i <= rcnt; i++) q[i+lask+lcnt-] = rq[i];
Solve(l, mid, lask, lask + lcnt - );
Solve(mid + , r, lask + lcnt, rask);
} int main() {
int m, a, b, c, d, ins = , ask = ;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
scanf("%d%d%d%d", &a, &b, &c, &d);
if(a == ) q[i] = P(a, b, c, d, ++ins);
else q[i] = P(a, b, c, d, ++ask);
}
Solve(, n, , m);
for(int i = ; i <= ask; i++)
printf("%lld\n", ans[i]);
return ;
}
树状数组：
//1828ms 6.7MB
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50010
#define lson rt<<1, l, m
#define rson rt<<1|1, m + 1, r
typedef long long LL;
struct P {
int type, l, r, id; LL val;
P () {}
P (int type, int l, int r, LL val, int id) : type(type), l(l), r(r), val(val), id(id) {}
} q[N], lq[N], rq[N], qq[N];
LL bit[][N], ans[N];
int n; int lowbit(int x) { return x & (-x); }
void Add(int i, int x, int w) { while(x <= n) bit[i][x] += w, x += lowbit(x); }
LL Sum(int i, int x) { LL ans = ; while(x) ans += bit[i][x], x -= lowbit(x); return ans; }
void update(int l, int r, int w) {
Add(, l, w); Add(, r + , -w); Add(, l, w * l); Add(, r + , -w * (r + ));
}
LL query(int l, int r) {
LL lsum = Sum(, l - ) * l - Sum(, l - );
LL rsum = Sum(, r) * (r + ) - Sum(, r);
return rsum - lsum;
} void Solve(int l, int r, int lask, int rask) {
if(rask < lask || r < l) return ;
if(l == r) { for(int i = lask; i <= rask; i++) if(q[i].type == ) ans[q[i].id] = l; return ; }
int mid = (l + r) >> , lcnt = , rcnt = ;
for(int i = lask; i <= rask; i++) {
if(q[i].type == ) {
if(mid >= q[i].val) { // 第k大 = 降序第k个,只更新比当前二分的答案大的
lq[++lcnt] = q[i];
} else {
rq[++rcnt] = q[i];
update(q[i].l, q[i].r, );
}
} else {
LL num = query(q[i].l, q[i].r);
if(num >= q[i].val) rq[++rcnt] = q[i];
else {
q[i].val -= num;
lq[++lcnt] = q[i];
}
}
}
for(int i = lask; i <= rask; i++) if(q[i].type == && mid < q[i].val) update(q[i].l, q[i].r, -);
for(int i = ; i <= lcnt; i++) q[i+lask-] = lq[i];
for(int i = ; i <= rcnt; i++) q[i+lask+lcnt-] = rq[i];
Solve(l, mid, lask, lask + lcnt - );
Solve(mid + , r, lask + lcnt, rask);
} int main() {
int m, a, b, c, d, ins = , ask = ;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
scanf("%d%d%d%d", &a, &b, &c, &d);
if(a == ) q[i] = P(a, b, c, d, ++ins);
else q[i] = P(a, b, c, d, ++ask);
}
Solve(, n, , m);
for(int i = ; i <= ask; i++)
printf("%lld\n", ans[i]);
return ;
}
第k小：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50010
#define lson rt<<1, l, m
#define rson rt<<1|1, m + 1, r
typedef long long LL;
struct P {
int type, l, r, id; LL val;
P () {}
P (int type, int l, int r, LL val, int id) : type(type), l(l), r(r), val(val), id(id) {}
} q[N], lq[N], rq[N], qq[N];
LL bit[][N], ans[N];
int n; int lowbit(int x) { return x & (-x); }
void Add(int i, int x, int w) { while(x <= n) bit[i][x] += w, x += lowbit(x); }
LL Sum(int i, int x) { LL ans = ; while(x) ans += bit[i][x], x -= lowbit(x); return ans; }
void update(int l, int r, int w) {
Add(, l, w); Add(, r + , -w); Add(, l, w * l); Add(, r + , -w * (r + ));
}
LL query(int l, int r) {
LL lsum = Sum(, l - ) * l - Sum(, l - );
LL rsum = Sum(, r) * (r + ) - Sum(, r);
return rsum - lsum;
} void Solve(int l, int r, int lask, int rask) {
if(rask < lask || r < l) return ;
if(l == r) { for(int i = lask; i <= rask; i++) if(q[i].type == ) ans[q[i].id] = l; return ; }
int mid = (l + r) >> , lcnt = , rcnt = ;
for(int i = lask; i <= rask; i++) {
if(q[i].type == ) {
if(mid >= q[i].val) { // 第k大 = 降序第k个,只更新比当前二分的答案大的
lq[++lcnt] = q[i];
update(q[i].l, q[i].r, );
} else {
rq[++rcnt] = q[i];
}
} else {
LL num = query(q[i].l, q[i].r);
if(num >= q[i].val) lq[++lcnt] = q[i];
else {
q[i].val -= num;
rq[++rcnt] = q[i];
}
}
}
for(int i = lask; i <= rask; i++) if(q[i].type == && mid >= q[i].val) update(q[i].l, q[i].r, -);
for(int i = ; i <= lcnt; i++) q[i+lask-] = lq[i];
for(int i = ; i <= rcnt; i++) q[i+lask+lcnt-] = rq[i];
Solve(l, mid, lask, lask + lcnt - );
Solve(mid + , r, lask + lcnt, rask);
} int main() {
int m, a, b, c, d, ins = , ask = ;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
scanf("%d%d%d%d", &a, &b, &c, &d);
if(a == ) q[i] = P(a, b, c, n - d + , ++ins);
else q[i] = P(a, b, c, d, ++ask);
}
Solve(, * n + , , m);
for(int i = ; i <= ask; i++)
printf("%lld\n", n - ans[i] + );
return ;
}