珂朵莉树

class ChthollyTree {
    std::map<int, /* data to maintain */> mp;

  public:
    void split(int l) {
        // 找出 l 所在的区间
        auto it = std::prev(mp.upper_bound(l));
        // 先复制一遍数据
        mp[l] = it->second;
    }

    // assign [l, r] to /* data */
    void assign(int l, int r, /* data */) {
        split(l), split(r + 1);
        auto it = mp.find(l);
        while (it->first != r + 1) 
            it = mp.erase(it);
        mp[l] = /* data */;
    }

    // Compute the result for [l, r]
    void perform(int l, int r) {
        split(l), split(r+1);
        auto it = mp.find(l);
        while(it->first != r+1) {
            // Do computation ...
            it = std::next(it);
        }
    }
};