P3527 题解
rainygame
·
·
题解
来一篇 O(n\log n) 的题解！
答案具有可二分性，考虑整体二分。设当前分治区间为 [l,r]，任务是判断 Q 集合内的国家答案是否小于等于 m=\dfrac{l+r}{2}。
还有一个更加暴力的做法：将 $[l,m]$ 操作转化成差分数组上的单点加，然后扫一遍整个序列，也可以求出每个太空站的值。这个做法是可以优化的，因为“关键点”个数只有 $O(\sum\limits_{i\in Q}\lvert S_i\rvert+r-l)$（其中 $S_i$ 表示属于国家 $i$ 的空间站集合），所以如果这些点排好序了，那么就可以直接扫一遍，复杂度优化为 $O(n\log n)$！
考虑在第一次分治之前就排好序，那么在后面的分治中，可以将点集有序地分为两部分，复杂度不会退化。
注意事项：
- 计算过程中可能会爆 `long long`。
- 注意有些国家可能没有空间站。
比两只 $\log$ 好写的代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef __int128 _int;
#define MAXN 300005
int n, m, q; int a[MAXN], p[MAXN], ans[MAXN]; _int tp[MAXN];
struct Node{int x, k, id;}; vector<Node> Q;
void sol(int l, int r, vector<Node> Q){
if (l == r){for (auto i: Q) if (!i.k) ans[a[i.x]]=l; return;} int mid((l+r)>>1);
for (_int i(0), res(0); i<Q.size(); ++i){
if (!Q[i].k) tp[a[Q[i].x]] += res; else if (Q[i].id <= mid) res += Q[i].k;
}
vector<Node> ql, qr;
for (auto i: Q){
if (i.k) (i.id <= mid ? ql : qr).push_back(i);
else if (tp[a[i.x]] >= p[a[i.x]]) ql.push_back(i);
else p[a[i.x]] -= tp[a[i.x]], tp[a[i.x]] = 0, qr.push_back(i);
}
for (auto i: Q) tp[a[i.x]] = 0; sol(l, mid, ql); sol(mid+1, r, qr);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> m >> n; for (int i(1); i<=n; ++i) cin >> a[i], Q.push_back({i, 0, 0});
for (int i(1); i<=m; ++i) cin >> p[i]; cin >> q;
for (int i(1), l, r, k; i<=q; ++i){
cin >> l >> r >> k;
if (l <= r) Q.push_back({l, k, i}), Q.push_back({r+1, -k, i});
else Q.push_back({1, k, i}), Q.push_back({r+1, -k, i}), Q.push_back({l, k, i});
}
sort(Q.begin(), Q.end(), [](Node a, Node b){return a.x == b.x ? !a.k < !b.k : a.x < b.x;});
memset(ans, 0x3f, sizeof(ans)); sol(1, q+1, Q);
for (int i(1); i<=m; ++i) if (ans[i] > q) cout << "NIE\n"; else cout << ans[i] << '\n';
return 0;
}
```