bzoj2243&luogu2486 sdoi2011 染色

bzoj2243&luogu2486 sdoi2011 染色

​​ Description

给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。 请你写一个程序依次完成这m个操作。 Input

第一行包含2个整数n和m，分别表示节点数和操作数； 第二行包含n个正整数表示n个节点的初始颜色 下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。 下面 行每行描述一个操作： “C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c； “Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。 Output

对于每个询问操作，输出一行答案。 Sample Input

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

Sample Output

3

1

2

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

这题我在做的时候有一个坑点没有意识到

ansr=update1(query(root,id[tp[y]],id[y]),ansr); y=fa[tp[y]]; 由于我们合并的时候是从下往上 所以我们的ansr是要放在合并的后面

#include#define N 110000inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int y,next;}data[N<<1];struct node1{ int left,right,l,r,lc,rc,size,lazy; node1(){lazy=-1;}}tree[N<<2];struct node2{ int lc,rc,size; node2(){ rc=lc=size=-1; }};inline void swap(int &x,int &y){ x^=y;y^=x;x^=y;}int size[N],h[N],fa[N],dep[N],son[N],id[N],w[N],num,tp[N],a[N],n,m,root;void dfs1(int x){ size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (fa[x]==y) continue; dep[y]=dep[x]+1;fa[y]=x;dfs1(y);size[x]+=size[y]; if (size[y]>size[son[x]]) son[x]=y; }}void dfs2(int x,int top){ id[x]=++num;tp[x]=top;w[num]=a[x]; if (son[x]) dfs2(son[x],top); for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (son[x]==y||fa[x]==y) continue; dfs2(y,y); }}inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].size=tree[l].size+tree[r].size; if (tree[l].rc==tree[r].lc) tree[x].size--; tree[x].lc=tree[l].lc;tree[x].rc=tree[r].rc;}void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r; if (l==r){tree[x].lc=tree[x].rc=w[l];tree[x].size=1;return;} int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}inline node2 update1(node2 tmp1,node2 tmp2){ node2 tmp; if(tmp1.lc==-1){ tmp.lc=tmp2.lc;tmp.rc=tmp2.rc;tmp.size=tmp2.size;return tmp; } if (tmp2.lc==-1){ tmp.lc=tmp1.lc;tmp.rc=tmp1.rc;tmp.size=tmp1.size;return tmp; } tmp.lc=tmp1.lc;tmp.rc=tmp2.rc; tmp.size=tmp1.size+tmp2.size-(tmp1.rc==tmp2.lc); return tmp;}inline void pushdown(int x){ if (tree[x].lazy==-1) return; int l=tree[x].left,r=tree[x].right; int lc=tree[x].lc; tree[l].lc=tree[l].rc=tree[r].lc=tree[r].rc=lc; tree[l].size=tree[r].size=1;tree[l].lazy=tree[r].lazy=tree[x].lazy; tree[x].lazy=-1;}void change(int x,int l,int r,int c){ if (l<=tree[x].l&&r>=tree[x].r){ tree[x].lc=tree[x].rc=c;tree[x].size=1;tree[x].lazy=c;return; } int mid=tree[x].l+tree[x].r>>1;pushdown(x); if (l<=mid) change(tree[x].left,l,r,c); if (r>mid) change(tree[x].right,l,r,c); update(x);}void print(int x){ if (tree[x].left) print(tree[x].left); printf("%d %d %d %d %d %d\n",tree[x].l,tree[x].r,tree[x].lc,tree[x].rc,tree[x].size,tree[x].lazy); if (tree[x].right) print(tree[x].right);}node2 query(int x,int l,int r){ if (l<=tree[x].l&&r>=tree[x].r){ node2 tmp2;tmp2.size=tree[x].size;tmp2.lc=tree[x].lc;tmp2.rc=tree[x].rc;return tmp2; } int mid=tree[x].l+tree[x].r>>1; node2 tmp1,tmp2;pushdown(x); if (l<=mid) tmp1=query(tree[x].left,l,r); if (r>mid) tmp2=query(tree[x].right,l,r); return update1(tmp1,tmp2);}int main(){ freopen("2486.in","r",stdin); n=read();m=read(); for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;iid[y]) swap(x,y); change(root,id[x],id[y],z); }else{ int x=read(),y=read();node2 ansl,ansr; while (tp[x]!=tp[y]){ if (dep[tp[x]]>dep[tp[y]]){ ansl=update1(query(root,id[tp[x]],id[x]),ansl); x=fa[tp[x]]; }else{ ansr=update1(query(root,id[tp[y]],id[y]),ansr); y=fa[tp[y]]; } } swap(ansl.lc,ansl.rc); if (id[x]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。