程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj 2243 染色樹鏈剖分好題！

bzoj 2243 染色樹鏈剖分好題！

編輯：關於C++

題意：中文題。

思路：很好的一道樹鏈剖分。樹剖後，線段樹要記錄左端點l,右端點r，左端點的顏色lc,右端點的顏色rc,區間成段更新的標記tag,區間

有多少顏色段。區間合並的時候要注意如果左子樹的右端和右子樹的左端顏色相同那麼數量要減一。但是存在一個問題當前剖到

的鏈與上一次的鏈在相交的邊緣可能顏色相同，如果顏色相同答案需要減一。所以統計答案的時候要記錄下上一次剖到的鏈的左端

點的顏色，與當前剖到的鏈右端點的顏色（因為在處理出的線段樹中越靠近根的點位置越左），比較這兩個顏色，若相同則答案減

1。又由於有u和v兩個位置在向上走，那麼要記錄ans1，ans2兩個變量來存“上一次的左端點顏色”。有一點需要注意，當

top[u]=top[v]的時候，即已經在同一個重鏈上時，兩邊端點顏色都要考慮與對應ans比較顏色，相同答案要相應減一。詳見代碼：

/*********************************************************
  file name: bzoj2243.cpp
  author : kereo
  create time:  2015年01月23日 星期五 09時51分17秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
int n,m,edge_cnt,cnt,Lc,Rc;
char str[N];
int col[MAXN],head[MAXN],sz[MAXN],dep[MAXN],fa[MAXN],son[MAXN],top[MAXN],pos[MAXN];
struct Edge{
    int u,v,next;
}edge[MAXN<<1];
struct node{
    int l,r;
    int num,tag,lc,rc;
}segtree[MAXN<<2];
void init(){
    edge_cnt=cnt=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
    edge[edge_cnt].u=u; edge[edge_cnt].v=v;
    edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;
}
void dfs1(int u,int pre,int depth){
    sz[u]=1; fa[u]=pre; son[u]=0; dep[u]=depth;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v == pre)
            continue;
        dfs1(v,u,depth+1);
        sz[u]+=sz[v];
        if(sz[son[u]]>1;
    build(L(rt),l,mid); build(R(rt),mid+1,r);
}
void update(int rt,int l,int r,int x){
    if(segtree[rt].l == l && segtree[rt].r == r){
        segtree[rt].num=segtree[rt].tag=1;
        segtree[rt].lc=segtree[rt].rc=x;
        return ;
    }
    push_down(rt);
    int mid=(segtree[rt].l+segtree[rt].r)>>1;
    if(r<=mid)
        update(L(rt),l,r,x);
    else if(l>mid)
        update(R(rt),l,r,x);
    else {
        update(L(rt),l,mid,x); update(R(rt),mid+1,r,x);
    }
    push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(segtree[rt].l == L)
        Lc=segtree[rt].lc;
    if(segtree[rt].r == R)
        Rc=segtree[rt].rc;
    if(segtree[rt].l == l && segtree[rt].r == r)
        return segtree[rt].num;
    push_down(rt);
    int mid=(segtree[rt].l+segtree[rt].r)>>1;
    if(r<=mid)
        return query(L(rt),l,r,L,R);
    else if(l>mid)
        return query(R(rt),l,r,L,R);
    else{
        int ans=query(L(rt),l,mid,L,R)+query(R(rt),mid+1,r,L,R);
        if(segtree[L(rt)].rc == segtree[R(rt)].lc)
            ans--;
        return ans;
    }
    push_up(rt);
}
int solve(int u,int v,int id,int c){
    int ans=0;
    if(id == 1){
        while(top[u]!=top[v]){
            if(dep[top[u]]dep[v])
            swap(u,v);
        update(1,pos[u],pos[v],c);
    }
    else{
        //printf("u=%d v=%d pos[u]=%d pos[v]=%d\n",u,v,pos[u],pos[v]);
        int ans1=-1,ans2=-1; //記錄上次鏈的左端的顏色
        while(top[u]!=top[v]){
            if(dep[top[u]]printf("%d %d\n",son[1],son[2]);
        /*for(int i=1;i<=n;i++)
            printf("top[i]=%d pos[i]%d\n",top[i],pos[i]);
        printf("---------------------------------------\n");
        printf("\n");*/
        for(int i=1;i<=n;i++)
            update(1,pos[i],pos[i],col[i]);
        while(m--){
            scanf("%s",str);
            int u,v;
            if(str[0] == 'C'){
                int c;
                scanf("%d%d%d",&u,&v,&c);
                solve(u,v,1,c);
            }
            else{
                int u,v;
                scanf("%d%d",&u,&v);
                printf("%d\n",solve(u,v,2,0));
                //printf("--------------------------------------\n");
            }
        }
    }
	return 0;
}