Splay 样例都没过/kk

const int N = 100010;

int n, m;
struct node
{
	int val, id;
 } a[N];

struct Splay
{
	int sz[N], fa[N], ch[N][2], val[N], cnt[N];
	int lzy[N]; 
	int root, tot;
	void update (int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } 
	bool get (int x) { return x == ch[fa[x]][1]; } 
	void clear (int x) { sz[x] = fa[x] = ch[x][0] = ch[x][1] = val[x] = cnt[x] = 0; } 
	
	void rotate (int x)
	{
		int y = fa[x], z = fa[y], chid = get (x);
		ch[y][chid] = ch[x][chid ^ 1]; fa[ch[x][chid ^ 1]] = y;
		ch[z][get(y)] = x; fa[x] = z;
		ch[x][chid ^ 1] = y; fa[y] = x;
		update(y);
		update(x);
	}
	
	void splay (int x, int goal = 0)
	{
		for (int f = fa[x]; f = fa[x], f != goal; rotate(x))
			if (fa[f] != goal) rotate(get(x) == get(f)? f: x);
		if (!goal) root = x;
	}
	
	void Find (int x)
	{
		if (!root) return;
		int cur = root;
		while (ch[cur][x > val[cur]] && x != val[cur])
			cur = ch[cur][x > val[cur]];
		splay(cur);
	}
	
	void ins (int k)
	{
		int x = root, f = 0;
		while (x && val[x] != k)
			f = x, x = ch[x][val[x] < k];
		if (x)
			cnt[x]++;
		else
		{
			x = ++tot;
			if (f) ch[f][val[f] < k] = x;
			ch[x][0] = ch[x][1] = 0;
			fa[x] = f, val[x] = k;
			cnt[x] = sz[x] = 1;
		}
		splay(x);
	} 
	
	void pushdown (int x)
	{
		if (lzy[x])
		{
			swap (ch[x][0], ch[x][1]);
			lzy[ch[x][0]] ^= 1;
			lzy[ch[x][1]] ^= 1;
			lzy[x] = 0;
			return ;
		}
	}
	
	int kth (int k)
	{
		int x = root;
		while (1)
		{
			pushdown (x);
			if (ch[x][0] && k <= sz[ch[x][0]]) x = ch[x][0];
			else if (k > sz[ch[x][0]] + cnt[x]) k -= sz[ch[x][0]] + cnt[x], x = ch[x][1];
			else {splay (x); return x;}
		}
	}
	
	void Reverse(int l, int r)
	{
		int x = kth(l), y = kth(r + 2);
		splay(x), splay(y, x);
		lzy[ch[y][0]] ^= 1;
		return ;
	}
	
	int Output(int x)
	{
		pushdown (x); splay(x);
		printf ("%d ", sz[ch[x][0]]);
		return sz[ch[x][0]];
	}
}splt; 

bool cmp (node a, node b)
{
	return a.val < b.val;
}

int main()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &a[i].val), a[i].id = i;
	sort (a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; i++)
		splt.ins(i);
	splt.ins(-1000000000);
	splt.ins(1000000000); 
	for (int i = 1; i <= n; i++)
	{
		splt.Reverse(i, splt.Output(a[i].id));
	}
	return 0;
}