题解：P13983 数列分块入门 8

headless_piston · 2025-09-06 16:24:52 · 题解

珂朵莉树是很棒的数据结构！
观察题目，发现每次询问后必须进行一次区间推平操作，这启示我们用珂朵莉树做这道题。
代码实现非常简单，拆分出区间后直接暴力遍历颜色段并累加贡献即可。

接下来进行复杂度分析：
设势能函数 \Phi 表示当前 ODT 中颜色段个数。显然初始势能 \Phi=n。

• split：每次最多新增 1 个颜色段。

• assign：两次 split 操作最多增加 2 个颜色段。设操作的区间 [l,r] 中有 k 个颜色段，那么操作将删去 k 个区间然后增加 1 个区间。

综上，对于一次 assign 操作有 \Delta\Phi=2-(k-1)=3-k。

那么，对于这 n 次操作，总体势能变化为：

由于区间数量显然是正数，所以有：

回顾 assign 操作，设当前颜色段数为 m，两次 split 操作时间复杂度 O(\log m)，遍历 k 个颜色段时间复杂度 O(k)，删除 k 个颜色段时间复杂度 O(k\log m)，插入 1 个新颜色段复杂度 O(\log m)，所以单次操作时间复杂度 O(k\log m)。

根据前文，\sum_{i=1}^n k_i<4n，m 不可能大于 n。所以 \sum_{i=1}^n k_i 和 m 都是 O(n) 的。所以总时间复杂度就是：

空间复杂度显然是线性。

关于时间复杂度的感性理解：我们发现每次操作若 k 很大，就会导致颜色段数急剧减少。而 k 极小时又不会产生过多的颜色段。所以给人的感觉就非常正确。

Code：

#include<cstdio>
#include<set>
using namespace std;
template<typename T>
inline void read(T &x);
template<typename T,typename...Args>
void read(T &x,Args &...args);
struct node{
    int l,r,val;
    bool operator<(const node &x)const{
        return l<x.l;
    }
};
int n;
set<node> odt;
auto split(int pos){
    if(pos>n) return odt.end();
    auto it=odt.lower_bound({pos});
    if(it!=odt.end()&&it->l==pos)
        return it;
    it--;
    int l=it->l,r=it->r,val=it->val;
    odt.erase(it);
    odt.insert({l,pos-1,val});
    return odt.insert({pos,r,val}).first;
}
int assign(int l,int r,int c){
    int res=0;
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++)
        if(it->val==c) res+=it->r-it->l+1;
    odt.erase(itl,itr);
    odt.insert({l,r,c});
    return res;
}
int main(){
    read(n);
    for(int i=1,a;i<=n;i++)
        read(a),odt.insert({i,i,a});
    for(int i=1,l,r,c;i<=n;i++){
        read(l,r,c);
        printf("%d\n",assign(l,r,c));
    }
    return 0;
}