[SDOI2011]染色（信息学奥赛一本通 1563）（洛谷 2486）

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]之间。

--->题目是复制过来的，感觉字体大小很奇怪啊...不管了，先把这道鸽了我好几天的题A掉

这道题呢主要是运用树链剖分和线段树的思想

我们用tree这个结构体来维护线段树中每个节点的左端点的颜色lc、右端点的颜色rc、区间标记col（别忘了标记下传）以及该区间颜色段的数量sum。

以下几点需要特别注意（本题难点）：

在区间合并的时候，如果左子树的右端和右子树的左端颜色一致，那么该区间sum--；
在剖链的时候，如果上一条链的左端（即靠近根节点的一端，因为在建树的时候，线段树中越左边的位置越靠近根节点）颜色和当前剖到的链的右段（即远离根节点的一端，两链相交处）颜色一致，那么总颜色数sum--；
当top[x]==top[y]，即两点已经在同一条重链上时，两边端点的颜色都应与对应的点进行比较，如颜色一致，同样总颜色数sum--；

详情请见代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e6+,inf=0x3f3f3f3f;

 int next[*N],head[*N],to[N*],d[N],fa[N],v[*N],seg[*N],rev[*N],top[N],size[N],son[N],w[N];

 int n;

 int m,q,p,tot,cnt;

 int sum,ma;

 struct node{

     int lc,rc,sum,col;

 }tree[N];

 void ADD(int k,int l,int r,int v)

 {

     tree[k].lc=tree[k].rc=v;

     tree[k].sum=;

     tree[k].col=v;

     return ;

 }

 void pushdown(int k,int l,int r,int mid)

 {

     if(!tree[k].col)return ;

     ADD(k<<,l,mid,tree[k].col);

     ADD(k<<|,mid+,r,tree[k].col);

     tree[k].col=;

 }

 void dfs1(int s,int ff)

 {

     size[s]=;d[s]=d[ff]+;fa[s]=ff;

     for(int i=head[s],t;i,t=to[i];i=next[i])

     {

         if(t!=fa[s])

         {

             dfs1(t,s);

             size[s]+=size[t];

             if(size[t]>size[son[s]])son[s]=t;

         }

     }

 }

 void dfs2(int s)

 {

     if(son[s])

     {

         seg[son[s]]=++seg[];

         top[son[s]]=top[s];

         rev[seg[]]=son[s];

         dfs2(son[s]);

     }

     for(int i=head[s],t;t=to[i],i;i=next[i])

     {

         if(!top[t])

         {

             seg[t]=++seg[];

             rev[seg[]]=t;

             top[t]=t;

             dfs2(t);

         }

     }

 }

 void update(int k)

 {

     tree[k].sum=tree[k<<].sum+tree[k<<|].sum;

     if(tree[k<<].rc==tree[k<<|].lc)tree[k].sum--;

     tree[k].lc=tree[k<<].lc;

     tree[k].rc=tree[k<<|].rc;

 }

 void build(int k,int l,int r)

 {

     if(l==r)

     {

         tree[k].lc=tree[k].rc=w[rev[l]];

         tree[k].sum=;

         return ;

     }

     int mid=l+r>>;

     build(k<<,l,mid);

     build(k<<|,mid+,r);

     update(k);

 }

 node query2(int k,int l,int r,int x,int y)

 {

     if(l>=x&&r<=y)

     {

         return tree[k];

     }

     int mid=l+r>>;

     pushdown(k,l,r,mid);

     if(mid>=x)

     {

         if(mid<y)

         {

             node res,ll=query2(k<<,l,mid,x,y),rr=query2(k<<|,mid+,r,x,y);

             res.sum=ll.sum+rr.sum+(ll.rc==rr.lc?-:);

             res.lc=ll.lc;res.rc=rr.rc;

             return res;

         }

         else return query2(k<<,l,mid,x,y);

     }

     else return query2(k<<|,mid+,r,x,y);

 }

 int query1(int x,int y)

 {

     //这里可能不是很好理解，但是把a、b当做现任和备胎可能会好想一些（机房大佬lhy指点）

     int sum=,a=,b=;

     int fx=top[x],fy=top[y];

     while(fx!=fy)

     {

         if(d[fx]<d[fy])swap(x,y),swap(fx,fy),swap(a,b);

         node res=query2(,,n,seg[fx],seg[x]);

         sum+=res.sum;

         if(res.rc==a)sum--;

         a=res.lc;

         x=fa[fx];fx=top[x];

     }

     if(d[x]>d[y])swap(x,y),swap(a,b);

     node res=query2(,,n,seg[x],seg[y]);

     sum+=res.sum;

     if(res.lc==a) sum--;

     if(res.rc==b) sum--;

     return sum;

 }

 int read()

 {

     int f=;char ch;

     while((ch=getchar())<''||ch>'')

         if(ch=='-')f=-;

     int res=ch-'';

     while((ch=getchar())>=''&&ch<='')

         res=res*+ch-'';

     return res*f;

 }

 void write(int x)

 {

     if(x<)

     {

         putchar('-');

         x=-x;

     }

     if(x>)write(x/);

     putchar(x%+'');

 }

 void add(int x,int y)

 {

     next[++tot]=head[x];

     head[x]=tot;

     to[tot]=y;

 }

 void change2(int k,int l,int r,int x,int y,int v)

 {

     if(l>=x&&r<=y)return ADD(k,l,r,v);

     int mid=l+r>>;

     pushdown(k,l,r,mid);

     if(mid>=x)change2(k<<,l,mid,x,y,v);

     if(mid<y)change2(k<<|,mid+,r,x,y,v);

     update(k);

 }

 void change1(int x,int y,int v)

 {

     int fx=top[x],fy=top[y];

     while(fx!=fy)

     {

         if(d[fx]<d[fy])swap(x,y),swap(fx,fy);

         change2(,,n,seg[fx],seg[x],v);

         x=fa[fx];fx=top[x];

     }

     if(d[x]>d[y])swap(x,y);

     change2(,,n,seg[x],seg[y],v);

 }

 int main()

 {

     n=read();m=read();

     for(int i=;i<=n;i++)w[i]=read();

     for(int i=;i<n;i++)

     {

         int x,y;

         x=read();y=read();

         add(x,y);add(y,x);

     }

     dfs1(,);

     seg[]=top[]=rev[]=seg[]=;

     dfs2();

     build(,,n);

     while(m--)

     {

         char ch;int a,b;

         while((ch=getchar())<'A'||ch>'Z');

         //这个地方读入一定要小心！我的爆零经验就是前车之鉴！！！

         a=read();b=read();

         if(ch=='C')

         {

             int c;c=read();

             change1(a,b,c);

         }

         else

         {

             write(query1(a,b));

             putchar('\n');

         }

     }

     return ;

 }

 //硬生生凑个200行 ~(～￣▽￣)～

巴特西

[SDOI2011]染色（信息学奥赛一本通 1563）（洛谷 2486）

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]之间。

--->题目是复制过来的，感觉字体大小很奇怪啊...不管了，先把这道鸽了我好几天的题A掉

这道题呢主要是运用树链剖分和线段树的思想

我们用tree这个结构体来维护线段树中每个节点的左端点的颜色lc、右端点的颜色rc、区间标记col（别忘了标记下传）以及该区间颜色段的数量sum。

以下几点需要特别注意（本题难点）：

在区间合并的时候，如果左子树的右端和右子树的左端颜色一致，那么该区间sum--；

在剖链的时候，如果上一条链的左端（即靠近根节点的一端，因为在建树的时候，线段树中越左边的位置越靠近根节点）颜色和当前剖到的链的右段（即远离根节点的一端，两链相交处）颜色一致，那么总颜色数sum--；

当top[x]==top[y]，即两点已经在同一条重链上时，两边端点的颜色都应与对应的点进行比较，如颜色一致，同样总颜色数sum--；

详情请见代码：

最新文章

热门文章

巴特西

[SDOI2011]染色（信息学奥赛一本通 1563）（洛谷 2486）

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]之间。

--->题目是复制过来的，感觉字体大小很奇怪啊...不管了，先把这道鸽了我好几天的题A掉

这道题呢主要是运用树链剖分和线段树的思想

我们用tree这个结构体来维护线段树中每个节点的左端点的颜色lc、右端点的颜色rc、区间标记col（别忘了标记下传）以及该区间颜色段的数量sum。

以下几点需要特别注意（本题难点）：

在区间合并的时候，如果左子树的右端和右子树的左端颜色一致，那么该区间sum--；

在剖链的时候，如果上一条链的左端（即靠近根节点的一端，因为在建树的时候，线段树中越左边的位置越靠近根节点）颜色和当前剖到的链的右段（即远离根节点的一端，两链相交处）颜色一致，那么总颜色数sum--；

当top[x]==top[y]，即两点已经在同一条重链上时，两边端点的颜色都应与对应的点进行比较，如颜色一致，同样总颜色数sum--；

详情请见代码：

最新文章

热门文章

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

3
1
2