BZOJ 2243 SDOI2011 染色

2243: [SDOI2011]染色

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 10135  Solved: 3868
[Submit][Status][Discuss]

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

一眼就看出是树剖+线段树
线段树需要维护cl，cr分别表示最左端和最右端分别是什么
合并就是T[rt].sum=T[rt<<1].sum+T[rt<<1|1].sum-(T[rt<<1].cr==T[rt<<1|1].cl)
因为在树链上往上跳的时候dfs序在减小   所以在树链上跳的时候拿一个变量来记录上个区间最左端的是什么 并在线段树查询的时候求一下当前链区间的右端是什么
如果左端==右端 那么这两个区间的连续相同区间个数就是ans1+ans2-1 否则的话就是ans1+ans2
然后依次向上计算即可
/**************************************************************
    Problem: 2243
    User: zhangenming
    Language: C++
    Result: Accepted
    Time:7164 ms
    Memory:139476 kb
****************************************************************/
 
#include <bits/stdc++.h>
#define ll long long
#define inf 1e9+10
using namespace std;
inline int read(){
    int x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN=1e6+10;
struct node{
    int y,next;
}e[MAXN];
int linkk[MAXN],len,n,m,dfn[MAXN],dfs_clock,son[MAXN],siz[MAXN],x,y,v,top[MAXN],f[MAXN][21],ansl,ansr,ans,dep[MAXN],val[MAXN],low[MAXN];
inline void insert(int x,int y){
    e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;
}
inline void dfs1(int x,int fa){
    f[x][0]=fa;siz[x]=1;dep[x]=dep[fa]+1;
    for(int i=linkk[x];i;i=e[i].next){
        if(e[i].y!=fa){
            dfs1(e[i].y,x);siz[x]+=siz[e[i].y];
            if(!son[x]) son[x]=e[i].y;
            else if(siz[e[i].y]>siz[son[x]]) son[x]=e[i].y;
        }
    }
}
inline void dfs2(int x,int fa){
    dfn[x]=++dfs_clock;top[x]=fa;low[dfs_clock]=x;
    if(son[x]) dfs2(son[x],fa);
    for(int i=linkk[x];i;i=e[i].next){
        if(e[i].y!=fa&&!dfn[e[i].y]){
            dfs2(e[i].y,e[i].y);
        }
    }
}
inline void getanser(){
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
}
inline int lca(int x,int y){
    if(x==y) return x;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[x]-(1<<i)>=dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]&&f[x][i]!=0){
            x=f[x][i];y=f[y][i];
        }
    }
    return f[x][0];
}
struct sig{
    int cl,cr,sum,tag;
}T[MAXN];
inline void update(int rt){
    T[rt].sum=T[rt<<1].sum+T[rt<<1|1].sum;
    if(T[rt<<1].cr==T[rt<<1|1].cl) T[rt].sum--;
    T[rt].cl=T[rt<<1].cl;T[rt].cr=T[rt<<1|1].cr;
}
inline void downit(int rt){
    if(T[rt].tag!=-1){
        T[rt<<1].tag=T[rt<<1|1].tag=T[rt].tag;
        T[rt<<1].sum=1;T[rt<<1].cl=T[rt<<1].cr=T[rt].tag;
        T[rt<<1|1].sum=1;T[rt<<1|1].cl=T[rt<<1|1].cr=T[rt].tag;
        T[rt].tag=-1;
    }
}
inline void build(int l,int r,int rt){
    if(l==r){
        T[rt].sum=1;T[rt].cl=T[rt].cr=val[low[l]];
        T[rt].tag=-1;return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    T[rt].tag=-1;update(rt);
}
inline void insert(int l,int r,int rt){
    if(l!=r) downit(rt);
    if(l>=x&&r<=y){
        T[rt].sum=1;T[rt].cl=T[rt].cr=T[rt].tag=v;
        return;
    }
    if(l>y||r<x) return;
    int mid=(l+r)>>1;
    insert(l,mid,rt<<1);
    insert(mid+1,r,rt<<1|1);
    update(rt);
}
inline void query(int l,int r,int rt){
    if(l!=r) downit(rt);
    if(l>=x&&r<=y){
        if(ansl==-1) ansl=T[rt].cl,ansr=T[rt].cr,ans+=T[rt].sum;
        else{
            ans+=T[rt].sum;
            if(T[rt].cl==ansr) ans--;
            ansr=T[rt].cr;
        }
        return;
    }
    if(l>y||r<x) return;
    int mid=(l+r)>>1;
    query(l,mid,rt<<1);
    query(mid+1,r,rt<<1|1);
}
inline void change(){
    int a=read();int b=read();v=read();
    int t=lca(a,b);
    while(top[a]!=top[t]){
        x=dfn[top[a]],y=dfn[a];
        insert(1,n,1);a=f[top[a]][0];
    }
    x=dfn[t];y=dfn[a];insert(1,n,1);
    while(top[b]!=top[t]){
        x=dfn[top[b]],y=dfn[b];
        insert(1,n,1);b=f[top[b]][0];
    }
    x=dfn[t];y=dfn[b];insert(1,n,1);
}
inline void getsum(){
    int a=read();int b=read();
    int t=lca(a,b);int sum=0;
    int l=-1;
    while(top[a]!=top[t]){
        x=dfn[top[a]];y=dfn[a];ansl=ansr=-1;ans=0;
        query(1,n,1);a=f[top[a]][0];
        if(l==-1){
            l=ansl;sum+=ans;
        }
        else{
            sum+=ans;
            if(l==ansr) sum--;
            l=ansl;
        }
    }
    ansl=ansr=-1;ans=0;
    x=dfn[t];y=dfn[a];query(1,n,1);
    if(l==-1){
        l=ansl;sum+=ans;
    }
    else{
        sum+=ans;
        if(l==ansr) sum--;
        l=ansl;
    }
    l=-1;
    while(top[b]!=top[t]){
        x=dfn[top[b]];y=dfn[b];ansl=ansr=-1;ans=0;
        query(1,n,1);b=f[top[b]][0];
        if(l==-1){
            l=ansl;sum+=ans;
        }
        else{
            sum+=ans;
            if(l==ansr) sum--;
            l=ansl;
        }
    }
    ansl=ansr=-1;ans=0;
    x=dfn[t];y=dfn[b];query(1,n,1);
    if(l==-1){
        l=ansl;sum+=ans;
    }
    else{
        sum+=ans;
        if(l==ansr) sum--;
        l=ansl;
    }
    sum--;printf("%d
",sum); 
}
int main(){
    //freopen("All.in","r",stdin);
    //freopen("All.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++){
        val[i]=read();
    }
    for(int i=1;i<n;i++){
        int x=read();int y=read();
        insert(x,y);insert(y,x);
    }
    dfs1(1,0);dfs2(1,1);
    getanser();char ch[5];
    build(1,n,1);
    for(int i=1;i<=m;i++){
        scanf("%s",ch);
        if(ch[0]=='Q'){
            getsum();
        }
        else change();
    }
    return 0;
}

　　

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/something-for-nothing/p/9352004.html