题解 P3497 【[POI2010]KOL-Railway】

kczno1 · 2017-02-11 16:55:12 · 题解

noip双栈排序加强版。

如果存在k使得ak<ai<aj且k>j>i，那么i,j不能入一个栈。

i<->j连一条边，之后跑二分图染色，优先给小的染黑色，表示进第一个栈。

我们可以预处理m[i]=min{a[i+1..n]}

对每个j，找ai<aj且ai>m[j]的。

然而我们不能把边都连出来，因为会是n^2。

我们想办法只连出一些生成树，染色之后模拟判断一下行不行。

方法就是每连了两个块就并成一个块，并且用可并堆维护块内最小ai。

因为m是单调增的，如果最小ai<=m，就弹出。

之后我们再用一个堆维护所有块里面最小ai最小的块，每次取出，如果满足ai<aj就连边，合并。

时间nlogn。

(好久没打堆了233)

#include<cstdio>
#include<algorithm> 
using std::swap;

#define ch_top 10000000
char ch[ch_top],*now_w=ch-1;
#define print(x) *++now_w=x;
#define chmin(x,y) {if(x>y)x=y;}
#define N 101000
int a[N],m[N];//m[i]=i->n min 
int t[N];
struct edge
{
    int to,next;
}l[10000000];int e;
#define add_e(x,y) l[++e]=(edge){y,t[x]};t[x]=e;
bool vis[N],col[N];//col[i]=1 第一个栈 
int q1[N],t1,q2[N],t2;

int n;
int head[N],next[N];
int h[N<<1],top;

void dfs(int x,bool now)
{
    if (vis[x])
    {
     if (col[x]!=now) {puts("NIE");exit(0);}
    }
    else
    {
        vis[x]=1;col[x]=now;
    for (int i=t[x];i;i=l[i].next) dfs(l[i].to,now^1);
    }
}

void move()
{
    for (int i=1,j;(j=i<<1)<=top;)
    {
        if (j<top&&a[h[j]]>a[h[j+1]]) ++j;
        if (a[h[i]]<a[h[j]]) break ;
        swap(h[i],h[j]);i=j;
    }
}

void push(int x)
{
    h[++top]=x;
    for (int i=top,j;i>1;)
    {
      if (a[h[i]]>=a[h[j=i>>1]])  break;
      swap(h[i],h[j]);i=j;
    }
}

void merge(int &x,int y)
{
    if (a[x]<a[y])
    {
        next[y]=head[x];head[x]=y;
    }
    else
    {
        next[x]=head[y];head[y]=x;
        x=y;
    }
}

void merges(int &x)
{
    int y=next[x],r;
    while (y)
    {
        r=next[y];
        merge(x,y);
        y=r;
    }
    next[x]=0;
}

int main()
{
    freopen("1.in","r",stdin);
    int i,j;
    scanf("%d",&n);
    for (i=1;i<=n;++i) {scanf("%d",a+i);m[i]=a[i];}
    for (i=n;--i;) chmin(m[i],m[i+1])
    h[top=1]=1;
    a[0]=N+1;
    m[n+1]=N;
    int p;
    for (i=2;i<=n;++i)
    {
        int rt=i;
        for (;a[p=h[1]]<a[i];)
        {
          while (a[p]<=m[i+1]) 
            merges(p=head[p]);
          if(a[p]<a[i]) {add_e(i,p);add_e(p,i);merge(rt,p);h[1]=h[top--]; }
          else h[1]=p;
          move();
        }
        push(rt);
    }
    int now=1;
    print('T') print('A') print('K') print('\n')
    for (i=1;i<=n;++i)
    {
        if (!vis[i]) dfs(i,1);
        if (col[i]) {q1[++t1]=i;print('1') }
        else {q2[++t2]=i;print('2') }
        print(' ')
        while (a[q1[t1]]==now||a[q2[t2]]==now)
        {
            if (a[q1[t1]]==now++) {  --t1; }
            else {  --t2; }
        }
    }
    if (now<=n) puts("NIE");
    else fwrite(ch,1,now_w-ch,stdout);
}