2243. [SDOI2011]染色【树链剖分】

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

3
1
2

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

一眼：链剖
两眼：链剖+两个区间相邻处特判
和学长说了一句：感觉不是很难写（flag）
然后我处理的时候是直接当区间修改时用for循环将线段树区间更新
……正确性当然可以保证啦……出乎意料的是并没有T飞……就T了一个点
去隔壁请教了学长被告知要维护线段树的两端颜色……
于是开始了漫长的调试……
其实这个题只要想到了维护两端的值就很好搞了啊……
哪怕像我想不到维护两端也有95可拿对不对【滑稽】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAX (150000+5)
using namespace std;
struct node
{
    int down;//下传标记
    int sum;//该区间有几种颜色
    int l,r;//该区间左右端点的颜色
} Segt[MAX*4];
struct node1
{
    int to;
    int next;
} edge[MAX*2];
int Father[MAX],Depth[MAX];
int Sum[MAX],Son[MAX],Top[MAX];
int TREE[MAX],T_NUM[MAX];
int num_edge,head[MAX],n,cnt;
int a[MAX];

inline int get()//神TM快读，维护左右颜色前卡常用的但没卡过去
{
    char c;
    int x=0,f=1;
    c=getchar();
    while (c<'0'||c>'9')
    {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

void add(int u,int v)
{
    edge[++num_edge].to=v;
    edge[num_edge].next=head[u];
    head[u]=num_edge;
}

void Build(int node,int l,int r)
{
    if (l==r)
    {
        Segt[node].sum=1;
        Segt[node].l=Segt[node].r=TREE[l];
    }
    else
    {
        int mid=(l+r)/2;
        Build(node*2,l,mid);
        Build(node*2+1,mid+1,r);//这里维护好麻烦啊……早知道写个pushup了
        Segt[node].l=Segt[node*2].l;
        Segt[node].r=Segt[node*2+1].r;
        Segt[node].sum=Segt[node*2].sum+Segt[node*2+1].sum-(Segt[node*2].r==Segt[node*2+1].l);
    }
}

void Pushdown(int node)
{
    if (Segt[node].down!=0)
    {
        Segt[node*2].sum=1;//因为修改成了一个数所以肯定只有一种颜色
        Segt[node*2+1].sum=1;

        Segt[node*2].down=Segt[node].down;//down存下传的颜色编号
        Segt[node*2+1].down=Segt[node].down;

        Segt[node*2].l=Segt[node*2].r=Segt[node].down;
        Segt[node*2+1].l=Segt[node*2+1].r=Segt[node].down;

        Segt[node].down=0;
    }
}

int Query(int node,int l,int r,int l1,int r1)
{
    if (r<l1 || l>r1)
        return 0;
    if (l1<=l && r<=r1)
        return Segt[node].sum;
    Pushdown(node);
    int mid=(l+r)/2;
    int x=Query(node*2,l,mid,l1,r1);
    int y=Query(node*2+1,mid+1,r,l1,r1);
    if (x!=0 && y!=0)
        return x+y-(Segt[node*2].r==Segt[node*2+1].l);
    return max(x,y);
}

void Update(int node,int l,int r,int l1,int r1,int k)//区间更新模板
{
    if (r<l1 || l>r1)
        return;
    if (l1<=l && r<=r1)
    {
        Segt[node].down=k;
        Segt[node].sum=1;
        Segt[node].l=Segt[node].r=k;
        return;
    }
    Pushdown(node);
    int mid=(l+r)/2;
    Update(node*2,l,mid,l1,r1,k);
    Update(node*2+1,mid+1,r,l1,r1,k);//再一次后悔没写pushup
    Segt[node].l=Segt[node*2].l;
    Segt[node].r=Segt[node*2+1].r;
    Segt[node].sum=Segt[node*2].sum+Segt[node*2+1].sum-(Segt[node*2].r==Segt[node*2+1].l);
}

int Ask(int node,int l,int r,int x)//查询某个点的颜色
{
    if (l==r)
        return Segt[node].l;
    else
    {
        Pushdown(node);
        int mid=(l+r)/2;
        if (x<=mid)    return Ask(node*2,l,mid,x);
        else return Ask(node*2+1,mid+1,r,x);
    }
}

int Get(int x,int y)
{
    int fx=Top[x],fy=Top[y];
    int Ans=0;
    while (fx!=fy)
    {
        if (Depth[fx]<Depth[fy])
            swap(fx,fy),swap(x,y);
        int re=Ask(1,1,n,T_NUM[fx]);
        int fun=Ask(1,1,n,T_NUM[Father[fx]]);
        Ans+=Query(1,1,n,T_NUM[fx],T_NUM[x])-(re==fun);
        x=Father[fx],fx=Top[x];
    }
    if (Depth[x]<Depth[y])
        swap(x,y);
    return Ans+=Query(1,1,n,T_NUM[y],T_NUM[x]);
}

void Change(int x,int y,int k)
{
    int fx=Top[x],fy=Top[y];
    while (fx!=fy)
    {
        if (Depth[fx]<Depth[fy])
            swap(fx,fy),swap(x,y);
        Update(1,1,n,T_NUM[fx],T_NUM[x],k);
        x=Father[fx],fx=Top[x];
    }
    if (Depth[x]<Depth[y])
        swap(x,y);
    Update(1,1,n,T_NUM[y],T_NUM[x],k);
}

void Dfs1(int x)
{
    Depth[x]=Depth[Father[x]]+1;
    Sum[x]=1;
    for (int i=head[x]; i!=0; i=edge[i].next)
        if (edge[i].to!=Father[x])
        {
            Father[edge[i].to]=x;
            Dfs1(edge[i].to);
            Sum[x]+=Sum[edge[i].to];
            if (Son[x]==0 || Sum[Son[x]]<Sum[edge[i].to])
                Son[x]=edge[i].to;
        }
}

void Dfs2(int x,int pre)
{
    TREE[++cnt]=a[x];
    T_NUM[x]=cnt;
    Top[x]=pre;
    if (Son[x]!=0)
        Dfs2(Son[x],pre);
    for (int i=head[x]; i!=0; i=edge[i].next)
        if (edge[i].to!=Son[x] && edge[i].to!=Father[x])
            Dfs2(edge[i].to,edge[i].to);
}

int main()
{
    char ch;
    int x,y,k,m,u,v;
    n=get();
    m=get();
    for (int i=1; i<=n; ++i)
        a[i]=get();
    for (int i=1; i<=n-1; ++i)
    {
        u=get();
        v=get();
        add(u,v);
        add(v,u);
    }
    Dfs1(1);
    Father[1]=1;
    Dfs2(1,1);
    Build(1,1,n);
    for (int i=1; i<=m; ++i)
    {
        ch=getchar();
        while (ch!='C'&&ch!='Q') ch=getchar();
        if (ch=='Q')
            x=get(),y=get(),printf("%d
",Get(x,y));
        else
            x=get(),y=get(),k=get(),Change(x,y,k);
    }
}