Description
Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。
第一行是两个数N,M。
第二行有M个数，第i个数Oi表示第i段轨道上有第Oi个国家的太空站。
第三行有N个数，第i个数Pi表示第i个国家希望收集的陨石数量。
第四行有一个数K，表示BIU预测了接下来的K场陨石雨。
接下来K行，每行有三个数Li,Ri,Ai，表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中（如果Li<=Ri，就是Li,Li+1,…,Ri，否则就是Ri,Ri+1,…,m-1,m,1,…,Li），向区间中的每个太空站提供Ai单位的陨石样本。
Output
N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到，输出NIE。
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
Hint
1<=n,m,k<=3*10^5
1<=Pi<=10^9
1<=Ai<10^9
Solution
首先考虑暴力。我们先枚举每个国家，然后二分波数，check时枚举波数，每次模拟[l,r]区间。但这样子的复杂度是不能接受的。
我们能不能改进一下暴力呢？
考虑改进这个暴力，因为许多国家二分的时候[l,r]区间都是一样的。从这个角度我们用整体二分的思想去优化，也就是说一次二分不仅仅解决一个国家的问题，而是解决多个国家的问题。这样就能把枚举国家的那一维复杂度降下来。
那么这时候复杂度还是不能接受的，因为check过程枚举波数和[l,r]区间是N^2的复杂度。怎么优化呢？
让我们看看check干了什么事。
显然check计算出了状态为mid时每个空间站上降落的陨石个数。从这个角度我们去考虑如何优化check。
首先注意到每次降落陨石都是一个区间，于是想到了差分来维护。例如[l,r]这个区间降落K的陨石，那么差分数组A的变化是：如果l<=r，A[l]+=K,A[r+1]-=K；如果l>r，A[1]+=K, A[r+1]-=K, A[l]+=K。询问相当于求差分数组的前缀和。
维护这个差分数组可以用树状数组来维护，既可以快速修改又可以快速查询。
那么怎么才能达到我们想要的状态mid呢？
可持久化线段树？MLE！
可持久化线段树的确是个不错的选择，对于每一波陨石雨都搞出来一颗新线段树。查询直接在第mid个根节点上查询即可。但是这样做空间复杂度比较大。PoPoQQQ神犇表示自己开到1500W的数组依然过不了。。。
因为时间是有序的，我们可以用一个指针ptr记录当前树状数组中有第1~ptr波陨石雨。求状态mid的时候我们左右移动ptr，然后在树状数组里面修改即可。
您可能会问：那么这样做复杂度能不能保证呢？
——别急我们来试一试。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <cstdio>
int ans = 0, ptr = 0, n = 300000;
void F(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
while (ptr < mid) ++ptr, ++ans;
while (ptr > mid) ptr--, ++ans;
F(l, mid);
F(mid + 1, r);
}
int main() {
F(1, n);
printf("%d %d", n, ans);
return 0;
}
|
输出：300000 2872511
而2872511≈10^6.458，也就是说这个复杂度是可以接受的。我们尝试打表、描点连线，发现：
貌似N和ans是线性关系！尝试用回归直线计算这条直线方程，得到ans≈9.75394N-65974.7。
当然是约等于啦。。。
那么总复杂度貌似就是NlogKlogM的吧
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| #include <cstdio>
typedef long long LL;
const LL LINF = ~0ull >> 2;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
int ptr = 0;
const int maxn = 300005;
int M, N, L[maxn], R[maxn], O[maxn], ans[maxn], I[maxn], J[maxn];
LL A[maxn], C[maxn], P[maxn];
int to[maxn], next[maxn], H[maxn], cnte = 1;
inline int lb(int x) { return x & (-x); }
void modify(int pos, LL val) {
for (int i = pos; i <= M; i += lb(i)) C[i] += val;
}
void ins(int pos) {
if (L[pos] <= R[pos]) {
modify(L[pos], A[pos]);
modify(R[pos] + 1, -A[pos]);
} else {
modify(1, A[pos]);
modify(R[pos] + 1, -A[pos]);
modify(L[pos], A[pos]);
}
}
void del(int pos) {
if (L[pos] <= R[pos]) {
modify(L[pos], -A[pos]);
modify(R[pos] + 1, A[pos]);
} else {
modify(1, -A[pos]);
modify(R[pos] + 1, A[pos]);
modify(L[pos], -A[pos]);
}
}
LL ask(int pos) {
LL ret = 0;
for (int i = pos; i; i -= lb(i)) ret += C[i];
return ret;
}
void insE(int x, int y) {
to[++cnte] = y;
next[cnte] = H[x];
H[x] = cnte;
}
void solve(int h, int t, int l, int r) {
if (h > t) return;
if (l == r) {
for (int i = h; i <= t; ++i) ans[I[i]] = l;
return;
}
int mid = (l + r) >> 1;
while (ptr < mid) ins(++ptr);
while (ptr > mid) del(ptr--);
int p1 = h, p2 = t, now;
for (int p = h; p <= t; ++p) {
now = I[p];
LL tmp = 0;
for (int i = H[now]; i; i = next[i]) {
tmp += ask(to[i]);
if (tmp >= P[now]) break;
}
if (tmp >= P[now]) J[p1++] = now;
else J[p2--] = now;
}
for (int i = h; i <= t; ++i) I[i] = J[i];
solve(h, p1 - 1, l, mid);
solve(p2 + 1, t, mid + 1, r);
}
int main() {
N = getint(); M = getint();
for (int i = 1; i <= M; ++i) {
O[i] = getint();
insE(O[i], i);
}
for (int i = 1; i <= N; ++i) P[i] = getint();
int K = getint();
for (int i = 1; i <= K; ++i) {
L[i] = getint();
R[i] = getint();
A[i] = getint();
}
L[K + 1] = 1;
R[K + 1] = M;
A[K + 1] = LINF;
for (int i = 1; i <= N; ++i) I[i] = i;
solve(1, N, 1, K + 1);
for (int i = 1; i <= N; ++i) {
if (ans[i] == K + 1) puts("NIE");
else printf("%d\n", ans[i]);
}
return 0;
}
|