1552: [Cerc2007]robotic sort
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1428 Solved: 563
[ Submit ][ Status ][ Discuss ]
Description
Input
输入共两行, 第一行为一个整数 N,N 表示物品的个数, 1<=N<=100000.
第二行为 N 个用空格隔开的正整数, 表示 N 个物品最初排列的编号.
Output
输出共一行, N 个用空格隔开的正整数 P1,P2,P3...Pn,Pi 表示第 i 次操作前第 i 小的物品所在的位置.
注意: 如果第 i 次操作前, 第 i 小的物品己经在正确的位置 Pi 上, 我们将区间 [Pi,Pi] 反转 (单个物品).
Sample Input
6
3 4 5 1 6 2
Sample Output
4 6 4 5 6 6
HINT
Source
[题解]
顺便维护一下子树最小值所在 splay 的节点即可, 想知道节点在序列中的位置, 把它 splay 到根看左子树即可
需要离散化让相等的数按出现顺序从小到大排
/**************************************************************
Problem: 1552
User: 33511595
Language: C++
Result: Accepted
Time:3360 ms
Memory:21528 kb
****************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
template <class T>
inline void swap(T& a, T& b)
{
T tmp = a;a = b;b = tmp;
}
inline void read(int &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = 500000 + 10;
int ch[MAXN][2], fa[MAXN], n, root, size[MAXN], data[MAXN], mi[MAXN], tag[MAXN];
void ddfs(int x)
{
if(!x) return;
ddfs(ch[x][0]);
if(x != 1 && x != n + 2) printf("%d", data[x]);
ddfs(ch[x][1]);
}
int son(int x){return x == ch[fa[x]][1];}
void pushup(int rt)
{
int l = ch[rt][0], r = ch[rt][1];
size[rt] = size[l] + size[r] + 1;
if(mi[l] == 0) mi[rt] = mi[r];
else if(mi[r] == 0) mi[rt] = mi[l];
else mi[rt] = data[mi[l]] < data[mi[r]] ? mi[l] : mi[r];
mi[rt] = data[mi[rt]] < data[rt] ? mi[rt] : rt;
}
void pushdown(int rt)
{
if(!tag[rt]) return;
int l = ch[rt][0], r = ch[rt][1];
tag[l] ^= 1, tag[r] ^= 1;
swap(ch[l][0], ch[l][1]), swap(ch[r][0], ch[r][1]);
tag[rt] = 0;
}
void rotate(int x)
{
int y = fa[x], z = fa[y], b = son(x), c = son(y), a = ch[x][!b];
if(z) ch[z][c] = x; else root = x; fa[x] = z;
if(a) fa[a] = y; ch[y][b] = a;
ch[x][!b] = y, fa[y] = x;
pushup(y), pushup(x);
}
void dfs(int x)
{
if(!x) return;
dfs(fa[x]);
pushdown(x);
}
void splay(int x, int i)
{
dfs(x);
while(fa[x] != i)
{
int y = fa[x], z = fa[y];
if(z == i) rotate(x);
else
if(son(x) == son(y)) rotate(y), rotate(x);
else rotate(x), rotate(x);
}
}
int getkth(int rt, int x)
{
pushdown(rt);int l = ch[rt][0];
if(size[l] + 1 == x) return rt;
if(x < size[l] + 1) return getkth(ch[rt][0], x);
return getkth(ch[rt][1], x - size[l] - 1);
}
void turn(int l, int r)
{
l = getkth(root, l - 1), r = getkth(root, r + 1);
// ddfs(root), putchar('\n');
splay(l, 0), splay(r, l);
// ddfs(root), putchar('\n');
int now = ch[r][0];
tag[now] ^= 1;swap(ch[now][0], ch[now][1]);pushdown(now);
}
// 查询节点 k 的排名
int getk(int k)
{
splay(k, 0);
return size[ch[k][0]] + 1;
}
int ask_mi(int l, int r)
{
l = getkth(root, l - 1), r = getkth(root, r + 1);
// ddfs(root), putchar('\n');
splay(l, 0), splay(r, l);
// ddfs(root), putchar('\n');
return getk(mi[ch[r][0]]);
}
int cnt[MAXN];
bool cmp(int a, int b)
{
return data[a] < data[b];
}
int main()
{
memset(data, 0x3f, sizeof(data));
read(n);
for(int i = 2;i <= n + 1;++ i) cnt[i] = i, read(data[i]);
std::stable_sort(cnt + 2, cnt + 2 + n, cmp);
for(int i = 2;i <= n + 1;++ i) data[cnt[i]] = i;
fa[2] = 1, ch[1][1] = 2;size[1] = n + 2;mi[1] = 2;
for(int i = 2;i <= n + 1;++ i)
{
ch[i][1] = i + 1, fa[i + 1] = i;size[i] = n + 3 - i;
mi[i] = i;
}
size[n + 2] = 1;mi[n + 2] = n + 2;root = 1;
for(int i = n + 2;i >= 1;-- i) pushup(i);
for(int i = 1;i < n;++ i)
{
int tmp = ask_mi(i + 1, n + 1);
printf("%d", tmp - 1);
turn(i + 1, tmp);
}
int tmp = ask_mi(n + 1, n + 1);
printf("%d\n", tmp - 1);
return 0;
}
BZOJ1552
BZOJ1552: [Cerc2007]robotic sort
来源: http://www.bubuko.com/infodetail-2479056.html