[HOJ 150][POI 17 Stage 1] 鐵路

恩...這題我寫完AC了之後在證明作法的時候才發現我錯了OAO...我的作法有反例。

不過思路大概就是，先回去推原本只有一個軌道的那題的比較好看的充要條件，可以得到條件是：不存在三個數 i < j < k，滿足 a_j > a_i > a_k ，所以如果有這種情況出現在兩個軌道的情形的話， i 和 j 就必須要被放在不同的軌道中。於是我直接猜：兩個軌道的充要條件就是不存在四個數 i < j < k < l ，滿足 a_k > a_j > a_i > a_l (但這是錯的)。

如果考慮一張圖，頂點是1~n，然後如果有「 i 和 j 必須要被放在不同的軌道」這個限制就在 i , j 之間連一條邊，問題就轉化為判斷這張圖是不是二部圖。

但如果直接把圖建出來記憶體會不夠(也會TLE)，因為這樣的邊數會到O(n^2)，舉個簡單的測資： m+1 , m+2 , ... , n , 2 , 3 , ... , m , 1 ，其中 m 在 n/2 附近。至於要如何減少邊，首先我們可以不用先把圖全部建出來再判他是不是二部圖，而是可以一條邊一條邊加，用 disjoint set作動態的加邊，一有矛盾就退出之類的。另一個觀察是注意到，如果 a_(i+1) < a_i ，那麼 i+1 在 1 ~ i 所連的邊都已經被 i 連過了，所以可以只考慮 i+1 往前連的其中一條邊即可，這樣就加速很多了。

但我在寫這題的時候，以為前面我說的那個錯的充要條件是對的，所以在直接用那個條件 check 這數列有解之後就篤定他是二部圖，所以在 disjoint set 那邊沒有再判二部圖， 而且是建完整張圖後再DFS求答案(有加那個 a_(i+1) > a_i 的優化 )，正解應該是上面那樣做才對......不過既然都過了，那就懶的重寫一次正解了(炸

附上會讓上面那個條件爛掉的測資 : (答案應該是 NIE )

14
2 5 4 1 10 7 3 9 6 13 12 8 14 11

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
using namespace std;
const int maxn=100000+10 ;

int n,a[maxn],inv[maxn],mi[maxn] ;
set<int> sti ;
set<pii> st ;

void insert(const pii &p)
{
        st.insert(p) ;
        set<pii>::iterator it=st.find(p) ;
        bool keep=1 ;
        if(it!=st.begin())
        {
                it-- ;
                if(it->S > p.S) keep=0 ;
                it++ ;
        }
        if(!keep) { st.erase(it) ; return ; }

        while(1)
        {
                set<pii>::iterator it2=it ;
                it2++ ; if(it2==st.end()) break ;
                if(it2->S < p.S) st.erase(it2) ;
                else break ;
        }
}

bool check()
{
        for(int i=1;i<n;i++)
        {
                if(i==1) { sti.insert(a[1]) ; continue ; }
                if(a[i]<(*sti.begin())) { sti.insert(a[i]) ; continue ; }
                if(!st.empty() && (*st.begin()).F < a[i])
                {
                        set<pii>::iterator it=st.lower_bound(mkp(a[i],a[i])) ;
                        it-- ;
                        if(mi[i+1]<it->S) return 0 ;
                }
                set<int>::iterator it=sti.lower_bound(a[i]) ; it-- ;
                insert(mkp(a[i],*it)) ; /// a[i] > *it
                sti.insert(a[i]) ;
        }
        return 1 ;
}

int fa[maxn] ;
int getfa(int x)
{
        return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}

vector<int> v[maxn] ;
void add_edge(int x,int y)
{
        if(getfa(x)==getfa(y)) return ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
        fa[getfa(x)]=getfa(y) ;
}

int ans[maxn] ;
void dfs(int x)
{
        for(auto i : v[x]) if(!ans[i])
                ans[i]=3-ans[x] , dfs(i) ;
}

main()
{
        scanf("%d",&n) ;
        for(int i=1;i<=n;i++)
                scanf("%d",&a[i]) , inv[a[i]]=i ;
        for(int i=n;i>=1;i--) mi[i]= (i==n?a[i]:min(mi[i+1],a[i])) ;

        if(!check()) { printf("NIE\n") ; return 0 ; }

        sti.clear() ;
        for(int i=1;i<=n;i++) fa[i]=i ;
        for(int i=1;i<n;i++)
        {
                sti.insert(a[i]) ;
                if(a[i]==(*sti.begin())) continue ;
                set<int>::iterator it=sti.lower_bound(a[i]) ; it-- ;

                while(*it > mi[i+1])
                {
                        add_edge(inv[*it],i) ;
                        if(a[i]<a[i-1]) break ;
                        if(it==sti.begin()) break ;
                        it-- ;
                }
        }

        for(int i=1;i<=n;i++) if(!ans[i])
                ans[i]=1 , dfs(i) ;

        printf("TAK\n") ;
        for(int i=1;i<=n;i++) printf("%d%c",ans[i]," \n"[i==n]) ;
}