本文主要是介绍「HNOI2009」 梦幻布丁 - 线段树合并,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
N个布丁摆成一行,进行M次操作,每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。例如颜色分别为1,2,2,1的四个布丁一共有3段颜色。
输入格式
第一行给出N,M表示布丁的个数和操作次数;
第二行N个数A1,A2…An表示第i个布丁的颜色
第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变,其后的两个整数X,Y表示将所有颜色为X的变为Y,X可能等于Y。若第一个数字为2表示要进行询问当前有多少段颜色,这时你应该输出一个整数。
输出格式
针对第二类操作即询问,依次输出当前有多少段颜色。
数据范围
0 < N , M < 100001 0<N,M<100001 0<N,M<100001
0 < A i , x , y < 1000000 0<A_i,x,y<1000000 0<Ai,x,y<1000000
分析
可以对种颜色开一棵线段树,范围为1~n,表示在区间中为改颜色的位置,同时线段树中记录区间内的段数,为左+右,若中间都有,则减1。对于颜色变换,直接线段树合并即可,注意同时维护答案。
注意,对于根节点不能开1000000的数组存,只能用STL map,数组空间开不下,会爆系统栈,然后发生越界现象,然后就有许多莫名奇妙的错误,比如Wa,TLE等。
代码
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
const int N=100010,M=1000005;
const int LogN=20;
typedef struct SegmentTree {int l,r,ls,rs,len;
}Segment,SegT;
SegT nd[N*LogN];
int tot;
int st[N*LogN],top;
int n,m,ans,app[N];
map<int,int> rt;
void Clear(int x) {nd[x].l=nd[x].r=0;nd[x].len=nd[x].ls=nd[x].rs=0;
}
int New() {if (top) return Clear(st[top]),st[top--];else return ++tot;
}
void Pushup(int x) {int lc=nd[x].l,rc=nd[x].r;nd[x].len=nd[lc].len+nd[rc].len;if (nd[lc].rs&&nd[rc].ls) nd[x].len--;nd[x].ls=nd[lc].ls;nd[x].rs=nd[rc].rs;
}
void Add(int &rt,int l,int r,int x,int v) {if (!rt) {rt=New();nd[rt].l=nd[rt].r=0;}if (l==r) {nd[rt].len+=v;nd[rt].ls+=v;nd[rt].rs+=v;return;}int mid=(l+r)>>1;if (x<=mid) Add(nd[rt].l,l,mid,x,v);else Add(nd[rt].r,mid+1,r,x,v);Pushup(rt);
}
void Recycle(int &y) {st[++top]=y;Clear(y);y=0;
}
void Merge(int l,int r,int&x,int &y) {//x<-y;if (!y) return;if (!x) {x=New();nd[x]=nd[y];Recycle(y);return;}if (l==r) {nd[x].len=nd[y].len;nd[x].ls=nd[y].ls;nd[x].rs=nd[y].rs;Recycle(y);return;}int mid=(l+r)>>1;Merge(l,mid,nd[x].l,nd[y].l);Merge(mid+1,r,nd[x].r,nd[y].r);Recycle(y);Pushup(x);
}
int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) {int cl;scanf("%d",&cl);app[i]=cl;Add(rt[cl],1,n,i,1);}sort(app+1,app+n+1);int n_=unique(app+1,app+n+1)-app-1;for (int i=1;i<=n_;i++)ans+=nd[rt[app[i]]].len;for (int i=1;i<=m;i++) {int op,x,y;scanf("%d",&op);if (op==2) printf("%d\n",ans);else {scanf("%d%d",&x,&y);//x->y;if (x==y) continue;ans-=nd[rt[x]].len;ans-=nd[rt[y]].len;Merge(1,n,rt[y],rt[x]);ans+=nd[rt[y]].len;}}return 0;
}
这篇关于「HNOI2009」 梦幻布丁 - 线段树合并的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!