题解 P3527 【[POI2011]MET-Meteors】

· · 题解

小蒟蒻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]);
}