BZOJ2527【POI2011】Meteors <整体二分>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

【POI2011】Meteors

Time  Limit:  60  Sec\mathrm{Time\;Limit:\;60\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

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

Input

第一行输入两个数N,MN,M。
第二行有MM个数，第ii个数OiO_i表示第ii段轨道上有第OiO_i个国家的太空站。
第三行有NN个数，第ii个数PiP_i表示第ii个国家希望收集的陨石数量。
第四行有一个数KK，表示预测了接下来的KK场陨石雨。
接下来KK行，每行有三个数Li,Ri,AiL_i,R_i,A_i，表示第KK场陨石雨的发生地点在从LiL_i顺时针到RiR_i的区间中（如果Li≤RiL_i\le R_i，就是Li,Li+1,⋯ ,RiL_i,L_i+1,\cdots,R_i，否则就是Ri,Ri+1,⋯ ,m−1,m,1,⋯ ,LiR_i,R_i+1,\cdots,m-1,m,1,\cdots,L_i），向区间中的每个太空站提供AiA_i单位的陨石样本。

Output

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

Sample Input

1
2
3
4
5
6
7
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

Sample Output

1
2
3
3
NIE
1

HINT

1≤n,m,k≤3×1051\le n,m,k\le3\times10^5，1≤Pi≤1091\le P_i\le10^9，1≤Ai<1091\le A_i<10^9。

Source

鸣谢Object022

标签：整体二分

Solution

整体二分模板题。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}