P8512 [Ynoi Easy Round 2021] TEST_152

ccxswl · 2023-10-13 15:33:53 · 题解

这题发现在线不好做，考虑离线。一开始想的是回滚莫队加数据结构暴力维护，但复杂度不对。

其实是个套路，把询问离线下来，按 r 排序，从前往后扫。

用树状数组维护每个时刻染的颜色对答案（全局和）的贡献，如果有一个后面的时刻覆盖了它的一部分，就让它的贡献减去相应的值。具体来说，当操作到 x 时刻，全局和就为 bit.ask(x)。

对于查询，就直接用树状数组区间查询即可。

序列操作就用 ODT 维护。

#include <bits/stdc++.h>

using namespace std;

#define int long long

int read() {
    int x;
    cin >> x;
    return x;
}

const int maxN = 5e5 + 7;

int n, m, q;

struct Bit {
    int t[maxN];
    void add(int x, int v) {
        if (!x) return;
        for (; x <= n; x += x & -x)
            t[x] += v;
    }
    int ask(int x) {
        int res = 0;
        for (; x > 0; x -= x & -x)
            res += t[x];
        return res;
    }
} b;

struct node {
    int l, r;
    mutable int v;
    int id;
    node(int l, int r, int v, int id) : l(l), r(r), v(v), id(id) {}
    friend bool operator < (node A, node B) {
        return A.l < B.l;
    }
};
set<node> odt;

auto split(int x) {
    if (x > m) return odt.end();
    auto it = --odt.upper_bound({x, 0, 0, 0});
    if (it->l == x) return it;
    int l = it->l, r = it->r, v = it->v, id = it->id;
    odt.erase(it);
    odt.emplace(l, x - 1, v, id);
    return odt.emplace(x, r, v, id).first;
}
void assign(int l, int r, int v, int id) {
    auto itr = split(r + 1), itl = split(l);
    for (auto tmp = itl; tmp != itr; tmp++)
        b.add(tmp->id, -tmp->v * (tmp->r - tmp->l + 1));
    odt.erase(itl, itr);
    odt.emplace(l, r, v, id);
    b.add(id, v * (r - l + 1));
}
struct modi {
    int l, r, v;
} mo[maxN];

struct ques {
    int l, r, id;
    friend bool operator < (ques A, ques B) {
        return A.r < B.r;
    }
} u[maxN];
int ans[maxN];

signed main() {
    n = read(), m = read(), q = read();
    odt.emplace(1, m, 0, 0);
    for (int i = 1; i <= n; i++)
        mo[i].l = read(), mo[i].r = read(), mo[i].v = read();
    for (int i = 1; i <= q; i++)
        u[i].l = read(), u[i].r = read(), u[i].id = i;
    sort(u + 1, u + q + 1);
    int now = 1;
    for (int i = 1; i <= q; i++) {
        while (now <= u[i].r)
            assign(mo[now].l, mo[now].r, mo[now].v, now), now++;
        ans[u[i].id] = b.ask(u[i].r) - b.ask(u[i].l - 1);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}