程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 【bzoj2243】[SDOI2011]染色樹鏈剖分(區間合並處理)

【bzoj2243】[SDOI2011]染色樹鏈剖分(區間合並處理)

編輯:關於C語言

【bzoj2243】[SDOI2011]染色樹鏈剖分(區間合並處理)


2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 5143 Solved: 1919
[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

對於每個詢問操作,輸出一行答案。

數N<=10^5,操作數M<=10^5,所有的顏色C為整數且在[0, 10^9]之間。

題意
一顆樹,節點各有顏色,1.修改區間顏色;2.詢問區間的顏色段數;

思路
1.區間操作--》線段樹;
2.給棵樹--》樹剖(dfs*2 找重鏈,賦樹剖的序);
3.詢問連續區間段數:
用線段樹節點維護的信息:
1.num本段區間個數;
2.l本段左端顏色;
3.r本段右端顏色;
(用於判定區間合並的處理)

if(t[lson].r==t[rson].l) t[id].num--;

*注意顏色可為0,故*lazy初始-1,或col++;

代碼

#include
#include
#include
#include
#define lson (id*2)
#define rson (id*2+1)
using namespace std;
int n,m;
struct node{
    int l,r,num;
    int lazy;
}t[800005];
vector lin[100005];
int xx,yy;
int a[100005],b[100005];
int in[100005],out[100005];
int size[100005];
int dep[100005];
int ans;
int top[100005];
int son[100005];
int fa[100005];
int tot;
void dfs1(int id,int pre)//找重鏈
{
    fa[id]=pre;
    size[id]=1;
    son[id]=-1;
    dep[id]=dep[pre]+1;
    int len=lin[id].size();
    for(int i=0;iR||r=l&&R<=r)
    {


        t[id].l=t[id].r=v;
        t[id].num=1;
        t[id].lazy=v;
        return ;
    }

    int mid=(L+R)>>1;
    push_down(id);
    add(lson,L,mid,l,r,v);
    add(rson,mid+1,R,l,r,v);
    push_up(id);
}
void query(int id,int L,int R,int l,int r,int ttt)
{

    if(l>R||r=l&&R<=r)
    {

        if(ttt!=2)
        ans+=t[id].num;

        if(L==R) 
        xx=t[id].l;
        return ;
    }
    int mid=(L+R)>>1;
    push_down(id);
    if(r<=mid) query(lson,L,mid,l,r,ttt);
    else if(l>mid)
    query(rson,mid+1,R,l,r,ttt);
    else
    {
        if(t[lson].r==t[rson].l) ans--;//區間連接處!
        query(lson,L,mid,l,r,ttt);
        query(rson,mid+1,R,l,r,ttt);
    }
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        t[id].num=1;

        t[id].l=t[id].r=b[l];

        return ;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    push_up(id);

}
int main()
{
    int aa,bb,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]++;
    }
    for(int i=1;idep[bb]) swap(aa,bb);        
            add(1,1,tot,in[aa],in[bb],v);


        }
        if(s[0]=='Q')
        {
            ans=0;
            scanf("%d%d",&aa,&bb);

            while(top[aa]!=top[bb])
            {               

                if(dep[top[aa]]dep[bb]) swap(aa,bb);
            query(1,1,tot,in[aa],in[bb],1);
            printf("%d\n",ans);
        }
    }
}
   

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved