CF1638E. Colorful Operations 珂朵莉树+差分树状数组

题意

给定长度为 n n n的序列，初始所有元素置 0 0 0。要求支持以下三个操作：

• Color(l, r, c)：将区间 [ l , r ] [l, r] [l,r]区间染色为 c c c；
• Add(c, x)：将颜色为 c c c的元素全部 + x +x +x；
• Query(i)：查询第 i i i个元素的值。

思路

含有多次区间赋值区间赋值操作，首先考虑珂朵莉树维护序列染色。那么首先需要大喊（雾）

珂朵莉是世界上最幸福的女孩！！！

首先建立颜色序列并初始化为 0 0 0，然后对于每个 C o l o r Color Color的操作，用珂朵莉树的assign操作暴力推平区间。但是注意在推平区间的时候不能直接整个 e r a s e erase erase掉，而是需要从iterator_left开始遍历到iterator_right，对每个区间进行颜色标记的下放操作。

对于每个点的颜色标记，我们维护一个差分树状数组，用差分操作进行区间加：

add(l, x), add(r, -x);

然后查询单点的时候直接getsum就可以得到该点最终的值。

那么总结一下维护的思路：

首先用珂朵莉树的split操作获得区间迭代器，然后遍历区间对每个区间下放颜色标记，然后擦除整个区间用新区间替换。

注意替换完成后，需要对整个树状数组区间执行一次减颜色的操作，避免最终答案累加的时候产生重复(最终答案为树状数组查询的结果+查询得到的颜色标记，如果一个点被反复标记则会产生重复加的后果)。

珂朵莉树和树状数组都是直接拉的板子，所以有一些操作没用…

Accepted Code

#include 
#define int long long
using namespace std;

const int N = 1e6 + 10;

namespace ct{
    struct node{
        int l, r;
        mutable int val;
        node (int lpos): l(lpos) {}
        node (int lpos, int rpos, int vall): l(lpos), r(rpos), val(vall) {}
        bool operator l, r = it -> r, val = it -> val;
        s.erase(it);
        if(l = pos) return s.insert(node(pos, r, val)).first;
        return s.end();
    }

    //^ChthollyTree-PartValueAssign
    void assign(int l, int r, int val){
        sit itr = split(r + 1), itl = split(l);
        s.erase(itl, itr);
        s.insert(node(l, r, val));
    }

    //^ChthollyTree-PartValueAddition
    void add(int l, int r, int val){
        sit itr = split(r + 1), itl = split(l);
        //for(auto it = itl; it != itr; it++) it -> val += val;
        while(itl != itr) itl -> val += val, itl++;
    }

    //^ChthollyTree-SinglePointQuery
    int query(int pos){
        auto it = s.lower_bound(pos);
        --it;
        return it -> val;
    }
}//ChthollyTreeTemplate


namespace BIT{
    int tree[N], len;
    #define lowbit(x) ((x) & (-x))

    inline void init(int n){ len = n; }

    inline void update(int i, int x){
        for(int pos = i; pos  r + 1, -colcnt[it -> val]);
        BIT::update(it -> l, colcnt[it -> val]);
        auto nxt = next(it);
        ct::s.erase(it);
        it = nxt;
    }
    ct::s.insert(ct::node(l, r, c));
    BIT::update(r + 1, colcnt[c]);
    BIT::update(l, -colcnt[c]);
}

inline int query(int pos, int res = 0){
    res = BIT::getsum(pos);
    auto it = ct::s.upper_bound(pos);
    if(it != ct::s.begin()){
        it = prev(it);
        if(it -> l  r >= pos) res += colcnt[it -> val];
    }
    return res;
}

inline void solve(){
    int n, q; cin >> n >> q;
    memset(colcnt, 0, sizeof(colcnt));
    BIT::init(n);
    ct::init(1, n);
    while(q--){
        string operation; cin >> operation;
        if(operation[0] == 'C'){
            int l, r, c; cin >> l >> r >> c;
            update(l, r, c);
        }
        else if(operation[0] == 'A'){
            int color, cnt; cin >> color >> cnt;
            colcnt[color] += cnt;
        }
        else if(operation[0] == 'Q'){
            int pos = 0; cin >> pos;
            cout