题解：P13983 数列分块入门 8

Swordmaker · 2025-09-06 15:08:27 · 题解

P13983 数列分块入门 8

注意：本题解不是分块做法！！！

思路

题意很简单：每次对一段区间先查询后推平。

众所周知这是一道分块题，但由于我不想用分块，所以我们可以使用一种能快速维护连续段的做法——

没错，就是珂朵莉树。

不会珂朵莉树的请去模板题进行学习。

现在假设你已经学会了可爱的珂朵莉树。

然后你就会发现这完全就是一道板子题，只需要进行连续颜色段的查询与覆盖可以了。

然后你就 AC 了。

code

int n;
struct CT
{
    int l,r;
    mutable int v;
    inline friend bool operator < (CT A,CT B){
        return A.l<B.l;
    }
};
set<CT> ct;
namespace Chtholly_Tree
{
    #define IT set<CT>::iterator
    inline IT split(int p)
    {
        IT it=ct.lower_bound({p,0,0});
        if(it!=ct.end()&&it->l==p) return it;
        it--;
        int l=it->l,r=it->r,v=it->v;
        ct.erase(it);ct.insert({l,p-1,v});
        return ct.insert({p,r,v}).first;
    }
    inline void assign(int l,int r,int v)
    {
        IT itr=split(r+1),itl=split(l);
        ct.erase(itl,itr);ct.insert({l,r,v});
    } 
    inline int query(int l,int r,int c)
    {
        int ans=0;
        IT itr=split(r+1),itl=split(l);
        for(IT it=itl;it!=itr;it++){
            if(it->v==c) ans+=it->r-it->l+1;
        }
        return ans;
    }
}
using namespace Chtholly_Tree;
signed main()
{
    n=read();
    for(int i=1;i<=n;i++){
        int x;x=read();ct.insert({i,i,x});
    }
    for(int i=1;i<=n;i++){
        int l,r,c;l=read(),r=read(),c=read();
        output(query(l,r,c));assign(l,r,c);
    }
    return 0;
}