• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

5小时前 2次浏览

# (text{Code})

``````#include <cstdio>
#include <algorithm>
#include <ctime>
#define re register
using namespace std;
typedef long long LL;

const int N = 1e5 + 5;
int n, b[N], rt, ls[N], rs[N], val[N], mi[N], rnd[N], siz[N], tag[N];
struct nod{int v, id;}a[N];
inline bool cmp(nod a, nod b){return (a.v < b.v ? 1 : (a.v == b.v ? a.id < b.id : 0));}

inline int new_node(int x)
{
static int size = 0;
val[++size] = x, mi[size] = x, rnd[size] = rand(),
siz[size] = 1, ls[size] = rs[size] = tag[size] = 0;
return size;
}

inline void pushup(int p)
{
siz[p] = siz[ls[p]] + siz[rs[p]] + 1, mi[p] = val[p];
if (ls[p]) mi[p] = min(mi[p], mi[ls[p]]);
if (rs[p]) mi[p] = min(mi[p], mi[rs[p]]);
}

inline void pushdown(int p)
{
if (!p || !tag[p]) return;
tag[p] = 0, swap(ls[p], rs[p]);
if (ls[p]) tag[ls[p]] ^= 1;
if (rs[p]) tag[rs[p]] ^= 1;
}

void split(int p, int k, int &x, int &y)
{
if (!p) return void(x = y = 0);
pushdown(p);
if (k <= siz[ls[p]]) y = p, split(ls[p], k, x, ls[y]);
else x = p, split(rs[p], k - siz[ls[p]] - 1, rs[x], y);
pushup(p);
}

int merge(int x, int y)
{
if (!x || !y) return x | y;
pushdown(x), pushdown(y);
if (rnd[x] < rnd[y]){rs[x] = merge(rs[x], y), pushup(x); return x;}
ls[y] = merge(x, ls[y]), pushup(y); return y;
}

inline int find(int p)
{
int k = 1;
while (1)
{
pushdown(p);
if (ls[p] && mi[ls[p]] == mi[p]) p = ls[p];
else if (rs[p] && mi[rs[p]] == mi[p]) k += siz[ls[p]] + 1, p = rs[p];
else return k + siz[ls[p]];
}
}

int main()
{
srand((unsigned)time(NULL));
scanf("%d", &n);
for(re int i = 1; i <= n; i++) scanf("%d", &a[i].v), a[i].id = i;
sort(a + 1, a + n + 1, cmp);
for(re int i = 1; i <= n; i++) b[a[i].id] = i;
for(re int i = 1; i <= n; i++) rt = merge(rt, new_node(b[i]));
for(re int i = 1; i <= n; i++)
{
int x, y, z, o = find(rt);
printf("%d ", o + i - 1);
split(rt, o, x, y), split(x, o - 1, x, z);
tag[x] ^= 1, rt = merge(x, y);
}
}
``````