BZOJ 2243: [SDOI2011]染色 树链剖分 倍增lca 线段树
2243: 染色Time Limit: 20 Sec Memory Limit: 256 MB题目连接
http://www.lydsy.com/JudgeOnline/problem.php?id=2243
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
2
HINT
题意
题解：
树链剖分 倍增lca 线段树
http://hzwer.com/2561.html
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 400001
#define mod 10007
#define eps 1e-9
int Num;
char CH;
//const int inf=0x7fffffff; //нчоч╢С
const int inf=0x3f3f3f3f;
/*
inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH+48);
puts("");
}
*/
inline ll 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 P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH+48);
puts("");
}
//**************************************************************************************
#define N 100001
int n,m,cnt,sz,head,deep,son,belong,pl,v,ft;
bool vis;
struct seg
{
int l,r,lc,rc,s,tag;
}t;
struct edge
{
int to,next;
}e;
void insert(int u,int v)
{
e[++cnt].to=v;e.next=head;head=cnt;
e[++cnt].to=u;e.next=head;head=cnt;
}
void dfs1(int x)
{
vis=son=1;
for(int i=1;i<=17;i++)
{
if(deep<(1<<i))
break;
ft=ft];
}
for(int i=head;i;i=e.next)
{
if(vis.to])
continue;
deep.to]=deep+1;
ft.to]=x;
dfs1(e.to);
son+=son.to];
}
}
void dfs2(int x,int chain)
{
pl=++sz;
belong=chain;
int k=0;
for(int i=head;i;i=e.next)
if(deep.to]>deep&&son<son.to])
k=e.to;
if(!k)
return;
dfs2(k,chain);
for(int i=head;i;i=e.next)
if(deep.to]>deep&&k!=e.to)
dfs2(e.to,e.to);
}
int lca(int x,int y)
{
if(deep<deep)
swap(x,y);
int t=deep-deep;
for(int i=0;i<=17;i++)
if(t&(1<<i))
x=ft;
for(int i=17;i>=0;i--)
if(ft!=ft)
{
x=ft;
y=ft;
}
if(x==y)
return x;
return ft;
}
void build(int k,int l,int r)
{
t.l=l,t.r=r,t.s=1,t.tag=-1;
if(l==r)
return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void pushup(int k)
{
t.lc=t.lc;t.rc=t.rc;
if(t.rc^t.lc)t.s=t.s+t.s;
else t.s=t.s+t.s-1;
}
void pushdown(int k)
{
int tmp=t.tag;t.tag=-1;
if(tmp==-1||t.l==t.r)return;
t.s=t.s=1;
t.tag=t.tag=tmp;
t.lc=t.rc=tmp;
t.lc=t.rc=tmp;
}
void change(int k,int x,int y,int c)
{
pushdown(k);
int l=t.l,r=t.r;
if(l==x&&r==y)
{t.lc=t.rc=c;t.s=1;t.tag=c;return;}
int mid=(l+r)>>1;
if(mid>=y)change(k<<1,x,y,c);
else if(mid<x)change(k<<1|1,x,y,c);
else
{
change(k<<1,x,mid,c);
change(k<<1|1,mid+1,y,c);
}
pushup(k);
}
int ask(int k,int x,int y)
{
pushdown(k);
int l=t.l,r=t.r;
if(l==x&&r==y)return t.s;
int mid=(l+r)>>1;
if(mid>=y)return ask(k<<1,x,y);
else if(mid<x)return ask(k<<1|1,x,y);
else
{
int tmp=1;
if(t.rc^t.lc)tmp=0;
return ask(k<<1,x,mid)+ask(k<<1|1,mid+1,y)-tmp;
}
}
int getc(int k,int x)
{
pushdown(k);
int l=t.l,r=t.r;
if(l==r)return t.lc;
int mid=(l+r)>>1;
if(x<=mid)return getc(k<<1,x);
else return getc(k<<1|1,x);
}
int solvesum(int x,int f)
{
int sum=0;
while(belong!=belong)
{
sum+=ask(1,pl],pl);
if(getc(1,pl])==getc(1,pl]]))sum--;
x=ft];
}
sum+=ask(1,pl,pl);
return sum;
}
void solvechange(int x,int f,int c)
{
while(belong!=belong)
{
change(1,pl],pl,c);
x=ft];
}
change(1,pl,pl,c);
}
void solve()
{
int a,b,c;
dfs1(1);
dfs2(1,1);
build(1,1,n);
for(int i=1;i<=n;i++)
change(1,pl,pl,v);
for(int i=1;i<=m;i++)
{
char ch;
scanf("%s",ch);
if(ch=='Q')
{
scanf("%d%d",&a,&b);
int t=lca(a,b);
printf("%d\n",solvesum(a,t)+solvesum(b,t)-1);
}
else
{
scanf("%d%d%d",&a,&b,&c);
int t=lca(a,b);
solvechange(a,t,c);solvechange(b,t,c);
}
}
}
void ini()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&v);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
insert(x,y);
}
}
int main()
{
ini();
solve();
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15303184/3111137
页:
[1]