Codevs1191數軸染色

http://codevs.cn/problem/1191/

思路

方法一：線段樹

顯然線段樹可以很友善的維護區間内黑色點的數量，我們在每次染色之前求一下染色區間内黑色點的個數，即為此次染色後将要減少的黑色點的個數，用目前總個數作差即為答案。染色過程當然也為線段樹的區間修改。

線段樹代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,anz;
int ls,rs;
struct inte
{
    int l,r;
    int A;//black
    int add;
}tree[];
void pushdown(int now)
{
    if(tree[now].add)
    {
        tree[now<<].A=;
        tree[now<<|].A=;
        tree[now<<].add=;
        tree[now<<|].add=;
        tree[now].add=;
    }
}
void update(int now)
{
    tree[now].A=tree[now<<].A+tree[now<<|].A;
}
void build(int now,int l,int r)
{
    tree[now].l=l;
    tree[now].r=r;
    if(l==r)
    {
        tree[now].A=;
        return;
    }
    int mid=(l+r)>>;
    build(now<<,l,mid);
    build(now<<|,mid+,r);
    update(now);
}
int ask_col(int now,int l,int r)
{
    if(tree[now].l>=l&&tree[now].r<=r)
    {
        return tree[now].A;
    }
    pushdown(now);
    int mid=(tree[now].l+tree[now].r)>>;
    int ans=;
    if(l<=mid)
    ans+=ask_col(now<<,l,r);
    if(r>mid)
    ans+=ask_col(now<<|,l,r);
    return ans;
}
void change(int now,int l,int r)
{
    if(tree[now].l>=l&&tree[now].r<=r)
    {
        tree[now].A=;
        tree[now].add=;
        return;
    }
    pushdown(now);
    int mid=(tree[now].l+tree[now].r)>>;
    if(l<=mid)
    change(now<<,l,r);
    if(r>mid)
    change(now<<|,l,r);
    update(now);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(,,n);
    anz=n;
    for(int i=;i<=m;i++)
    {
        scanf("%d%d",&ls,&rs);
        printf("%d\n",anz-=ask_col(,ls,rs));
        change(,ls,rs);
    }
    return ;
}
           

方法二：并查集

我們在得到一個區間後，由區間左端點開始，嘗試直接跳到在其右邊的第一個黑色點上去，這樣我們就可以快速找到區間中未被染色的點然後依次一個一個統計。也就是說對于數軸上的每個點，我們都需要一個指針指向☞其右邊的第一個黑色點，如果這個黑色點後來被染色了，說明其右邊的第一個黑色點在數軸上的位置右移了，我們需要重新将指針指向新位置。

說到這樣….應該會想到并查集了（或者或者也可以吧fa數組了解為一個連結清單…）。

并查集的路徑壓縮可以維護指針的右移（或者或者也可以了解為連結清單的跳鍊重連…）。

對于未染過色的點，有一個比較巧妙的方法是将其fa設定為下一位置的點，這樣在需要查詢此點右邊的第一個黑色點時，路徑壓縮便可找到最終位置。

代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,ls,rs,ans;
int fa[];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    ans=n;
    for(int i=;i<=n+;i++)//n向後連向n+1的位置
    fa[i]=i;
    for(int i=;i<=m;i++)
    {
        scanf("%d%d",&ls,&rs);
        for(int j=ls;j<=rs;j=find(j))//巧妙寫法
        {
            if(fa[j]==j)
            {
                fa[j]=j+;
                ans--;
            }
        }
        printf("%d\n",ans);
    }
}