Codeforces Round #771 (Div. 2) E Colorful Operations

Colorful Operations

珂朵莉树 + 树状数组 || 线段树

单独维护点当前的值 \(val\) 和 当前颜色的值 \(tag\)

这样就可以分开维护颜色和点的值，把复杂的操作 \(2\) 变成 \(O(1)\)

每次更改 \(i\) 的颜色 a->b 的时候：$val_i = val_i + tag_a - tag_b`

操作 \(3\) 查询 \(i\) 答案的时候：\(ans = val_i + tag_{col_i}\)

操作 \(1\) 覆盖颜色的时候，可以用珂朵莉树去维护，因为颜色的覆盖都是连续的，因此可以顺带用树状数组完成 \(val\) 的更改

时间复杂度为 \(O(qlogn)\)

因为最多也就增加 \(q\) 个区间

线段树的话也基本同上，线段树结点维护两个值，一个是当前的 \(val\)，另一个是当前颜色

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
#define It set<ran>::iterator
vector<ll>tr, tag;
int n, m;

inline int lowbit(int x)
{
    return x & (-x);
}

void add(int x, ll w)
{
    for(int i=x; i<=n; i+=lowbit(i))
        tr[i] += w;
}

void update(int l, int r, ll w)
{
    add(l, w);
    add(r + 1, -w);
}

ll query(int x)
{
    ll ans = 0;
    for(int i=x; i; i-=lowbit(i))
        ans += tr[i];
    return ans;
}

struct ran
{
    int l, r;
    mutable ll w;
    ran(){}
    ran(int _l, int _r, ll _w){l = _l; r = _r; w = _w;}
    bool operator < (const ran& x) const
    {
        return l < x.l;
    }
};

set<ran>st;
It split(int pos)
{
    It now = st.lower_bound(ran(pos, -1, 0));
    if(now != st.end() && now->l == pos) return now;
    now--;
    int l = now->l, r = now->r;
    ll w = now->w;
    st.erase(now);
    st.insert(ran(l, pos - 1, w));
    return st.insert(ran(pos, r, w)).first;
}

void merge_update(int l, int r, int w)
{
    It itr = split(r + 1), itl = split(l);
    for(It it=itl; it!=itr; it++)
        update(it->l, it->r, tag[it->w]);
    st.erase(itl, itr);
    update(l, r, -tag[w]);
    st.insert(ran(l, r, w));
}

ll Query(int x)
{
    It it = st.lower_bound(ran(x, -1, 0));
    if(it == st.end() || it->l != x) it--;
    return tag[it->w] + query(x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    tr.resize(n + 1, 0);
    tag.resize(n + 1, 0);
    st.insert(ran(1, n, 1));
    while(m--)
    {
        string op;
        cin >> op;
        if(op == "Color")
        {
            int l, r, c;
            cin >> l >> r >> c;
            merge_update(l, r, c);
        }
        else if(op == "Add")
        {
            int c, x;
            cin >> c >> x;
            tag[c] += x;
        }
        else
        {
            int i;
            cin >> i;
            cout << Query(i) << "\n";
        }
    }
    return 0;
}