Steven_Mengの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$,换一下根即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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);
}
}
}

 评论