洛谷 P2486 【SDOI2011】染色 题解

洛谷 P2486 【SDOI2011】染色 题解

2020-3-8 xiaoh

题意

给定一棵有$n$个节点的树($1\leq n\leq 10^5$).每个节点上都有一种颜色$c$($1\leq c\leq 10^9$),接下来要求你实现以下两种共$m$个($1\leq m\leq 10^5$)操作:

$1.$将两点间的路径全部改为颜色$c$;

$2.$求两点间”颜色段“的数量.

题解

当我们看到链上操作,以及那个熟悉的$10^5$时，就可以确定本题是树链剖分了.对于线段树,我们维护区间内颜色段的数量,以及颜色段的左右端点.每次pushup时要检查,若左区间的右端点$=$右区间的左端点,那么就要把颜色段数量$-1$.这样就可以高效的维护和查询信息.接下来在树剖沿着重链往上跳时,采用相仿的操作判断即可,注意当两个节点在同一重链上时,需要同时判断链的两端是否需要$-1$.时间复杂度$O(n+m\log^2 n)$.当然,本题的线段树常数并不大,加上数据很弱,可以轻松过去.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int 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^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010;
int n,m;
int a[MAXN];
int tot=1;
int edge[MAXN*2],nxt[MAXN*2],hd[MAXN];
inline void add_edge(int u,int v)
{
    edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
int son[MAXN],fa[MAXN],d[MAXN],sz[MAXN],top[MAXN],id[MAXN],rk[MAXN];
void dfs1(int p,int f,int dep)
{
    fa[p]=f,d[p]=dep,sz[p]=1;
    for(int i=hd[p];i;i=nxt[i])
    if(edge[i]!=f)
    {
        dfs1(edge[i],p,dep+1);
        sz[p]+=sz[edge[i]];
        if(sz[edge[i]]>sz[son[p]]) son[p]=edge[i];
    }
}
int cnt=0;
void dfs2(int p,int tp)
{
    top[p]=tp;
    id[p]=++cnt,rk[cnt]=p;
    if(son[p]) dfs2(son[p],tp);
    for(int i=hd[p];i;i=nxt[i])
    if(edge[i]!=fa[p]&&edge[i]!=son[p]) dfs2(edge[i],edge[i]);
}
struct node{
    int l,r;
    int num,ls,rs;
    int tag;
}f[MAXN*4];
inline void pushup(int p)
{
    f[p].num=f[p<<1].num+f[p<<1|1].num;
    if(f[p<<1].rs==f[p<<1|1].ls) f[p].num--;
    f[p].ls=f[p<<1].ls,f[p].rs=f[p<<1|1].rs;
}
inline void pushdown(int p)
{
    if(!f[p].tag) return;
    f[p<<1].ls=f[p<<1].rs=f[p<<1|1].ls=f[p<<1|1].rs=f[p].tag;
    f[p<<1].num=f[p<<1|1].num=1,f[p<<1].tag=f[p<<1|1].tag=f[p].tag;
    f[p].tag=0;
}
void build(int p,int l,int r)
{
    f[p].l=l,f[p].r=r;
    if(l==r)
    {
        f[p].num=1;
        f[p].ls=f[p].rs=a[rk[l]];
        return;
    }
    int mid=(f[p].l+f[p].r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int c)
{
    if(f[p].l>=l&&f[p].r<=r)
    {
        f[p].ls=f[p].rs=c;
        f[p].num=1;
        f[p].tag=c;
        return;
    }
    pushdown(p);
    int mid=(f[p].l+f[p].r)>>1;
    if(l<=mid) modify(p<<1,l,r,c);
    if(r>mid) modify(p<<1|1,l,r,c);
    pushup(p);
}
struct node2{
    int l,r,num;
};
node2 query(int p,int l,int r)
{
    if(f[p].l>=l&&f[p].r<=r) return {f[p].ls,f[p].rs,f[p].num};
	pushdown(p);
    node2 ret={0,0,0};
    int mid=(f[p].l+f[p].r)>>1;
    if(l<=mid)
    {
        ret=query(p<<1,l,r);
        if(r>mid)
        {
            node2 tmp=query(p<<1|1,l,r);
            ret.num+=tmp.num;
            if(ret.r==tmp.l) ret.num--;
            ret.r=tmp.r;
        }
    }
    else ret=query(p<<1|1,l,r);
    return ret;
}
inline void solve1(int x,int y,int c)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        modify(1,id[top[x]],id[x],c);
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    modify(1,id[x],id[y],c);
}
inline int solve2(int x,int y)
{
    int ans=0;
    int c1=-1,c2=-1;
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y),swap(c1,c2);
        node2 tmp=query(1,id[top[x]],id[x]);
        ans+=tmp.num;
        if(c1==tmp.r) ans--;
        c1=tmp.l;
        x=fa[top[x]];
    }
    if(id[x]>id[y]) swap(x,y),swap(c1,c2);
    node2 tmp=query(1,id[x],id[y]);
    ans+=tmp.num;
    if(c1==tmp.l) ans--;
    if(c2==tmp.r) ans--;
    return ans;
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        read(u),read(v);
        add_edge(u,v),add_edge(v,u);
    }
    dfs1(1,-1,1),dfs2(1,1),build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        char op[2];
        scanf("%s",op);
        if(op[0]=='C')
        {
            int a,b,c;
            read(a),read(b),read(c);
            solve1(a,b,c);
        }
        else
        {
            int a,b;
            read(a),read(b);
            write(solve2(a,b)),putchar('\n');
        }
    }
	return 0;
}

后记

其实本题的难度并不大,是没什么写题解的必要的.不过为什么要写呢？因为本题笔者不但写了两次(第一次写挂了……),第二次要拿标称对拍了好久才写出来,最后发现是愚蠢的pushdown写挂了.故写题解记这件愚蠢的事情.