2080: [Poi2010]Railway
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 140 Solved: 35
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
4
1 3 4 2
[样例输入2]
4
2 3 4 1
Sample Output
TAK
1 1 2 1 (1号线进到侧线1,然后出来,3号进入侧线1,4号进入侧线2,2号进入侧线1,然后出来,接着3号出来,4号出来)
[样例输出2]
NIE (不可能。。No)
HINT
Source
分析
本题和 NOIP 2008 提高组 的 双栈排序 是类似的。
首先,考虑一个序列满足双栈排序,需要什么样的性质。
发现,如果点i入栈,那么在i之前的值大于a[i]的点都不可能出栈,那么它们出来的时候一定和入栈的顺序刚好相反。
如果,其入栈不是递减的,出栈就不会是递增的。后来发现,这也是序列满足双栈排序的充要条件。
因此,对于所有的i<j<k且有a[k]<a[i]<a[k],在i和j之间连边。每条边上的两个点不能在同一个栈中。做染色即可。
双栈排序数据太水,不用刻意调整顺序即可AC,而且边很少。
然而BZOJ上POI的双栈排序要难多了,数据范围更大,而且还卡格式了。
Railway要求只能O(NlogN),考虑机智地遍历图地方式。
对于一个点,如果lim表示最大的下标满足min(lim...n)<num[i],那么i向[i + 1, lim]中所有值大于num[i]的地方都有边,可以用一个按下标维护的线段树来查询区间内最大的num值,即可知道是否有边。
对于一个点,如果low表示min(i...n),那么i向num值在(low, num[i])内的所有在i之前的地方都右边,可以用一个按num值维护的线段树来查询区间内最小的下标值,即可知道是否有边。
DFS时,每访问一个点,就把这个点从两个线段树中删除,保证以后不会再访问到。最终对染色方案进行判断,看是否合法即可。
代码
#include <bits/stdc++.h> using namespace std; const int N = ; int n, num[N]; int low[N], col[N]; int hd[N], to[N], nt[N], tot; void addEdge(int x, int y)
{
nt[++tot] = hd[x]; to[tot] = y; hd[x] = tot;
nt[++tot] = hd[y]; to[tot] = x; hd[y] = tot;
} bool dfs(int u, int c)
{
if (col[u] != -)
return col[u] != c; col[u] = c; for (int i = hd[u]; i; i = nt[i])
if (dfs(to[i], c ^ ))return true; return false;
} int stk1[N], tot1;
int stk2[N], tot2;
int ans[N], cnt, t(); void pop(void)
{
if (tot1 && stk1[tot1] == t)
{ ans[++cnt] = , --tot1, ++t; pop(); }
if (tot2 && stk2[tot2] == t)
{ ans[++cnt] = , --tot2, ++t; pop(); }
} void putAns(void)
{
for (int i = ; i <= n; ++i)
{
pop(); switch (col[i])
{
case :
{
stk1[++tot1] = num[i];
ans[++cnt] = ;
break;
}
case :
{
stk2[++tot2] = num[i];
ans[++cnt] = ;
break;
}
}
} pop(); for (int i = ; i <= cnt; ++i)
printf("%c ", 'a' + ans[i]);
} signed main(void)
{
scanf("%d", &n); for (int i = ; i <= n; ++i)
scanf("%d", num + i); low[n] = num[n]; for (int i = n; i >= ; --i)
low[i - ] = min(num[i], low[i]); for (int i = ; i < n; ++i)
for (int j = + i; j <= n; ++j)
if (num[i] < num[j] && num[i] > low[j])
addEdge(i, j); bool flag = true; memset(col, -, sizeof(col)); for (int i = ; i <= n; ++i)
if (col[i] == -)if (dfs(i, ))
{ flag = false; break; } if (flag)
putAns();
else
puts("");
}
双栈排序.cpp
#include <bits/stdc++.h> template <class Int>
Int min(const Int &a, const Int &b)
{
return a < b ? a : b;
} template <class Int>
Int max(const Int &a, const Int &b)
{
return a > b ? a : b;
} #define N 1000005 struct Data
{
int val;
int pos; Data(void) {};
Data(int v, int p)
{
val = v;
pos = p;
} friend bool operator <
(const Data &a, const Data &b)
{
return a.val < b.val;
} friend bool operator >
(const Data &a, const Data &b)
{
return a.val > b.val;
}
}; struct Node
{
int lt;
int rt;
Data min;
Data max;
}; struct SegTree
{
Node tr[N << ]; void build(int p, int l, int r)
{
Node &t = tr[p]; t.lt = l;
t.rt = r; t.min = Data(N, );
t.max = Data(, ); if (l ^ r)
{
int mid = (l + r) >> ; build(p << , l, mid);
build(p << | , mid + , r);
}
} Data queryMin(int p, int l, int r)
{
if (l > r)
return Data(N, ); Node &t = tr[p]; if (t.lt == l && t.rt == r)
return t.min; int mid = (t.lt + t.rt) >> ; if (r <= mid)
return queryMin(p << , l, r);
else if (l > mid)
return queryMin(p << | , l, r);
else
return min(
queryMin(p << , l, mid),
queryMin(p << | , mid + , r)
);
} Data queryMax(int p, int l, int r)
{
if (l > r)
return Data(, ); Node &t = tr[p]; if (t.lt == l && t.rt == r)
return t.max; int mid = (t.lt + t.rt) >> ; if (r <= mid)
return queryMax(p << , l, r);
else if (l > mid)
return queryMax(p << | , l, r);
else
return max(
queryMax(p << , l, mid),
queryMax(p << | , mid + , r)
);
} void change(int p, int pos, Data val)
{
Node &t = tr[p]; if (t.lt == t.rt)
t.min = t.max = val;
else
{
int mid = (t.lt + t.rt) >> ; if (pos <= mid)
change(p << , pos, val);
else
change(p << | , pos, val); t.min = min(tr[p << ].min, tr[p << | ].min);
t.max = max(tr[p << ].max, tr[p << | ].max);
}
}
}; int n;
int num[N];
int low[N];
int pre[N]; SegTree A;
SegTree B; int color[N]; bool dfs(int u, int c)
{
if (color[u] != -)
return color[u] != c; color[u] = c; A.change(, u, Data(, ));
B.change(, num[u], Data(N, )); sta:Data a = A.queryMax(, u + , pre[num[u] - ]); if (a.pos && a.val > num[u])
{
if (dfs(a.pos, color[u] ^ ))
return true; goto sta;
} stb:Data b = B.queryMin(, low[u] + , num[u] - ); if (b.pos && b.val < u)
{
if (dfs(b.pos, color[u] ^ ))
return true; goto stb;
} return false;
} int bit[][N]; int lowbit(int x)
{
return x & -x;
} void add(int *b, int p)
{
while (p <= n)
++b[p], p += lowbit(p);
} int qry(int *b, int p)
{
int r = ; while (p)
r += b[p], p -= lowbit(p); return r;
} signed main(void)
{
scanf("%d", &n); for (int i = ; i <= n; ++i)
scanf("%d", num + i); memset(low, 0x3f, sizeof(low)); for (int i = n; i >= ; --i)
low[i] = min(num[i], low[i + ]); for (int i = ; i <= n; ++i)
pre[low[i]] = max(pre[low[i]], i); for (int i = ; i <= n; ++i)
pre[i] = max(pre[i], pre[i - ]); A.build(, , n);
B.build(, , n); for (int i = ; i <= n; ++i)
A.change(, i, Data(num[i], i)); for (int i = ; i <= n; ++i)
B.change(, num[i], Data(i, i)); memset(color, -, sizeof(color)); for (int i = ; i <= n; ++i)
if (color[i] == -)if (dfs(i, ))
return puts("NIE"), ; memset(bit, , sizeof(bit)); for (int i = ; i <= n; ++i)
{
if (qry(bit[color[i]], num[i] - ) > qry(bit[color[i]], low[i]))
return puts("NIE"), ;
else add(bit[color[i]], num[i]);
} puts("TAK"); for (int i = ; i < n; ++i)
printf("%d ", ++color[i]); printf("%d\n", ++color[n]);
}
BZOJ_2080.cpp
@Author: YouSiki