Steven_Meng's Blog

BZOJ

GDOI

对于每种颜色开一棵线段树，比如说对于颜色序列$\text {1 2 2 3 3 2}$，它的线段树开出来是这样的：

因为两种颜色搞在一起后，没有任何操作能把他们分开，不妨把替换视为合并。

比如把$3$替换成$2$，就是把$3$合并到$2$。

考虑如何$\rm pushup$，只要维护区间左右端点值$(0/1)$，和区间$1$的段数即可，如果左区间的右端点和右区间的左端点都是$1$，那么他们拼起来形成一大段，所以段数$-1$。

合并也非常简单，发现把$y$合并到$x$，就相当于把$y$所代表的线段树合并到$x$，并且删除$y$所代表的线段树。

还有一些要分类讨论的小细节：如果两种颜色相同或者没有$x$这种颜色，那么什么都不用搞，如果有$x$而没有$y$，那么相当于把$x$替换成$y$，换一下根即可。

#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace SegmentTree{
    struct node{
        int l,r;
        int val;//1或者0
        int lval,rval,sum;//左边为0/1，右边为0/1，总的段数
    }tree[MAXN*30];
    #define lc tree[i].l
    #define rc tree[i].r
    inline void pushup(int i,int x,int y){
        tree[i].lval=tree[x].lval;
        tree[i].rval=tree[y].rval;
        tree[i].sum=tree[x].sum+tree[y].sum;
        if (tree[x].rval==1&&tree[y].lval==1) tree[i].sum--;
    }
    int tot;
    void Update(int &i,int l,int r,int pos){
        if (!i) i=++tot;
        if (l==r){
            tree[i].lval=tree[i].rval=tree[i].sum=1;
            return ;
        }
        int mid=(l+r)>>1;
        if (pos<=mid) Update(lc,l,mid,pos);
        else Update(rc,mid+1,r,pos);
        pushup(i,lc,rc);
    }
    void Merge(int &x,int &y){
        if (!x||!y){
            x=x+y;
            return ;
        }
        Merge(tree[x].l,tree[y].l);
        Merge(tree[x].r,tree[y].r);
        pushup(x,tree[x].l,tree[x].r);
        y=0;//非常重要，要删除y这棵树
    }
}
using namespace SegmentTree;
map<int,int>rt;
int main(){
    #define SUM(c) tree[rt[c]].sum
    int n=read(),m=read();
    for (register int i=1;i<=n;++i){
        int color=read();
        Update(rt[color],1,n,i);
    }
    int ans=0;
    for (const auto& it:rt){
        ans+=SUM(it.first);
    }
    for (register int i=1;i<=m;++i){
        int opr=read();
        if (opr==1){
            int x=read(),y=read();
            if (x==y||!rt[x]) continue;//如果两种颜色相同或者没有x这种颜色
            if (!rt[y]){//相当于是替换
                rt[y]=rt[x];
                rt[x]=0;
                continue;
            }
            ans-=SUM(x),ans-=SUM(y);
            Merge(rt[y],rt[x]);
            ans+=SUM(y);
        }
        else {
            printf("%d\n",ans);
        }
    }
}