POI2010 Railway

题目:

  一个铁路包含两个侧线1和2,右边由A进入,左边由B出去(看下面的图片) 有n个车厢在通道A上,编号为1到n,它们被安排按照要求的顺序()进入侧线,进去还要出来,它们要按照编号顺序()从通道B出去。他们从A到1或2,然后经过一系列转移从B出去,不用考虑容量问题。

思路:

  这题算是「NOIP2008 双栈排序」的数据加强版,所以里面的结论就先直接拿来用了。
  设 如果存在 ,那么 就不能在同一个栈中。 的做法可以直接建二分图进行染色。
  但是因为边数很大,所以不可能建出整张图(我一开始尝试了线段树优化连边,但是好像不大行....)。注意到如果在图中抽一棵生成树进行染色,如果原图是一张二分图,那么树的染色方案也是一种合法的染色方案。
  所以又多了一个思路:建生成树进行染色,再判断染色是否合法。
  那么就要能快速的找到与当前点 有边的点。
  先考虑大于 的点,设 表示满足 的最大值,那么与 有边的点就满足 。用以编号为下标用线段树维护权值最大值即可。
  再考虑小于 的点,所有与 有边的点都满足 ,以权值为下标维护编号最小值即可。
  为了保证每个点都只走一次(因为是生成树),所以每访问一个点就要在线段树中删去。染色后再检验一下所有的连边,用树状数组实现应该是比较简单的。
  复杂度

代码:

include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1e5 + 5;

int val[N], mn[N << 2], mx[N << 2], pos[N], lim[N], n, low[N];
#define mid (L + R >> 1)
#define ls (o << 1)
#define rs (o << 1 | 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
void build(int o, int L, int R) {
    if(L == R) {
        mx[o] = val[L]; mn[o] = pos[L];
        return;
    }
    build(lson); build(rson);
    mx[o] = max(mx[ls], mx[rs]);
    mn[o] = min(mn[ls], mn[rs]);
}
int qry_max(int l, int r, int o, int L, int R) {
    if(l > r) return -1e9;
    if(l == L && r == R) return mx[o];
    if(r <= mid) return qry_max(l, r, lson);
    else if(l > mid) return qry_max(l, r, rson);
    else return max(qry_max(l, mid, lson), qry_max(mid + 1, r, rson));
}
int qry_min(int l, int r, int o, int L, int R) {
    if(l > r) return 1e9;
    if(l == L && r == R) return mn[o];
    if(r <= mid) return qry_min(l, r, lson);
    else if(l > mid) return qry_min(l, r, rson);
    else return min(qry_min(l, mid, lson), qry_min(mid + 1, r, rson));
}
void del_min(int x, int o, int L, int R) {
    if(L == R) {mn[o] = 1e9; return;}
    if(x <= mid) del_min(x, lson);
    else del_min(x, rson);
    mn[o] = min(mn[ls], mn[rs]);
}
void del_max(int x, int o, int L, int R) {
    if(L == R) {mx[o] = -1e9; return;}
    if(x <= mid) del_max(x, lson);
    else del_max(x, rson);
    mx[o] = max(mx[ls], mx[rs]);
}

bool col[N];
void dfs(int o) {
    del_max(o, 1, 1, n);
    del_min(val[o], 1, 1, n);
    while(true) {
        int x = qry_max(o, lim[val[o]], 1, 1, n);
        if(x < val[o]) break;
        col[pos[x]] = !col[o];
        dfs(pos[x]);
    }
    while(true) {
        int x = qry_min(low[o], val[o], 1, 1, n);
        if(x > o) break;
        col[x] = !col[o];
        dfs(x);
    }
}

struct BIT {
#define low(x) ((x) & -(x))
    int c[N], a;
    void add(int x, int d) {
        for(; x < N; x += low(x)) c[x] += d;
    }
    int qry(int x) {
        for(a = 0; x; x -= low(x)) a += c[x];
        return a;
    }
    int qry(int l, int r) {
        return qry(r) - qry(l - 1);
    }
} sum, cnt;

void check() {
    bool flag = true;
    rep(i, 1, n) {
        int c = cnt.qry(low[i], val[i]);
        int s = sum.qry(low[i], val[i]);
        if(col[i] && s != 0) flag = false;
        if(!col[i] && s != c) flag = false;
        cnt.add(val[i], 1); sum.add(val[i], col[i]);
    }
    if(flag) {
        puts("TAK");
        rep(i, 1, n) printf("%d%c", col[i] + 1, " \n"[i == n]);
    }
    else puts("NIE");
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", val + i);
    low[n] = val[n];
    drep(i, n - 1, 1) low[i] = min(low[i + 1], val[i]);
    rep(i, 1, n) pos[val[i]] = i;
    int p = n;
    drep(i, n, 1) {
        while(low[p] > i) p--;
        lim[i] = p;
    }
    build(1, 1, n);
    while(true) {
        int o = qry_min(1, n, 1, 1, n);
        if(o == 1e9) break;
        dfs(o);
    }
    check();
    return 0;
}