cjb-poi2010railway

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define N 110000
int n,a[N],pos[N],b[N],c[N],col[N];
struct node1 
{
    int p[5*N];
    void build(int t,int l,int r)
    {
        if (l==r){ p[t]=a[l]; return; }
        int mid=(l+r)/2;
        build(2*t,l,mid);
        build(2*t+1,mid+1,r);
        p[t]=max(p[2*t],p[2*t+1]);
    }
    int get(int t,int l,int r,int a,int b,int k)
    {
        if (l>r)return -1;
        if (p[t]<=k)return -1;
        if (l==r)return l;
        int mid=(l+r)/2;
        if (b<=mid)return get(2*t,l,mid,a,b,k);
        if (a>mid)return get(2*t+1,mid+1,r,a,b,k);
        int ans=get(2*t,l,mid,a,mid,k);
        if (ans!=-1)return ans;
        return get(2*t+1,mid+1,r,mid+1,b,k);
    }
    void del(int t,int l,int r,int k)
    {
        if (l==r){ p[t]=0; return; }
        int mid=(l+r)/2;
        if (k<=mid)del(2*t,l,mid,k);
        else del(2*t+1,mid+1,r,k);
        p[t]=max(p[2*t],p[2*t+1]);
    }
}A;
struct node2
{
    int p[5*N];
    void build(int t,int l,int r)
    {
        if (l==r){ p[t]=pos[l]; return; }
        int mid=(l+r)/2;
        build(2*t,l,mid);
        build(2*t+1,mid+1,r);
        p[t]=min(p[2*t],p[2*t+1]);
    }
    int get(int t,int l,int r,int a,int b,int k)
    {
        if (l>r)return -1;
        if (p[t]>=k)return -1;
        if (l==r)return p[t];
        int mid=(l+r)/2;
        if (b<=mid)return get(2*t,l,mid,a,b,k);
        if (a>mid)return get(2*t+1,mid+1,r,a,b,k);
        int ans=get(2*t,l,mid,a,mid,k);
        if (ans!=-1)return ans;
        return get(2*t+1,mid+1,r,mid+1,b,k);
    }
    void del(int t,int l,int r,int k)
    {
        if (l==r){ p[t]=2147483647; return; }
        int mid=(l+r)/2;
        if (k<=mid)del(2*t,l,mid,k);
        else del(2*t+1,mid+1,r,k);
        p[t]=min(p[2*t],p[2*t+1]);
    }
}B;
void dfs(int x,int cc)
{
    //cout<<x<<endl;
    col[x]=cc;
    A.del(1,1,n,x);
    B.del(1,1,n,a[x]);
    while (1)
    {
        int p1=A.get(1,1,n,x+1,c[a[x]],a[x]);
        if (p1!=-1)dfs(p1,((cc-1)^1)+1);
        int p2=B.get(1,1,n,b[x]+1,a[x]-1,x);
        if (p2!=-1)dfs(p2,((cc-1)^1)+1);
        if (p1==-1 && p2==-1)break;
    }
}
bool check()
{
    stack<int> stack1,stack2;
    while (!stack1.empty())stack1.pop();
    while (!stack2.empty())stack2.pop();
    int now=1;
    rep(i,n)
    {
        int flag=0;
        while (1)
        {
            if (!stack1.empty() && stack1.top()==i){ flag=1; stack1.pop(); break; }
            if (!stack2.empty() && stack2.top()==i){ flag=1; stack2.pop(); break; }
            if (now<=n && col[now]==1){ stack1.push(a[now++]); continue; }
            if (now<=n && col[now]==2){ stack2.push(a[now++]); continue; }
            if (now>n)break;
        }
        if (!flag)return 0;
    }
    return 1;
}
int main()
{
    cin>>n;
    rep(i,n){ scanf("%d",&a[i]); pos[a[i]]=i; }
    A.build(1,1,n);
    B.build(1,1,n);
    b[n]=a[n]; for(int i=n-1;i>=1;i--)b[i]=min(b[i+1],a[i]);
    rep(i,n)c[b[i]+1]=i; rep(i,n)c[i]=max(c[i-1],c[i]);

    //rep(i,n)cout<<b[i]<<" "; puts("");
    //rep(i,n)cout<<c[i]<<" "; puts("");

    rep(i,n)col[i]=-1;
    rep(i,n)if (col[i]==-1)dfs(i,1);
    if (!check()){ puts("NIE"); return 0; }
    puts("TAK");
    rep(i,n)printf("%d%c",col[i],i==n?'\n':' ');

    return 0;
}

}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define N 110000
int n,a[N],pos[N],b[N],c[N],col[N];
struct node1 
{
    int p[5*N];
    void build(int t,int l,int r)
    {
        if (l==r){ p[t]=a[l]; return; }
        int mid=(l+r)/2;
        build(2*t,l,mid);
        build(2*t+1,mid+1,r);
        p[t]=max(p[2*t],p[2*t+1]);
    }
    int get(int t,int l,int r,int a,int b,int k)
    {
        if (l>r)return -1;
        if (p[t]<=k)return -1;
        if (l==r)return l;
        int mid=(l+r)/2;
        if (b<=mid)return get(2*t,l,mid,a,b,k);
        if (a>mid)return get(2*t+1,mid+1,r,a,b,k);
        int ans=get(2*t,l,mid,a,mid,k);
        if (ans!=-1)return ans;
        return get(2*t+1,mid+1,r,mid+1,b,k);
    }
    void del(int t,int l,int r,int k)
    {
        if (l==r){ p[t]=0; return; }
        int mid=(l+r)/2;
        if (k<=mid)del(2*t,l,mid,k);
        else del(2*t+1,mid+1,r,k);
        p[t]=max(p[2*t],p[2*t+1]);
    }
}A;
struct node2
{
    int p[5*N];
    void build(int t,int l,int r)
    {
        if (l==r){ p[t]=pos[l]; return; }
        int mid=(l+r)/2;
        build(2*t,l,mid);
        build(2*t+1,mid+1,r);
        p[t]=min(p[2*t],p[2*t+1]);
    }
    int get(int t,int l,int r,int a,int b,int k)
    {
        if (l>r)return -1;
        if (p[t]>=k)return -1;
        if (l==r)return p[t];
        int mid=(l+r)/2;
        if (b<=mid)return get(2*t,l,mid,a,b,k);
        if (a>mid)return get(2*t+1,mid+1,r,a,b,k);
        int ans=get(2*t,l,mid,a,mid,k);
        if (ans!=-1)return ans;
        return get(2*t+1,mid+1,r,mid+1,b,k);
    }
    void del(int t,int l,int r,int k)
    {
        if (l==r){ p[t]=2147483647; return; }
        int mid=(l+r)/2;
        if (k<=mid)del(2*t,l,mid,k);
        else del(2*t+1,mid+1,r,k);
        p[t]=min(p[2*t],p[2*t+1]);
    }
}B;
void dfs(int x,int cc)
{
    //cout<<x<<endl;
    col[x]=cc;
    A.del(1,1,n,x);
    B.del(1,1,n,a[x]);
    while (1)
    {
        int p1=A.get(1,1,n,x+1,c[a[x]],a[x]);
        if (p1!=-1)dfs(p1,((cc-1)^1)+1);
        int p2=B.get(1,1,n,b[x]+1,a[x]-1,x);
        if (p2!=-1)dfs(p2,((cc-1)^1)+1);
        if (p1==-1 && p2==-1)break;
    }
}
bool check()
{
    stack<int> stack1,stack2;
    while (!stack1.empty())stack1.pop();
    while (!stack2.empty())stack2.pop();
    int now=1;
    rep(i,n)
    {
        int flag=0;
        while (1)
        {
            if (!stack1.empty() && stack1.top()==i){ flag=1; stack1.pop(); break; }
            if (!stack2.empty() && stack2.top()==i){ flag=1; stack2.pop(); break; }
            if (now<=n && col[now]==1){ stack1.push(a[now++]); continue; }
            if (now<=n && col[now]==2){ stack2.push(a[now++]); continue; }
            if (now>n)break;
        }
        if (!flag)return 0;
    }
    return 1;
}
int main()
{
    cin>>n;
    rep(i,n){ scanf("%d",&a[i]); pos[a[i]]=i; }
    A.build(1,1,n);
    B.build(1,1,n);
    b[n]=a[n]; for(int i=n-1;i>=1;i--)b[i]=min(b[i+1],a[i]);
    rep(i,n)c[b[i]+1]=i; rep(i,n)c[i]=max(c[i-1],c[i]);
    //rep(i,n)cout<<b[i]<<" "; puts("");
    //rep(i,n)cout<<c[i]<<" "; puts("");
    rep(i,n)col[i]=-1;
    rep(i,n)if (col[i]==-1)dfs(i,1);
    if (!check()){ puts("NIE"); return 0; }
    puts("TAK");
    rep(i,n)printf("%d%c",col[i],i==n?'\n':' ');
    return 0;
}