题解 P3527 【[POI2011]MET-Meteors】

~~在发现此题前，我以为整体二分只能求第K大来着，我还是太菜了~~ 我们先不考虑多组询问，假设只有一组询问 不难发现，答案具有明显的单调性，所以我们考虑二分来做 对于我们二分的值$mid$，我们先假设$l-mid$的雨全部下下来 如果当前的降雨量大于我们所需要的，那么答案大了，否则答案小了，就把所需要的降雨量变为：原本所需要的降雨量$-(l-mid$的降雨量$)$ 那么有多组询问要怎么做呢？ 我们考虑整体二分，我们定义函数solve(l, r, L, R)为我们二分的值为$[l, r]$（也就是单组询问的$l, r$），目前的操作区间为$[L,R]$（如果是单组询问的话就是$[L==R]$） 我们可以将$[L, R]$区间内所有的操作进行分类：分成答案大的和答案小的（见单组二分的分类），将答案小的放在前面（类似于归并排序），将答案大的放在后面，于是我们就可以继续二分递归了 我们假设在$[L, R]$内有$cnt1$个操作比答案小，那么我们递归应该是： solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R); 最后，我们最开始的假设$[l, mid]$的雨全部下下来，可以用树状数组来实现，在每次递归进入下一次的时候，树状数组需要清空，但我们并不需要$memset$，只需要把这一层递归修改的值改回来就行了 ### $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define int long long #define inf 1000000000 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define lb(x) (x)&(-(x)) #define maxn 300005 int n, m, ans[maxn], tr[maxn * 2], T; struct ques { int l, r, a, id; }e[maxn]; struct node { int ned, id; }p[maxn], p1[maxn], p2[maxn]; vector<int> q[maxn]; il void add(int x, int v) { for(re int i = x; i <= 2 * m; i += lb(i)) tr[i] += v; } il int query(int x) { int ans = 0; for(re int i = x; i; i -= lb(i)) ans += tr[i]; return ans; } il int Query(int x) { int ans = 0; for(re int i = 0; i < q[p[x].id].size(); ++ i) { ans += query(q[p[x].id][i]) + query(q[p[x].id][i] + m); if(ans >= p[x].ned) return ans; } return ans; } il void solve(int l, int r, int L, int R) { if(L > R) return; if(l == r) { //如果二分到了终点，显然当前操作区间的答案都等于二分的答案 rep(i, L, R) ans[p[i].id] = l; return; } int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0; //差分，假设[l, mid]的雨全部下下来 rep(i, l, mid) add(e[i].l, e[i].a), add(e[i].r + 1, -e[i].a); //判断哪些答案大了，那些小了 rep(i, L, R) { int temp = Query(i); if(temp >= p[i].ned) p1[++ cnt1] = p[i]; else p[i].ned -= temp, p2[++ cnt2] = p[i]; } //清空树状数组 rep(i, l, mid) add(e[i].l, -e[i].a), add(e[i].r + 1, e[i].a); //归并排序 rep(i, L, L + cnt1 - 1) p[i] = p1[i - L + 1]; rep(i, L + cnt1, R) p[i] = p2[i - L - cnt1 + 1]; //继续二分 solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R); } signed main() { n = read(), m = read(); rep(i, 1, m) q[read()].push_back(i); rep(i, 1, n) p[i].ned = read(), p[i].id = i; T = read(); rep(i, 1, T) { e[i].l = read(), e[i].r = read(), e[i].a = read(), e[i].id = i; if(e[i].r < e[i].l) e[i].r += m; } ++ T, e[T].id = T, e[T].l = 1, e[T].r = 2 * m, e[T].a = inf; solve(1, T, 1, n); rep(i, 1, n) ans[i] == T ? puts("NIE") : printf("%lld\n", ans[i]); return 0; } ```