yyb_test
2018-04-11 21:40:05
这道题有两种解法，树剖&LCT 但是实现方法却截然不同 做完本题后对树剖和LCT会有更深的认识 让我们充分认识到两者之间的优缺点
优点：暴力，直接
缺点：代码量大，常数大（毕竟是优雅的暴力）
做法：
一、线段树：
需要多维护两个值，lc和rc，分别记录右端 点和左端点的颜色。
在合并两个子区间的时候，如果左区间的右端点颜色=右区间的左端点颜色，则颜色带数量-1
二、路径求和
当然不能naive地把路径上的颜色带累加
我们发现树剖求LCA是利用两个点按照深度向上跳最后跳到一起的方法
自下而上，根据深度交替向上跳
而这个路径可以看成‘人’字型
我们不妨把这个路径分成两边
左边和右边
我们再用变量
pos1表示当前要往上跳的路径\上次的终点颜色
pos2表示另一条路径\上一次的终点颜色
这样，如果当前往上跳的路径\这次的起点颜色等于 当前要往上跳的路径\上次的终点颜色 那么颜色段数量-1
如果当前要往上跳的节点所在路径发生了改变（也就是路径发生了交替），则swap(pos1,pos2)
然后问题就落到如何找起点终点颜色了
很简单，起点颜色就是线段树上查询的左端点的颜色，终点颜色就是查询的右端点的颜色。
在往上跳（线段树查询）的时候顺便记录一下Lc和Rc即可
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define rg register int
#define ll long long
#define RG register
#define il inline
using namespace std;
il int gi() {
rg x=0,o=0;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||'9'<ch)) ch=getchar();
if(ch=='-') o=1,ch=getchar();
while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return o?-x:x;
}
#define SZ 1000002
int n,m,pos1,pos2,lc,rc,col[SZ];
char ch;
struct Edge { int to,nxt; }e[SZ<<1];
int Ehead[SZ],Ecnt=2;
il void Eadd(rg u,rg v) {
e[Ecnt]=(Edge){v,Ehead[u]};
Ehead[u]=Ecnt++;
e[Ecnt]=(Edge){u,Ehead[v]};
Ehead[v]=Ecnt++;
}
int cnt,fa[SZ],id[SZ],rid[SZ],siz[SZ],dep[SZ],son[SZ],top[SZ];
il void pou_debug() {
for(rg i=1; i<=n; ++i)
printf("fa:%d id:%d son:%d siz:%d dep:%d top:%d\n",fa[i],id[i],son[i],siz[i],dep[i],top[i]);
}
void dfs1(rg u,rg ff) {
fa[u]=ff,dep[u]=dep[ff]+1,siz[u]=1;
for(rg v,i=Ehead[u]; i; i=e[i].nxt) {
v=e[i].to;
if(v==ff) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(rg u,rg tp) {
top[u]=tp,id[u]=++cnt,rid[cnt]=u;
if(!son[u]) return;
dfs2(son[u],tp);
for(rg v,i=Ehead[u]; i; i=e[i].nxt) {
v=e[i].to;
if(v==son[u]||v==fa[u]) continue;
dfs2(v,v);
}
}
#define lson rt<<1
#define rson rt<<1|1
struct Segtree { int l,r,lc,rc,c,v; }tr[SZ<<4];
il void Seg_debug() {
for(rg i=1; i<=n*3; ++i)
printf("#%d : l:%d r:%d lc:%d rc:%d c:%d v:%d\n",i,tr[i].l,tr[i].r,tr[i].lc,tr[i].rc,tr[i].c,tr[i].v);
}
il void pushup(rg rt) {
tr[rt].v=tr[lson].v+tr[rson].v;
if(tr[lson].rc==tr[rson].lc) --tr[rt].v;
tr[rt].lc=tr[lson].lc;
tr[rt].rc=tr[rson].rc;
}
il void pushcol(rg rt,rg col) {
tr[rt].lc=tr[rt].rc=col;
tr[rt].v=1,tr[rt].c=col;
}
il void pushdown(rg rt) {
if(tr[rt].c) {
if(lson) pushcol(lson,tr[rt].c);
if(rson) pushcol(rson,tr[rt].c);
tr[rt].c=0;
}
}
void build(rg rt,rg l,rg r) {
tr[rt].l=l,tr[rt].r=r;
if(l==r) {
tr[rt].lc=tr[rt].rc=col[rid[l]];
tr[rt].v=1;
return;
}
rg mid=l+r>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(rt);
}
void modify(rg rt,rg L,rg R,rg x) {
rg l=tr[rt].l,r=tr[rt].r;
if(L<=l&&r<=R) {
pushcol(rt,x);
return;
}
pushdown(rt);
rg mid=l+r>>1;
if(L<=mid) modify(lson,L,R,x);
if(R>mid) modify(rson,L,R,x);
pushup(rt);
}
int query(rg rt,rg L,rg R) {
rg l=tr[rt].l,r=tr[rt].r;
if(L<=l&&r<=R) {
if(l==L) lc=tr[rt].lc;
if(r==R) rc=tr[rt].rc;
return tr[rt].v;
}
pushdown(rt);
rg mid=l+r>>1;
if(R<=mid) return query(lson,L,R);
if(L>mid) return query(rson,L,R);
rg ret=query(lson,L,R)+query(rson,L,R);
if(tr[lson].rc==tr[rson].lc) --ret;
return ret;
}
il void add(rg u,rg v,rg c) {
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
modify(1,id[top[u]],id[u],c);
u=fa[top[u]];
}
if(id[u]>id[v]) swap(u,v);
modify(1,id[u],id[v],c);
}
il int ask(rg u,rg v) {
rg ret=0;
pos1=pos2=0;
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v),swap(pos1,pos2);
ret+=query(1,id[top[u]],id[u]);
if(rc==pos1) --ret;
pos1=lc,u=fa[top[u]];
}
if(id[u]>id[v]) swap(u,v),swap(pos1,pos2);
ret+=query(1,id[u],id[v]);
if(lc==pos1) --ret;
if(rc==pos2) --ret;
return ret;
}
int main() {
n=gi(),m=gi();
for(rg i=1; i<=n; ++i) col[i]=gi();
for(rg u,v,i=1; i<n; ++i)
u=gi(),v=gi(),Eadd(u,v);
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(rg a,b,c,i=1; i<=m; ++i) {
ch=getchar();
while(ch!='C'&&ch!='Q') ch=getchar();
if(ch=='C') {
a=gi(),b=gi(),c=gi();
add(a,b,c);
}
if(ch=='Q') {
a=gi(),b=gi();
printf("%d\n",ask(a,b));
}
}
return 0;
}优点：常数小，代码短
缺点：难想，难实现，细节多
做法：
我们考虑把连接不同色点的边权值设为1,连接同色的点的边权设为0，这样我们就可以把问题转化为查询这条路径上所有的边权和，你要输出的就是这个答案加一
对于维护，我们对每个splay节点一个最左端点的值和最右端点的颜色，这样，对于它的父亲节点，就可以很轻松地找到其前驱与后继的颜色，这样便可以累计它跟前驱后继所连边的权值和了。
前驱=左儿子最右端点，后继=右儿子最左端点
注意：区间反转时最左和最右端点也要反转
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define rg register int
#define ll long long
#define RG register
#define il inline
using namespace std;
il int gi() {
rg x=0,o=0;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||'9'<ch)) ch=getchar();
if(ch=='-') o=1,ch=getchar();
while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return o?-x:x;
}
#define SZ 1000010
int n,m;
char ch;
#define lson tr[x].ch[0]
#define rson tr[x].ch[1]
struct Splaytree { int w,c,lc,rc,tag,rev,fa,ch[2]; }tr[SZ];
int stk[SZ],top;
il bool isroot(rg x) { return tr[tr[x].fa].ch[0]!=x&&tr[tr[x].fa].ch[1]!=x; }
il void pushdown(rg x) {
if(tr[x].rev) {
swap(lson,rson);
swap(tr[lson].lc,tr[lson].rc);
swap(tr[rson].lc,tr[rson].rc);
tr[lson].rev^=1,tr[rson].rev^=1;
tr[x].rev=0;
}
if(tr[x].tag) {
tr[x].lc=tr[x].rc=tr[x].c=tr[x].tag;
tr[lson].tag=tr[rson].tag=tr[x].tag;
tr[x].w=tr[x].tag=0;
}
}
il void pushup(rg x) {
pushdown(lson),pushdown(rson);
tr[x].w=tr[lson].w+tr[rson].w;
if(lson) {
tr[x].lc=tr[lson].lc;
if(tr[x].c!=tr[lson].rc) ++tr[x].w;
}
else tr[x].lc=tr[x].c;
if(rson) {
tr[x].rc=tr[rson].rc;
if(tr[x].c!=tr[rson].lc) ++tr[x].w;
}
else tr[x].rc=tr[x].c;
}
il void rotate(rg x) {
rg y=tr[x].fa,z=tr[y].fa;
rg k=tr[y].ch[1]==x;
if(!isroot(y)) tr[z].ch[tr[z].ch[1]==y]=x; tr[x].fa=z;
tr[y].ch[k]=tr[x].ch[k^1],tr[tr[x].ch[k^1]].fa=y;
tr[x].ch[k^1]=y,tr[y].fa=x;
pushup(y);
}
il void splay(rg x) {
stk[top=1]=x;
for(rg i=x; !isroot(i); i=tr[i].fa) stk[++top]=tr[i].fa;
while(top) pushdown(stk[top--]);
while(!isroot(x)) {
rg y=tr[x].fa,z=tr[y].fa;
if(!isroot(y))
(tr[y].ch[0]==x)^(tr[z].ch[0]==y)?rotate(x):rotate(y);
rotate(x);
}
pushup(x);
}
il void access(rg x) {
for(rg y=0; x; y=x,x=tr[x].fa) splay(x),rson=y,pushup(x);
}
il void makeroot(rg x) {
access(x),splay(x),tr[x].rev^=1;
}
il int findroot(rg x) {
access(x),splay(x);
while(lson) x=lson;
return x;
}
il void split(rg x,rg y) {
makeroot(x),access(y),splay(y);
}
il void link(rg x,rg y) {
makeroot(x),tr[x].fa=y;
}
int main() {
n=gi(),m=gi();
for(rg i=1; i<=n; ++i) tr[i].c=tr[i].lc=tr[i].rc=gi();
for(rg u,v,i=1; i<n; ++i) u=gi(),v=gi(),link(u,v);
for(rg a,b,c,i=1; i<=m; ++i) {
ch=getchar();
while(ch!='C'&&ch!='Q') ch=getchar();
if(ch=='C') {
a=gi(),b=gi(),c=gi();
split(a,b);
tr[b].tag=c;
}
if(ch=='Q') {
a=gi(),b=gi();
split(a,b);
printf("%d\n",tr[b].w+1);
}
}
return 0;
}博客链接