颜色段均摊和 CDQ 分治

· · 题解

颜色段均摊有两层含义，都是建立在存在区间赋值（推平）操作的基础上。

  1. 随机数据：任意时刻的颜色段个数期望 O(\log_2n)；
  2. 非随机数据（本题）：每次推平时访问的颜色段个数为均摊 O(n)。

考虑本题有区间推平操作，所以使用珂朵莉树，然而我们发现数据不随机，所以暴力上珂朵莉树是 O(n^2) 的，不要想着用这种方法过去。

因为要求的是不同颜色个数，我们可以用只算第一次出现的方法来计算，设 pre_x=\max\limits_{(y<x\land a_y=a_x)\lor y=0}y，即上一次出现或者它在数组里第一次出现，则为 0。

这个数组有什么用？发现 x 在区间 [l,r] 第一次出现当且仅当 x\in[l,r],pre_x\in[0,l)，于是就变成了典型的二维数点问题，可以用 CDQ 分治解决。

如何维护这个数组？因为每次推平操作时，每一个被删除的颜色段都会有 O(1) 次修改，所以总修改数是 O(n) 的，总复杂度为 O(n\log_2^2n)，具体实现时要用 set 维护每种颜色的当前存在段，以便删除段时更改后继左端点的 pre 值：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
using ll=long long;
int n,QT,a[N],qt,rq,pr[N],mp[N],mt;
struct Q{int l,r,d,p;}q[N*6],q2[N*6];
struct odt{
    int l,r;mutable int d;
    bool operator<(const odt &z)
    const{return l<z.l;}
};
struct rag{
    int l,r;
    bool operator<(const rag &z)
    const{return r<z.r;}
};
void addp(int x,int d){q[++rq]={pr[x],x,d};}
void cgpr(int x,int y){
    if(pr[x]!=y)addp(x,-1),pr[x]=y,addp(x,1);
}
struct RGdt:set<rag>{
    void add(int l,int r){
        auto it=lower_bound({0,r});
        if(it!=end())cgpr(it->l,r);
        if(it!=begin())--it,cgpr(l,it->r);
        else cgpr(l,0);
        insert({l,r});
    }void del(int l,int r){
        erase({l,r});
        auto it=lower_bound({0,r});
        if(it!=end()){
            if(it!=begin()){
                auto at=it;--at;
                cgpr(it->l,at->r);
            }else cgpr(it->l,0);
        }
    }
}lt[N];
struct Odt:set<odt>{
    set<odt>::iterator split(int r){
        if(r>n)return end();
        auto it=lower_bound({r});
        if(it!=end()&&it->l==r)return it;
        --it;int L=it->l,R=it->r,D=it->d;
        lt[D].erase({L,R}),lt[D].insert({L,r-1});
        lt[D].insert({r,R});
        erase(it),insert({L,r-1,D});
        auto res=insert({r,R,D}).first;
        return res;
    }
}ADT;
ll ct[N],ans[N];
void solve(int l,int r){
    if(l>=r)return;
    int i,x,y,md=l+r>>1;
    solve(l,md),solve(md+1,r);
    for(x=md+1,y=l;x<=r;++x){
        while(y<=md&&q[y].l<=q[x].l){
            if(!q[y].p)for(i=q[y].r;i<=n;i+=i&-i)ct[i]+=q[y].d;++y;
        }if(q[x].p)for(i=q[x].r;i;i-=i&-i)ans[q[x].p]+=q[x].d*ct[i];
    }
    for(x=l;x<y;++x)
        if(!q[x].p)for(i=q[x].r;i<=n;i+=i&-i)ct[i]-=q[x].d;
    merge(q+l,q+md+1,q+md+1,q+r+1,q2+l,[&](Q x,Q y){
        return x.l<y.l;
    });for(i=l;i<=r;++i)q[i]=q2[i];
}
int main(){
    ios::sync_with_stdio(false);
    int i,j,A,l,r,d,qi;cin>>n>>QT;
    for(i=1;i<=n;++i)cin>>a[i],mp[++mt]=a[i];
    for(qi=1;qi<=QT;++qi){
        cin>>q2[qi].p>>q2[qi].l>>q2[qi].r;
        if(q2[qi].p==1){
            cin>>q2[qi].d;
            mp[++mt]=q2[qi].d;
        }
    }
    sort(mp+1,mp+mt+1),unique(mp+1,mp+mt+1)-mp-1;
    for(i=1;i<=n;++i)a[i]=lower_bound(mp+1,mp+mt+1,a[i])-mp;
    for(qi=1;qi<=QT;++qi)
        if(q2[qi].p==1)
            q2[qi].d=lower_bound(mp+1,mp+mt+1,q2[qi].d)-mp;
    for(i=1;i<=n;++i){
        ADT.insert({i,i,a[i]});
        if(lt[a[i]].size()){
            auto it=lt[a[i]].end();--it;
            pr[i]=it->r;
        }lt[a[i]].insert({i,i});
        addp(i,1);
    }
    for(qi=1;qi<=QT;++qi){
        A=q2[qi].p,l=q2[qi].l,r=q2[qi].r,d=q2[qi].d;
        if(A==1){
            auto R=ADT.split(r+1),L=ADT.split(l);
            auto it=L;lt[it->d].del(it->l,it->r);
            for(++it;it!=R;++it)cgpr(it->l,it->l-1),lt[it->d].del(it->l,it->r);
            ADT.erase(L,R);
            ADT.insert({l,r,d});
            lt[d].add(l,r);
        }else{
            ++qt,q[++rq]={l-1,r,1,qt};
            q[++rq]={l-1,l-1,-1,qt};
        }
    }solve(1,rq);
    for(i=1;i<=qt;++i)
        printf("%lld\n",ans[i]);
    return 0;
}