珂朵莉树/颜色段均摊

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using db = double;
using ldb = long double;
#define int ll
int n=1e5+1;
struct node{
    int l,r;
    mutable int v;
    node(int a,int b,int c):l(a),r(b),v(c){}
    bool operator <(const node x)const{return l<x.l;}
};
set<node> odt;
map<int,int> mp;
auto split(int x){
    if(x>n) return odt.end();
    auto it=--odt.upper_bound(node(x,0,0));
    if(it->l==x) return it;
    // int l=it->l,r=it->r,v=it->v;
    auto [l,r,v]=(*it);
    odt.erase(it);
    odt.insert(node(l,x-1,v));
    return odt.insert(node(x,r,v)).first;
}
void assign(int l,int r,int v){
    auto itr=split(r+1),itl=split(l);
    odt.erase(itl,itr);//set erase(itl,itr)删除的是[itl,itr)
    odt.insert(node(l,r,v));
    mp[v]+=(r-l+1);
}
void performance(int l,int r,int v){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++){
        auto [L,R,V]=(*it);
        mp[V]-=(R-L+1);
        if(mp[V]==0) mp.erase(V);
    }
    assign(l,r,v);
}
void solve(){
    int q;cin>>q;
    odt.insert(node(0,1e5+1,0));
    mp[0]=(1e5+2);
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        performance(l,r,x);
        cout<<mp.size()<<"\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

例题：牛客周赛95F