poj 2528 Mayor's posters(動態線段樹)

poj 2528 Mayor's posters(動態線段樹)

傳送門：點擊打開鏈接

題目大意：

給定一個 1 ~ 10000000 的區間，然後有N次操作（N <= 10000），第i次操作是將 l~r 區間覆蓋為i。問最後一共有多少種有顏色。

解題思路：

一開始想到了離散化，但是想了一想感覺有點麻煩 然後就問專職搞數據結構的隊友。然後他說了 動態線段樹。思路如下：

定義一個ID。然後 根節點1表示掌管1-MAXN顏色的區間。然後每次都是動態的建樹。當一個區間的左子區間還不存在時。建立它，並且記錄下每個區間的左子區間和右子區間的ID.那麼就可以搞了。

最後再用一個DFS 用SET來記錄一共出現了多少種顏色。

注意:

當將一個區間的左子區間和右子區間被它更新之後時，一定要把他清零。

還有那個maxn。開始是未知的。

#include 
#include 
using namespace std;
#define maxn 2000000
int lson[maxn],rson[maxn],color[maxn];
int cnt,root;
void build()
{
    cnt = 2;
    root = 1;
    lson[root] = 0;
    rson[root] = 0;
    color[root] = 0;
}

void pushdown(int id)
{
    if(!lson[id])
    {
        lson[id] = cnt++;
        lson[lson[id]] = 0;
        rson[lson[id]] = 0;
        color[lson[id]] = 0;
    }
    if(!rson[id])
    {
        rson[id] = cnt++;
        lson[rson[id]] = 0;
        rson[rson[id]] = 0;
        color[rson[id]] = 0;
    }
    if(color[id])
    {
        color[lson[id]] = color[id];
        color[rson[id]] = color[id];
        color[id] = 0;
    }
}

void op(int id,int ls,int rs,int l,int r,int c)
{
    if(ls >= l && rs <= r)
    {
        color[id] = c;
        return;
    }
    pushdown(id);
    int mid = (ls+rs)>>1;
    if(l <= mid) op(lson[id],ls,mid,l,r,c);
    if(mid < r) op(rson[id],mid+1,rs,l,r,c);

}
set ans;

void dfs(int id)
{
    if(color[id])
    {
        ans.insert(color[id]);
        return;
    }
    if(lson[id]) dfs(lson[id]);
    if(rson[id]) dfs(rson[id]);
}


int main()
{
    int T;
    scanf("%d",&T);
    for(int ks = 1;ks <= T;ks++)
    {
        int n;
        scanf("%d",&n);
        ans.clear();
        build();
        for(int i = 1;i <= n;i++)
        {
            int l,r;
            scanf("%d %d",&l,&r);
            op(root,1,10000000,l,r,i);
        }
        dfs(root);
        printf("%d\n",ans.size());
    }
    return 0;
}