BZOJ2527【POI2011】Meteors <整体二分>

Problem

【POI2011】Meteors

Description

有个成员国。
现在它发现了一颗新的星球，这颗星球的轨道被分为份（第份和第份相邻），第份上有第个国家的太空站。
这个星球经常会下陨石雨。已经预测了接下来场陨石雨的情况。的第个成员国希望能够收集单位的陨石样本。
你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

Input

第一行输入两个数。
第二行有个数，第个数表示第段轨道上有第个国家的太空站。
第三行有个数，第个数表示第个国家希望收集的陨石数量。
第四行有一个数，表示预测了接下来的场陨石雨。
接下来行，每行有三个数，表示第场陨石雨的发生地点在从顺时针到的区间中（如果，就是，否则就是），向区间中的每个太空站提供单位的陨石样本。

Output

输出共行。
第行的数表示第个国家在第波陨石雨之后能够收集到足够的陨石样本。
如果到第波结束后仍然收集不到，输出NIE。

Sample Input

Sample Output

1
2
3

3
NIE
1

HINT

，，。

Source

鸣谢Object022

标签：整体二分

Solution

整体二分模板题。

将所有询问离线下来一起做二分答案。对于二分中点，考虑每个国家是否能在前波流星雨之内达到收集要求。对每个国家用树状数组统计出会有多少陨石落到它的所有卫星上，即可判断每个询问的答案在中还是中。
注意每次判的时候不要将区间内的所有流星雨都加入树状数组修改，这样复杂度是伪的。应当对于每个答案区间在中的询问累加前面的陨石总数，即累加前面区间对后面的贡献。

Code

#include <bits/stdc++.h>
#define MAX_N 20000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int N, M, Q, cnt, val[MAX_N+5], ans[MAX_N+5];
struct node {int id, tp, a, b, k, s;} p[MAX_N+5], q[MAX_N+5];
int num[MAX_N+5], tr[MAX_N+5]; bool mrk[MAX_N+5];
void inc(int p) {for (; p <= N; p += (p&-p)) tr[p]++;}
void dec(int p) {for (; p <= N; p += (p&-p)) tr[p]--;}
int sum(int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
void bi_solve(int l, int r, int s, int t) {
    if (l > r) return;
    if (s == t) {
        for (int i = l; i <= r; i++)
            if (p[i].tp == 3) ans[p[i].id] = s;
        return;
    }
    for (int i = l; i <= r; i++)
        if (p[i].tp == 1 && p[i].b <= mid) inc(p[i].a);
        else if (p[i].tp == 2 && p[i].b <= mid) dec(p[i].a);
        else if (p[i].tp == 3) num[i] = sum(p[i].b)-sum(p[i].a-1);
    for (int i = l; i <= r; i++)
        if (p[i].tp == 1 && p[i].b <= mid) dec(p[i].a);
        else if (p[i].tp == 2 && p[i].b <= mid) inc(p[i].a);
    int lsz = 0;
    for (int i = l; i <= r; i++)
        if (p[i].tp == 3) {
            if (p[i].k <= p[i].s+num[i]) lsz++, mrk[i] = false;
            else p[i].s += num[i], mrk[i] = true;
        } else lsz += (p[i].b <= mid), mrk[i] = (p[i].b > mid);
    for (int i = l, p1 = l, p2 = l+lsz; i <= r; i++)
        if (!mrk[i]) q[p1++] = p[i]; else q[p2++] = p[i];
    for (int i = l; i <= r; i++) p[i] = q[i];
    bi_solve(l, l+lsz-1, s, mid), bi_solve(l+lsz, r, mid+1, t);
}
int main() {
    read(N), read(M);
    for (int i = 1; i <= N; i++)
        read(val[i]), p[++cnt] = (node){0, 1, i, val[i], 0, 0};
    for (int i = 1, a, b, k; i <= M; i++) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'C')
            read(a), read(b), 
            p[++cnt] = (node){0, 2, a, val[a], 0, 0}, 
            p[++cnt] = (node){0, 1, a, (val[a] = b), 0, 0};
        else
            read(a), read(b), read(k), 
            p[++cnt] = (node){++Q, 3, a, b, k, 0};
    }
    bi_solve(1, cnt, 0, INF);
    for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
    return 0;
}