bzoj2243【SDOI2011】染色
2024-08-28 09:56:06
2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MB id=2243" style="color:blue; text-decoration:none">Submit id=2243" style="color:blue; text-decoration:none">Discuss
Submit: 4537 Solved: 1702
[
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
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
1
2
HINT
数N<=10^5。操作数M<=10^5,全部的颜色C为整数且在[0, 10^9]之间。
Source
有关链的操作,非常显然树链剖分+线段树维护区间。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
using namespace std;
struct seg{int l,r,lc,rc,s,tag;}t[maxn*4];
struct edge_type{int next,to;}e[maxn*2];
int n,m,x,y,z,cnt,tot;
int head[maxn],d[maxn],son[maxn],belong[maxn],p[maxn],a[maxn],f[maxn][18];
char ch;
bool vst[maxn];
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*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add_edge(int x,int y)
{
e[++cnt]=(edge_type){head[x],y};head[x]=cnt;
e[++cnt]=(edge_type){head[y],x};head[y]=cnt;
}
inline void dfs1(int x)
{
vst[x]=true;son[x]=1;
for(int i=1;i<=17;i++)
{
if (d[x]<(1<<i)) break;
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=head[x];i;i=e[i].next)
{
if (vst[e[i].to]) continue;
d[e[i].to]=d[x]+1;
f[e[i].to][0]=x;
dfs1(e[i].to);
son[x]+=son[e[i].to];
}
}
inline void dfs2(int x,int chain)
{
p[x]=++tot;belong[x]=chain;
int k=0;
for(int i=head[x];i;i=e[i].next)
if (d[e[i].to]>d[x]&&son[k]<son[e[i].to]) k=e[i].to;
if (!k) return;
dfs2(k,chain);
for(int i=head[x];i;i=e[i].next)
if (d[e[i].to]>d[x]&&e[i].to!=k) dfs2(e[i].to,e[i].to);
}
inline int lca(int x,int y)
{
if (d[x]<d[y]) swap(x,y);
int t=d[x]-d[y];
F(i,0,17) if (t&(1<<i)) x=f[x][i];
if (x==y) return x;
D(i,17,0) if (f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
return f[x][0];
}
inline void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;t[k].s=1;t[k].tag=-1;
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
inline void pushup(int k)
{
t[k].lc=t[k<<1].lc;t[k].rc=t[k<<1|1].rc;
if (t[k<<1].rc==t[k<<1|1].lc) t[k].s=t[k<<1].s+t[k<<1|1].s-1;
else t[k].s=t[k<<1].s+t[k<<1|1].s;
}
inline void update(int k,int z)
{
t[k].tag=t[k].lc=t[k].rc=z;
t[k].s=1;
}
inline void pushdown(int k)
{
if (t[k].tag==-1) return;
update(k<<1,t[k].tag);
update(k<<1|1,t[k].tag);
t[k].tag=-1;
}
inline void change(int k,int l,int r,int x)
{
if (t[k].l==l&&t[k].r==r){update(k,x);return;}
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
if (r<=mid) change(k<<1,l,r,x);
else if (l>mid) change(k<<1|1,l,r,x);
else{change(k<<1,l,mid,x);change(k<<1|1,mid+1,r,x);}
pushup(k);
}
inline int ask(int k,int l,int r)
{
if (t[k].l==l&&t[k].r==r) return t[k].s;
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
if (r<=mid) return ask(k<<1,l,r);
else if (l>mid) return ask(k<<1|1,l,r);
else
{
int tmp=t[k<<1].rc==t[k<<1|1].lc;
return ask(k<<1,l,mid)+ask(k<<1|1,mid+1,r)-tmp;
}
}
inline int getc(int k,int pos)
{
if (t[k].l==t[k].r) return t[k].lc;
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
if (pos<=mid) return getc(k<<1,pos);
else return getc(k<<1|1,pos);
}
inline void solvechange(int x,int t,int c)
{
while (belong[x]!=belong[t])
{
change(1,p[belong[x]],p[x],c);
x=f[belong[x]][0];
}
change(1,p[t],p[x],c);
}
inline int solvesum(int x,int t)
{
int sum=0;
while (belong[x]!=belong[t])
{
sum+=ask(1,p[belong[x]],p[x]);
if (getc(1,p[belong[x]])==getc(1,p[f[belong[x]][0]])) sum--;
x=f[belong[x]][0];
}
sum+=ask(1,p[t],p[x]);
return sum;
}
int main()
{
n=read();m=read();
F(i,1,n) a[i]=read();
F(i,1,n-1){x=read();y=read();add_edge(x,y);}
dfs1(1);
dfs2(1,1);
build(1,1,n);
F(i,1,n) change(1,p[i],p[i],a[i]);
F(i,1,m)
{
ch=getchar();
while (ch<'A'||ch>'Z') ch=getchar();
if (ch=='Q')
{
x=read();y=read();
int t=lca(x,y);
printf("%d\n",solvesum(x,t)+solvesum(y,t)-1);
}
else
{
x=read();y=read();z=read();
int t=lca(x,y);
solvechange(x,t,z);solvechange(y,t,z);
}
}
}
最新文章
- deepin 15.3 安装数据库MariaDB10.0
- JavaScript-事件坐标
- [.net 面向对象编程基础] (4) 基础中的基础——数据类型转换
- Hybrid框架UI重构之路:二、事出有因
- 【MySQL 安装过程1】顺利安装MySQL完整过程
- 理解em,rem以及rem的失效问题
- 【LeetCode】338. Counting Bits (2 solutions)
- WPF打印票据
- 用 Python 和 OpenCV 检测图片上的条形码
- DrawerLayout带有侧滑功能的布局类(1)
- django 学习-1
- hdoj 2147 kiki&#39;s game【博弈】
- hibernate和struts2实现分页功能
- xcode 执行时模拟器不可选的问题
- android第一天错误
- 【2】docker 与UFW
- Android .mk文件语法解析
- 简学Python第一章__进入PY的世界
- 【Shell Basic】source . 与 bash sh 的区别
- L1-Day6
热门文章
- 【PostgreSQL-9.6.3】LOG: unrecognized configuration parameter ";dynamic_shared_memory_type";
- linux下启动、停止tomcat,杀死tomcat进程
- UI开发模式-容器模式
- Change the color of a link in an NSMutableAttributedString
- [HNOI2006]最短母串 (AC自动机+状压)
- ThinkPHP---案例2--职员管理功能
- 【转】Go语言入门教程(一)Linux下安装Go
- Java之三大基础排序(冒泡、选择、插入)
- P1048 采药(洛谷,动态规划递推,01背包原题)
- MySQL-date和datetime