[ABC380E] 1D Bucket Tool

考虑使用珂朵莉树。
操作 1，找到 x 所在的颜色段，然后暴力往外扩展，最后像 assign 操作一样，把中间的全删了，插入一个大块。
操作 2 可以在操作 1 的同时维护一个 cnt 数组。
code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define ui unsigned int
#define i128 __int128
#define lid (id << 1)
#define rid (id << 1 | 1)
const int N = 2e5+5;
namespace tianyu{
    int n, q;
    int cnt[500005];
    struct node{
        int l, r;
        mutable int v;
        node(int L, int R, int V) : l(L), r(R), v(V) {}
        inline bool operator <(const node &b)const{return l == b.l ? r < b.r : l < b.l;}
    };set<node>odt;
    inline auto split(int x){
        auto pos = odt.lower_bound({x, 0, 0});
        if (pos != odt.end() && pos->l == x) return pos;
        if ((--pos)->r < x) return odt.end();
        int l = pos->l, r = pos->r, v = pos->v;
        return (odt.erase(pos), odt.insert({l, x - 1, v}), odt.insert({x, r, v})).first;
    }
    inline void update(int x, int c){
        auto pos = prev(odt.upper_bound({x, (int)1e9, 0}));
        auto pl = pos, pr = next(pos);
        int l = pos->l, r = pos->r;
        cnt[pos->v] -= r - l + 1;
        for (;pl != odt.begin() && prev(pl)->v == pos->v;--pl, cnt[pl->v] -= l - pl->l, l = pl->l) ;
        for (;pr != odt.end() && pr->v == pos->v;cnt[pr->v] -= pr->r - r, r = pr->r, ++pr) ;
        odt.erase(pl, pr);odt.insert({l, r, c});cnt[c] += r - l + 1;
    }
    void awa(){
        cin >> n >> q;
        for (int i = 1;i <= n;i++) odt.insert({i, i, i}), ++cnt[i];
        while (q--){
            int op;
            cin >> op;
            if (op == 1){
                int x, c;
                cin >> x >> c;
                update(x, c);
            }
            else{
                int x;
                cin >> x;
                cout << cnt[x] << '\n';
            }
        }
    }
}
signed main(){
    int T = 1;
    while (T--) tianyu::awa();
    return 0;
}