ODT学习笔记：E - Colorful Operations(Codeforces division 2 # 771)

原题链接
ODT(Old Driver Tree),又名珂朵莉树（Chtholly Tree），是一种维护区间覆盖信息的数据结构，常见的维护手法是通过利用STLmap或者set来存储每个区间的左右端点。
今天在codeforces上找到了一题合适的题目来学习ODT。

对与一个序列，进行以下操作。

• 修改区间(l,r)的颜色标记为c。
• 将当前颜色为c的所有元素加x。
• 询问第i个元素 a i a_i ai​ 的值
  数据规模为1e6级别，初始所有元素为0，颜色标记为1。

本题可以使用线段树来解决，这里主要介绍使用ODT + 树状数组来解决这个问题。

ODT主要用来维护区间覆盖的相关的操作。本题的涂色操作相当于将区间进行了覆盖。
mapODT 中主要维护了区间的左右节点以及区间的一些基本信息。当我们需要对区间 ( l , r ) (l,r) (l,r) 进行覆盖时，首先通过lower_bound找到 l , r l,r l,r 这两个端点当前被哪个区间包含，然后将这两个区间（ [ L 1 , R 1 ] , [ L 2 , R 2 ] [L_1,R_1],[L_2,R_2] [L1​,R1​],[L2​,R2​]）分别以 l l l 和 r r r 为界，一分为二。得到区间 [ L 1 , l − 1 ] , [ l , R 1 ] , [ L 2 , r ] , [ r + 1 , R 2 ] [L_1,l -1],[l,R_1],[L_2,r],[r+1,R_2] [L1​,l−1],[l,R1​],[L2​,r],[r+1,R2​]。
然后再遍历 [ l , r ] [l,r] [l,r] 中的区间，将这些区间删除，插入区间 [ l , r ] [l,r] [l,r] 。

namespace ODT{
    struct Node{;
        int r, val, color;
    };
    map odt;
    void split(int x) {
        if (x == 0) return;
        auto it = prev(odt.upper_bound(x));
        
        if (it -> second.r <= x) {return;}
        int ll = it -> first;  
        Node tmp = it -> second;
        odt.erase(it);
        odt[ll] = {x,tmp.val, tmp.color};
        odt[x + 1] = tmp;

    }
    void assign(int l, int r, int x) {
        split(l - 1);//  注意左端点是以 l - 1 为界
        split(r);
        auto itl = odt.lower_bound(l);
        auto itr = odt.upper_bound(r);
        for (auto it = itl; it != itr; it ++) {
			
        }
        for (auto it = itl; it != odt.end();) {
            if (it -> second.r > r) break;
            it = odt.erase(it);
        }
        odt[l] = {r, - color[x], x};
    }
}

这里的split() 函数的作用就是将包含左右节点的区间进行一分为二。
assign()的作用就是对区间 ( l , r ) (l,r) (l,r) 进行覆盖，我们也可以在删除原有区间的同时，对原有的区间进行一些操作。
ODT的每次覆盖操作，如果访问的区间超过了2个，那么必然会删掉一些区间，使得区间总数减少（比如一次覆盖操作访问了4个区间，那么区间总数必然减少 x >=2），所以ODT的时间复杂度大约为 O ( N × l o g N ) O(Ntimes log_N) O(N×logN​)

首先，我们使用一个数组 C o l o r i Color_i Colori​ 来记录Add操作对于颜色 i i i 一共加了多少值。当一个区间被覆盖为颜色 i i i 时，我们记录下当时这种颜色的 C o l o r i ′ = C o l o r i Color_i' = Color_i Colori′​=Colori​ , 当这个区间被覆盖成其他颜色时，记录下此时的 C o l o r i Color_i Colori​,这段时间内，Add操作对这段区间的所有元素产生的值的贡献是 C o l o r i − C o l o r i ′ Color_i - Color_i' Colori​−Colori′​ 。通过树状数组对这些元素进行区间加操作即可。
当查询一个元素的值时，需要先单点查询树状数组对应元素的值，然后再加上元素当前所在区间产生的贡献（当前区间还未被删除，所以贡献还没有加到树状数组中）。

参考代码：

#include 
using namespace std;
#define int long long 
#define _D if(Debug == 1)
const int N = 1e6 + 10;
const int Debug = 0;
int n, q;
int color[N];

namespace BIT{
    int c[N];
    void inst(int x, int val) {
        for (int i = x; i <= n; i += (i & -i)) {
            c[i] += val;
        }
    }
    int query(int x) {
        int sum = 0;
        for (int i = x; i;i -= (i & -i)) {
            sum += c[i];
        }
        return sum;
    }

}

namespace ODT{
    using namespace BIT;
    struct Node{;
        int r, val, color;
    };
    map odt;
    void split(int x) {
        if (x == 0) return;
        auto it = prev(odt.upper_bound(x));
        
        if (it -> second.r <= x) {return;}
        int ll = it -> first;  
        Node tmp = it -> second;
        odt.erase(it);
        odt[ll] = {x,tmp.val, tmp.color};
        odt[x + 1] = tmp;

    }
    void assign(int l, int r, int x) {
        split(l - 1);
        split(r);
        auto itl = odt.lower_bound(l);
        auto itr = odt.upper_bound(r);
        for (auto it = itl; it != itr; it ++) {
            
            BIT::inst(it -> first, it-> second.val + color[it -> second.color]);
            BIT::inst(it -> second.r + 1, - it-> second.val -  color[it -> second.color]);
        }
        for (auto it = itl; it != odt.end();) {
            if (it -> second.r > r) break;
            it = odt.erase(it);
        }
        odt[l] = {r, - color[x], x};
    }
    int get_ans(int x) {
        auto it = prev(odt.upper_bound(x));
        return BIT::query(x) + color[it -> second.color] + it -> second.val;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin >> n >> q;
    ODT::odt[1] = {n, 0, 1};
    for (int i = 1; i <= q; i ++) {
        string opt;
        cin >> opt;
        if (opt == "Color") {
            int l, r, x;
            cin >> l >> r >> x;
            ODT::assign(l, r, x);
        } else if (opt == "Add") {
            int co, x;
            cin >> co >> x;
            color[co] += x;
        } else {
            int x;
            cin >> x;
            cout << ODT::get_ans(x) << 'n';
        }
    }
}