珂朵莉树+树状数组T#19求助神犇
查看原帖
珂朵莉树+树状数组T#19求助神犇
610557
shinzanmonoszm 妹妹楼主2022/9/4 10:19
#include <bits/stdc++.h>
#define iter set<node>::iterator
#define lowbit(x) ((x) & -(x))
using namespace std;
using ll = long long;
struct node {
    ll l, r;
    mutable ll color;
    bool operator<(const node &a) const {
        return l < a.l;
    }
};
int val[1000010];
set<node> odt;
ll n, q;
void build() {
    odt.insert(node{1, n, 1});
}
iter split(int x) {
    if (x > n) return odt.end();
    iter it = --odt.upper_bound(node{x, 0, 0});
    if (it -> l == x) return it;
    ll l = it -> l, r = it -> r, color = it -> color;
    odt.erase(it);
    odt.insert(node{l, x - 1, color});
    return odt.insert(node{x, r, color}).first;
}
void assign(int l, int r, int c) {
    iter itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(node{l, r, c});
}
struct BIT {
    ll tree1[1000010], tree2[1000010];
    void add(ll id, ll val) {
        for (ll i = id; i <= n; i += lowbit(i))
            tree2[i] += id * val, tree1[i] += val;
    }
    ll query(ll id) {
        ll ans = 0;
        for (ll i = id; i; i -= lowbit(i)) ans += (id + 1) * tree1[i] - tree2[i];
        return ans;
    }
} bit;
void add(ll c, ll x) {
    for (node i: odt)
        if (i.color == c)
            bit.add(i.l, x), bit.add(i.r + 1, -x);
}
void query(ll x) {
    cout << bit.query(x) - bit.query(x - 1) << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> q;
    build();
    while (q--) {
        string op;
        int l, r, c, x;
        cin >> op;
        if (op == "Color")
            cin >> l >> r >> c, assign(l, r, c);
        else if (op == "Add")
            cin >> c >> x, add(c, x);
        else if (op == "Query")
            cin >> x, query(x);
    }
    return 0;
}
2022/9/4 10:19
加载中...