题解 P3527 【[POI2011]MET-Meteors】
Juan_feng
2019-08-25 21:54:47
小蒟蒻Jf写水题划水遭到毒瘤怒斥QAQAQ 再也不敢了.jpg
~~题解还是要水一发的~~
## 题是整体二分题， 这里提供一个分块做法qwq
**思路如下：**
对操作（区间加）进行分块， 设每T个操作为一组， 每次加入一组的操作， 在序列上差分一下求出每个位置当前的答案。 然后扫一下所有的国家（国家用vector保存这个国家的每一个位置), 如果这个国家的答案已经被求出来了， 那么直接跳过这个国家； 否则就判断一下这个国家所有位置的答案之和是否大于需求， 如果大于则说明使其达成需求的操作一定在这一组里面（不超过T个）， 这时候倒着扫一下就可以了。
因为每个位置最多只会被倒着扫一次， 没次不会扫超过T个操作， 且一共要做n/T次差分。 所以当T取sqrt(n)时， 总复杂度为m sqrt(n) + n sqrt(m)。
然后就没什么啦qwq，有什么问题可以私信小蒟蒻Jf。
**那么代码如下**：
```
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#define maxn 300010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
#define DFR(i, l, r) for(re int i = l; i >= r; --i)
using namespace std;
int n, m, c, r, t, x, y, z, k;
int sq;
int a[maxn], ned[maxn], bl[maxn], siz[maxn], of[maxn], anss[maxn];
long long qwq[maxn], cha[maxn], res[maxn];
vector<int> ve[maxn];
struct hz {
int l, r, k;
}q[maxn];
int main() {
scanf("%d%d", &n, &m);
FOR(i, 1, m) {
scanf("%d", &t);
ve[t].push_back(i),
++siz[t],
of[i] = t;
}
FOR(i, 1, n)
scanf("%d", &ned[i]);
scanf("%d", &k);
sq = sqrt(k)*2.5; //可调参
FOR(i, 1, (k-1)/sq+1) {
int l = (i-1)*sq+1, r = min(k, i*sq);
FOR(j, l, r) {
scanf("%d%d%d", &q[j].l, &q[j].r, &q[j].k);
if(q[j].l > q[j].r)
qwq[q[j].l] += q[j].k, qwq[m+1] -= q[j].k, qwq[1] += q[j].k, qwq[q[j].r+1] -= q[j].k;
else
qwq[q[j].l] += q[j].k, qwq[q[j].r+1] -= q[j].k;
}
FOR(j, 1, m) {
cha[j] = qwq[j];
cha[j] += cha[j-1];
res[of[j]] += cha[j];
}
FOR(u, 1, n) {
long long pt = res[u];
if(anss[u] || pt < ned[u])
continue;
DFR(j, r, l) {
FOR(xx, 0, siz[u]-1)
if(q[j].l <= q[j].r) {
if(q[j].l <= ve[u][xx] && ve[u][xx] <= q[j].r)
pt -= q[j].k;
}
else
if(q[j].l <= ve[u][xx] || ve[u][xx] <= q[j].r)
pt -= q[j].k;
if(pt < ned[u]) {
anss[u] = j;
break;
}
}
}
memset(res, 0, sizeof(res));
}
FOR(i, 1, n)
if(anss[i] == 0)
puts("NIE");
else
printf("%d\n", anss[i]);
}
```