題幹描述
輸入描述
輸出格式
對于每個詢問操作，輸出一行答案。
輸入輸出樣例
輸入 #1 複制
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
輸出 #1 複制
3
1
2
說明/提示
題幹很清楚，就是樹鍊剖分+線段樹的基本操作。但是在實作的過程中有幾個點需要注意一下。
我們分類讨論一下：
第一種情況：
左區間：1231（顔色個數為4） 右區間：222（個數為1）
合并後：1231222（顔色個數為4+1=5）
這是第一種情況：沒有重複。
我們再來看第二種：
左區間：1231（顔色個數為4）右區間：121（個數為3）
合并後：1231121（顔色個數為4+3-1）
這就是第二種情況了，左區間的最後一個顔色和右區間的第一個顔色重合，也就重複了，是以總數減一。
是以我們線上段樹更新過程中需要維護這段區間内的最左邊的顔色和最右邊的顔色。如果左兒子的右端點顔色和右兒子的左端點顔色相等的話，就減一就可以了。線段樹區間合并的操作。
剩下的就是樹鍊剖分将樹剖成幾條鍊了。樹鍊剖分的基本操作。
但是樹鍊剖分之後的這一條鍊上的點并不是通過一次操作就能求出來的，而是經過好幾次操作，那麼這幾次操作之間相鄰的顔色要是重了，就出現的計數錯誤。是以我們在求完一次之後，我們需要查詢一下這次左端點的顔色和下一次查詢中右端點的顔色是否相同，如果相同，就減一。
代碼如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxx=1e5+100;
struct node{
int l;
int r;
int lazy;
int lcor;
int rcor;
int num;
}p[maxx<<2];
struct edge{
int to,next;
}e[maxx<<1];
int head[maxx<<1],top[maxx],fa[maxx];
int in[maxx],son[maxx],pre[maxx];
int a[maxx],deep[maxx],size[maxx];
int n,m,tot,sign;
/*----------準備階段---------*/
inline void init()
{
memset(son,0,sizeof(son));
memset(head,-1,sizeof(head));
tot=sign=0;
}
inline void add(int u,int v)
{
e[tot].to=v,e[tot].next=head[u],head[u]=tot++;
}
/*-----------dfs-----------*/
inline void dfs1(int u,int f)
{
fa[u]=f;
deep[u]=deep[f]+1;
size[u]=1;
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(to==f) continue;
dfs1(to,u);
size[u]+=size[to];
if(size[to]>size[son[u]]) son[u]=to;
}
}
inline void dfs2(int u,int Top)
{
in[u]=++sign;
pre[sign]=u;
top[u]=Top;
if(son[u]) dfs2(son[u],Top);
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(to==fa[u]||to==son[u]) continue;
dfs2(to,to);
}
}
/*-----------線段樹------------*/
inline void pushup(int cur)//往上更新的時候隻傳左端點顔色和右端點顔色就行
{
p[cur].lcor=p[cur<<1].lcor;
p[cur].rcor=p[cur<<1|1].rcor;
p[cur].num=p[cur<<1].num+p[cur<<1|1].num;
if(p[cur<<1].rcor==p[cur<<1|1].lcor) p[cur].num--;
}
inline void pushdown(int cur)
{
if(p[cur].lazy!=-1)
{
p[cur<<1].lazy=p[cur<<1|1].lazy=p[cur].lazy;
p[cur<<1].lcor=p[cur<<1].rcor=p[cur<<1|1].lcor=p[cur<<1|1].rcor=p[cur].lcor;
p[cur<<1].num=p[cur<<1|1].num=1;
p[cur].lazy=-1;
}
}
inline void build(int l,int r,int cur)
{
p[cur].l=l;
p[cur].r=r;
p[cur].num=0;
p[cur].lazy=-1;
p[cur].lcor=p[cur].rcor=-1;
if(l==r)
{
p[cur].lcor=p[cur].rcor=a[pre[l]];
p[cur].num=1;
return ;
}
int mid=l+r>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
pushup(cur);
}
inline void update(int l,int r,int cur,int col)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r)
{
p[cur].lcor=p[cur].rcor=col;
p[cur].num=1;
p[cur].lazy=col;
return ;
}
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) update(l,r,cur<<1,col);
else if(l>mid) update(l,r,cur<<1|1,col);
else update(l,mid,cur<<1,col),update(mid+1,r,cur<<1|1,col);
pushup(cur);
}
inline node query(int l,int r,int cur)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r) return p[cur];
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) return query(l,r,cur<<1);
else if(l>mid) return query(l,r,cur<<1|1);
else//區間合并，判斷相鄰兩端點是否顔色相同
{
node a=query(l,mid,cur<<1);
node b=query(mid+1,r,cur<<1|1);
node c;
c.lcor=a.lcor;c.rcor=b.rcor;
c.num=a.num+b.num;
if(a.rcor==b.lcor) c.num--;
return c;
}
}
inline int query_col(int pos,int cur)//查詢單點顔色
{
int L=p[cur].l;
int R=p[cur].r;
if(L==R) return p[cur].lcor;
pushdown(cur);
int mid=L+R>>1;
if(pos<=mid) return query_col(pos,cur<<1);
else return query_col(pos,cur<<1|1);
}
/*-------------樹鍊剖分-------------*/
inline void Update(int x,int y,int col)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
update(in[top[x]],in[x],1,col);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
update(in[x],in[y],1,col);
}
inline int Query(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=query(in[top[x]],in[x],1).num;
int scol=query_col(in[top[x]],1);
int fcol=query_col(in[fa[top[x]]],1);//标記相鄰端點顔色是否相同，如果相同，就減一。
if(scol==fcol) ans--;
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
ans+=query(in[x],in[y],1).num;
return ans;
}
int main()
{
int x,y,z;char c[2];
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
deep[0]=0;
dfs1(1,0);
dfs2(1,1);
build(1,n,1);
while(m--)
{
scanf("%s",c);
if(c[0]=='Q') scanf("%d%d",&x,&y),printf("%d\n",Query(x,y));
else
{
scanf("%d%d%d",&x,&y,&z);
Update(x,y,z);
}
}
return 0;
}
簡化到線段版本，就簡單多了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxx=5e5+100;
struct node{
int l;
int r;
int lcol;
int rcol;
int num;
int lazy;
}p[maxx<<2];
int n,m;
inline void pushdown(int cur)
{
if(p[cur].lazy!=-1)
{
p[cur<<1].lcol=p[cur<<1|1].lcol=p[cur<<1].rcol=p[cur<<1|1].rcol=p[cur].lazy;
p[cur<<1].num=p[cur<<1|1].num=1;
p[cur<<1].lazy=p[cur<<1|1].lazy=p[cur].lazy;
p[cur].lazy=-1;
}
}
inline void pushup(int cur)
{
p[cur].lcol=p[cur<<1].lcol;p[cur].rcol=p[cur<<1|1].rcol;
p[cur].num=p[cur<<1].num+p[cur<<1|1].num;
if(p[cur<<1].rcol==p[cur<<1|1].lcol) p[cur].num--;
}
inline void build(int l,int r,int cur)
{
p[cur].l=l;
p[cur].r=r;
p[cur].num=0;p[cur].lazy=-1;
if(l==r)
{
scanf("%d",&p[cur].lcol);
p[cur].rcol=p[cur].lcol;
p[cur].num=1;
return ;
}
int mid=l+r>>1;
build(l,mid,cur<<1);
build(mid+1,r,cur<<1|1);
pushup(cur);
}
inline void update(int l,int r,int cur,int col)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r)
{
p[cur].lcol=p[cur].rcol=col;
p[cur].num=1;
p[cur].lazy=col;
return ;
}
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) update(l,r,cur<<1,col);
else if(l>mid) update(l,r,cur<<1|1,col);
else update(l,mid,cur<<1,col),update(mid+1,r,cur<<1|1,col);
pushup(cur);
}
inline node query(int l,int r,int cur)
{
int L=p[cur].l;
int R=p[cur].r;
if(l<=L&&R<=r) return p[cur];
pushdown(cur);
int mid=L+R>>1;
if(r<=mid) return query(l,r,cur<<1);
else if(l>mid) return query(l,r,cur<<1|1);
else
{
node c;
node a=query(l,mid,cur<<1);
node b=query(mid+1,r,cur<<1|1);
if(a.rcol==b.lcol) c.num=a.num+b.num-1;
else c.num=a.num+b.num;
c.lcol=a.lcol;
c.rcol=b.rcol;
return c;
}
}
int main()
{
int op,x,y,c;
while(~scanf("%d%d",&n,&m))
{
build(1,n,1);
while(m--)
{
scanf("%d",&op);
if(op==1) scanf("%d%d%d",&x,&y,&c),update(x,y,1,c);
else
{
scanf("%d%d",&x,&y);if(x>y) swap(x,y);
printf("%d\n",query(x,y,1).num);
}
}
}
return 0;
}
努力加油a啊，(o)/~