淘先锋技术网

首页 1 2 3 4 5 6 7

Bzoj 2243: [SDOI2011]染色(树链剖分+线段树)

2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MB
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]之间。
Source
第一轮day1

/*
树链剖分+线段树.
读入操作的时候要用ch[] scanf 读入(又被卡了).
这还是shenben告诉我的%%%.
以为用树剖搞贡献可能无法处理衔接点.
然后就yy了一种类似于暴力的做法.
倍增处理出lca然后跳链.
一开始只能得分不知道为啥(写的很鬼畜~).
原来是没写lca是链顶的情况.
网上大多数人的做法是处理区间贡献
然后单点查询判断端点情况,
一开始因为想到找链的时候两个点蹦跶可能不好处理端点
然后就没这样搞...
其实我们可以先处理出段点的贡献(还是有点晕~). 
通过这题还会了手动开栈.
我是找的lca然后分情况讨论乱搞.
这题线段树merge什么的都还好.
还有几个需要注意的地方:
build tree 标号,update &&pushtag.
最重要的是读入读入读入！！！
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 100001
using namespace std;
struct data{int l,r,lc,rc,sum,lans,rans,bj;}tree[MAXN<<];
struct edge{int v,next;}e[MAXN*2];
int n,m,cut,head[MAXN],a[MAXN];
int maxsize,size[MAXN],pos[MAXN],top[MAXN],deep[MAXN],fa[MAXN][];
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-,ch=getchar();
    return x*f;
}
void add(int u,int v)
{
    e[++cut].v=v;
    e[cut].next=head[u];
    head[u]=cut;
}
void update(int k)
{
    if(tree[tree[k].lc].rans==tree[tree[k].rc].lans)
        tree[k].sum=tree[tree[k].lc].sum+tree[tree[k].rc].sum-;
    else tree[k].sum=tree[tree[k].lc].sum+tree[tree[k].rc].sum;
    tree[k].lans=tree[tree[k].lc].lans;tree[k].rans=tree[tree[k].rc].rans;
    return ;
}
void push(int k)
{
    tree[tree[k].lc].bj=tree[tree[k].rc].bj=tree[k].bj;
    tree[tree[k].lc].lans=tree[tree[k].lc].rans=tree[k].bj;
    tree[tree[k].rc].lans=tree[tree[k].rc].rans=tree[k].bj;
    tree[tree[k].lc].sum=tree[tree[k].rc].sum=;
    tree[k].bj=;
    return ;
}
void build(int l,int r)
{
    int k=++cut;tree[k].l=l,tree[k].r=r;
    if(l==r) return ;// w.
    int mid=(l+r)>>;
    tree[k].lc=cut+;build(l,mid);
    tree[k].rc=cut+;build(mid+,r);
    update(k);return ;
}
void change(int k,int l,int r,int z)
{
    if(l<=tree[k].l&&tree[k].r<=r) {
        tree[k].sum=;
        tree[k].lans=tree[k].rans=z;
        tree[k].bj=z;
        return ;
    }
    if(tree[k].bj) push(k);
    int mid=(tree[k].l+tree[k].r)>>;
    if(l<=mid) change(tree[k].lc,l,r,z);
    if(r>mid) change(tree[k].rc,l,r,z);
    update(k);//２w.
    return ;
}
data query(int k,int l,int r)
{
    data xx;
    if(l<=tree[k].l&&tree[k].r<=r) return tree[k];
    if(tree[k].bj) push(k);
    int mid=(tree[k].l+tree[k].r)>>;
    if(l>mid) return query(tree[k].rc,l,r);
    else if(r<=mid) return query(tree[k].lc,l,r);
    else
    {
        data ll=query(tree[k].lc,l,mid);
        data rr=query(tree[k].rc,mid+,r);
        if(ll.rans==rr.lans) xx.sum=ll.sum+rr.sum-;
        else xx.sum=ll.sum+rr.sum;
        xx.lans=ll.lans,xx.rans=rr.rans;
    }
    update(k);
    return xx;
}
void dfs1(int u)
{
    size[u]=;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(!fa[v][]) fa[v][]=u,deep[v]=deep[u]+,dfs1(v),size[u]+=size[v];
    }
    return ;
}
void dfs2(int u,int top1)
{
    pos[u]=++maxsize;top[u]=top1;
    int k=;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(fa[v][]==u&&size[v]>size[k]) k=v;
    }
    if(!k) return ;
    dfs2(k,top1);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(fa[v][]==u&&v!=k) dfs2(v,v);
    }
    return ;
}
void slovechange(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        change(,pos[top[x]],pos[x],z);
        x=fa[top[x]][];
    }
    if(pos[x]>pos[y]) swap(x,y);
    change(,pos[x],pos[y],z);
    return ;
}
int get_same(int u,int v)
{
    for(int i=;i<=;i++)
      if(v&(<<i)) u=fa[u][i];
    return u;
}
int lca(int u,int v)
{
    if(deep[u]<deep[v]) swap(u,v);
    u=get_same(u,deep[u]-deep[v]);
    if(u==v) return u;
    for(int i=;i>=;i--)
    {
        if(fa[u][i]!=fa[v][i])
          u=fa[u][i],v=fa[v][i];
    }
    return fa[u][];
}
int get(int k,int x)
{
    if(tree[k].l==tree[k].r) return tree[k].lans;
    if(tree[k].bj) push(k);
    int mid=(tree[k].l+tree[k].r)>>;
    if(x<=mid) return get(tree[k].lc,x);
    else return get(tree[k].rc,x);
    update(k);
}
int slovequery(int x,int y)
{
    /*int ans=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        ans+=query(1,pos[top[x]],pos[x]).sum;
        if(get(1,pos[top[x]])==get(1,pos[fa[top[x]][0]])) ans--;
        x=fa[top[x]][0];
    }
    if(pos[x]>pos[y]) swap(x,y);
    ans+=query(1,pos[x],pos[y]).sum;
    return ans;*/
    data ans,ansl,ansr;
    int lc=lca(x,y);
    if(top[x]==top[y])
    {
        if(pos[x]>pos[y]) swap(x,y);
        ans=query(,pos[x],pos[y]);
        return ans.sum;
    }
    if(deep[lc]>deep[top[x]]||lc==top[x]) ansl=query(,pos[lc],pos[x]);
    else 
    {
        ansl=query(,pos[top[x]],pos[x]);x=fa[top[x]][];
        while(deep[lc]<deep[top[x]]) 
        {
            ans=query(,pos[top[x]],pos[x]);
            if(ans.rans==ansl.lans) ans.sum+=ansl.sum-;
            else ans.sum+=ansl.sum;
            ans.rans=ansl.rans;
            ansl=ans;
            x=fa[top[x]][];
        }
        ans=query(,min(pos[lc],pos[x]),max(pos[lc],pos[x]));
        if(ans.rans==ansl.lans) ans.sum+=ansl.sum-;
        else ans.sum+=ansl.sum;
        ans.rans=ansl.rans;
        ansl=ans;
    }
    if(deep[lc]>deep[top[y]]||lc==top[y]) ansr=query(,pos[lc],pos[y]);
    else
    {
        ansr=query(,pos[top[y]],pos[y]);y=fa[top[y]][];
        while(deep[lc]<deep[top[y]])
        {
            ans=query(,pos[top[y]],pos[y]);
            if(ans.rans==ansr.lans) ans.sum+=ansr.sum-;
            else ans.sum+=ansr.sum;
            ans.rans=ansr.rans;
            ansr=ans;
            y=fa[top[y]][];
        }
        ans=query(,min(pos[y],pos[lc]),max(pos[lc],pos[y]));
        if(ans.rans==ansr.lans) ans.sum+=ansr.sum-;
        else ans.sum+=ansr.sum;
        ans.rans=ansr.rans;
        ansr=ans;
    }
    if(ansl.lans==ansr.lans) ans.sum=ansl.sum+ansr.sum-;
    else ans.sum=ansl.sum+ansr.sum;
    return ans.sum;
}
void get_father()
{
    for(int j=;j<=;j++)
      for(int i=;i<=n;i++)
        fa[i][j]=fa[fa[i][j-]][j-];
    return ;
}
int main()
{
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    /*int ss=64<<20;
    char *p=(char *)malloc(ss)+ss;
    __asm__("movl %0, %%esp\n"::"r"(p));*/
    int x,y,z;char ch[];
    n=read(),m=read();
    for(int i=;i<=n;i++) a[i]=read();
    for(int i=;i<=n-;i++)
    {
        x=read(),y=read();
        add(x,y),add(y,x);
    }
    fa[][]=;dfs1(),dfs2(,);
    cut=;build(,n);
    for(int i=;i<=n;i++) change(,pos[i],pos[i],a[i]);
    get_father();
    for(int i=;i<=m;i++)
    {
        scanf("%s",ch);// n T.... 
        if(ch[]=='Q') x=read(),y=read(),printf("%d\n",slovequery(x,y));
        else {
            x=read(),y=read(),z=read();
            slovechange(x,y,z);
        }
    }
    return ;
}