CF1638E. Colorful operations Kodori tree + differential tree array

The question

Given length is $n$ Sequence , All elements are initially set to $0$. The following three operations are required ：

• Color(l, r, c)： The interval $[l,r]$ Interval coloring is $c$;
• Add(c, x)： Set color to $c$ All elements of $+x$;
• Query(i)： Query the first $i$ The value of the elements .

Ideas

Contains multiple interval assignment operations , First, consider the maintenance sequence coloring of the Kodori tree . First of all, we need to shout （ Fog ）

Kodori is the happiest girl in the world ！！！

First, create a color sequence and initialize it to $0$, And then for each $Color$ The operation of , With the petaly tree assign Operate the violent pushing interval . However, it should be noted that when the interval is leveled, the whole $erase$ fall , It needs to start from iterator_left So let's start walking through iterator_right, Lower the color mark for each section .

Color marking for each point , We maintain a differential tree array , Perform interval addition with differential operation ：

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

Then, when querying a single point, directly getsum You can get the final value of this point .

Then summarize the idea of maintenance ：

First of all, use the... Of the cadoli tree split Operation obtains interval iterator , Then traverse the intervals and place color marks on each interval , Then erase the whole section and replace it with a new one .

Note that after the replacement is completed , You need to perform a color subtraction operation on the entire tree array range , Avoid repetition when the final answer is accumulated ( The final answer is the result of the tree array query + The color mark obtained by query , If a point is marked repeatedly, it will have the consequence of repeated addition ).

Both the Kodori tree and the tree array are directly pulled boards , So some operations are useless …

Accepted Code

#include <bits/stdc++.h>
#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< (const node &a) const {
     return l < a.l; }
    };

    set<node> s;
    using sit = set<node>::iterator;

    inline void init(int l, int r){
     s.insert(node(l, r, 1)); }

    //^ChthollyTree-SetSplit
    sit split(int pos){
    
        sit it = s.lower_bound(node(pos));
        if(it != s.end() && it -> l == pos) return it;
        --it;
        int l = it -> l, r = it -> r, val = it -> val;
        s.erase(it);
        if(l <= pos - 1) s.insert(node(l, pos - 1, val));
        if(r >= 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 <= len; pos += lowbit(pos)) tree[pos] += x;
    }

    inline int getsum(int i, int ans = 0){
    
        for(int pos = i; pos; pos -= lowbit(pos)) ans += tree[pos];
        return ans;
    }

    inline int query(int l, int r){
     return getsum(r) - getsum(l - 1); }
}//BITTemplate

int colcnt[N];

inline void update(int l, int r, int c){
    
    ct::sit itr = ct::split(r + 1), itl = ct::split(l);
    for(auto it = itl; it != itr;){
    
        BIT::update(it -> 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 <= pos && it -> 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 << query(pos) << endl;
        }
    }
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}