「Luogu P3527」[POI2011]Meteors

给定一个环，每个节点有一个所属国家，k 次事件，每次对 [l, r] 区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值。

Luogu

分析

整体二分

二分的值域是 1 到 k + 1 ，每次都把 1 到 mid 的陨石雨的贡献加进来，用树状数组统计，然后计算对当前询问区间的关系就好了。

代码

卡卡常还是 T 了一个点，吸氧可以过，应该是用了 vector 的原因

#include <bits/stdc++.h>

#define N 300003
#define rg register
#define ll long long
#define lowbit(i) i&-i

using namespace std;

int gi() {
    int x = 0, f = 1; char c = getchar();
    for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return x * f;
}

int n, m, k;
int ans[N];
ll c[N << 1];

vector <int> vec[N];
vector <int> :: iterator it;

struct qaq {
    ll p; int id;
} q[N], q1[N], q2[N];

struct rain {
    int l, r; ll a;
} g[N];

inline void add(int i, ll k) {
    while (i <= 2 * m) {
        c[i] += k;
        i += lowbit(i);
    }
}

inline ll query(int i) {
    rg ll ret = 0;
    while (i) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}

inline void solve(int l, int r, int L, int R) {
    if (l > r || L > R) return;
    if (l == r) {
        for (rg int i = L; i <= R; ++i) ans[q[i].id] = l;
        return;
    }
    rg int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    for (rg int i = l; i <= mid; ++i) add(g[i].l, g[i].a), add(g[i].r + 1, -g[i].a);
    for (rg int i = L; i <= R; ++i) {
        rg ll tmp = 0;
        for (it = vec[q[i].id].begin(); it != vec[q[i].id].end(); ++it) {
            tmp += query(*it) + query(*it + m);
            if (tmp >= q[i].p) break;
        }
        if (tmp >= q[i].p) q1[++cnt1] = q[i];
        else q[i].p -= tmp, q2[++cnt2] = q[i];
    }
    for (rg int i = l; i <= mid; ++i) add(g[i].l, -g[i].a), add(g[i].r + 1, g[i].a);
    for (rg int i = 1; i <= cnt1; ++i) q[L + i - 1] = q1[i];
    for (rg int i = 1; i <= cnt2; ++i) q[L + cnt1 + i - 1] = q2[i];
    solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R);
}

int main() {
    n = gi(), m = gi();
    for (rg int i = 1; i <= m; ++i) vec[gi()].push_back(i);
    for (rg int i = 1; i <= n; ++i) q[i] = (qaq){gi(), i};
    k = gi();
    for (rg int i = 1; i <= k; ++i) {
        g[i] = (rain){gi(), gi(), gi()};
        if (g[i].l > g[i].r) g[i].r += m;
    }
    solve(1, k + 1, 1, n);
    for (rg int i = 1; i <= n; ++i)
        if (ans[i] > k) puts("NIE");
        else printf("%d\n", ans[i]);
    return 0;
}

「Luogu P3527」[POI2011]Meteors

原文：https://www.cnblogs.com/hlw1/p/12269626.html