珂朵莉树的树状数组实现方法

· · 算法·理论

珂朵莉树概述

在一部分数据结构问题中，对于多个连续相同的值我们可以放在一起处理，这就是珂朵莉树的基本思想。我们将序列分成若干个三元组 (l,r,c) 表示 [l,r] 区间内的所有数都是 c。这样的三元组被我们称为颜色段。

对于一部分问题，珂朵莉树的复杂度是错误的，但是在不断覆盖中，颜色段的数量会锐减，使得珂朵莉树可以高效解决。

对于另一部分问题，我们在查询的同时将其覆盖，意味着每次遍历都代表一次颜色段合并，由于合并总次数往往不会太多，均摊下来复杂度则是正确的。我们将给出一种这种问题的更好的珂朵莉树实现方式。

珂朵莉树更好的实现方法（树状数组）

参考 oiwiki 中给出的 set 实现方法与链表实现方法，我们可以知道珂朵莉本质上是链表结构，所以当确定头尾所在的颜色段之后就可以用前驱后继高效遍历。

但是如何快速寻找一个点所在的颜色段呢？

我们考虑颜色段是什么样子的：

(1,r_1) , (r_1+1,r_2) , (r_2+1,r_3) \cdots (r_m+1,n)

颜色段完全覆盖整个序列且互不相交。

我们设置一个标记数组 t。

我们不妨对于每个颜色段 (l,r,c) ，将 t_l 异或上 l ，在 t_{r+1} 异或上 l ，这样对于第 x 个数，他所在的颜色段的左端点就是 \bigoplus\limits_{i=1}^{x} t_i。

考虑查询的都是前缀，所以树状数组维护即可。

测试效果

P13983数列分块入门 8

#include<bits/stdc++.h>
#define int unsigned int 
using namespace std;
const int N=3e5+5;
int l[N],r[N],c[N],tree[N],n;
void read(int &x){
    int flag=1;
    char c=getchar_unlocked();
    while(c<'0'||c>'9'){
        if(c=='-'){
            flag=-1;
        }
        c=getchar_unlocked();
    }
    x=0;
    while('0'<=c&&c<='9'){
        x*=10,x+=c-'0';
        c=getchar_unlocked();
    }
    x*=flag;
}
void write(int &x){
    if(!x){
        putchar_unlocked('0');
        return ;
    }
    int cnt=0,val[22];
    while(x){
        val[++cnt]=x%10;
        x/=10;
    }
    while(cnt){
        putchar_unlocked('0'+val[cnt--]);
    }
}
void upd(int x){
    for(int i=l[x];i<=n;i+=(i&-i))tree[i]^=l[x];
    for(int i=r[x]+1;i<=n;i+=(i&-i))tree[i]^=l[x];
}
int query(int x){
    int ans=0;for(int i=x;i;i-=(i&-i))ans^=tree[i];
    return ans;
}
void split(int x){
    if(!x)return ;
    int id=query(x);
    if(x==r[id])return ;
    upd(id);
    c[x+1]=c[id];l[x+1]=x+1;r[x+1]=r[id];
    r[id]=x;
    upd(x+1);upd(id);
}
signed main(){
    read(n);
    for(int i=1;i<=n;i++){
        int x;read(x);l[i]=r[i]=i;
        c[i]=x;
        upd(i);
    }
    for(int i=1;i<=n;i++){
        int L,R,C;
        read(L);read(R);read(C);
        int ans=0;
        split(L-1);split(R);
        for(int j=L;j<=R;j=r[j]+1){
            ans+=(r[j]-l[j]+1)*(c[j]==C);upd(j);
        }
        l[L]=L;r[L]=R;c[L]=C;upd(L);
        write(ans);putchar_unlocked('\n');
    }
    return 0;
}

目前题目最优解 rk1。