思路和其他Splay题解思路一样

目前样例RE，对于rotate()如果不下传标记则不会RE。RE是因为在print()中调用儿子会形成一个环。

但是pushdown我对排了一下也没有问题

T.print()就是将平衡树中序输出的

#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#define fi first
#define se second
#define mp make_pair
#define lfor(i, x, y) for (int i = (x); i <= (y); ++ i)
#define llfor(i, x, y) for (int i = (x); i < (y); ++ i)
#define rfor(i, x, y) for (int i = (x); i >= (y); -- i)
#define rlfor(i, x, y) for (int i = (x); i > (y); -- i)
#define For(i, p) for(int i = G.head[p]; ~i; i = G.nxt[i])
template <typename T>inline void read(T &x){bool f=0;x=0;char ch=getchar();while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-')ch=getchar(),f=1;while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=f?-x:x;}
template <typename T1,typename... T2>inline void read(T1 &x,T2& ...y){read(x);read(y...);}
using namespace std;

/*======================Header Template======================*/
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pr;
const int N = 1e5 + 5;
const int P = 1e9 + 5;
pr a[N]; int rk[N], raw[N];
map<int, int> vl;
struct Splay {
	int ch[N][2], fa[N], cnt[N], sz[N], val[N], tot, rt;
	bool mark[N];
	
	void maintian(int x) {sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}
	void clear(int x) {ch[x][0] = ch[x][1] = sz[x] = val[x] = cnt[x] = fa[x] = 0;}
	int get(int x) {return x == ch[fa[x]][1];}
	
	void pushdown(int cur) {
		if (!cur || !mark[cur]) return;
		if (ch[cur][0]) mark[ch[cur][0]] ^= 1; 
		if (ch[cur][1]) mark[ch[cur][1]] ^= 1;
		swap(ch[cur][0], ch[cur][1]);
		mark[cur] = 0;
	}
	
	void rotate(int x) {
		if (x == rt) return;
    int y = fa[x], z = fa[y], chk = get(x);
    pushdown(y); pushdown(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;
    maintian(y);
    maintian(x);
  }
	
	void splay(int x, int tar) {
    for (int f = fa[x]; f = fa[x], f != tar; rotate(x))
      if (fa[f] != tar) rotate(get(x) == get(f) ? f : x);
    if (!tar) rt = x;
  }
	
	int build(int f, int l, int r) {
		if (l > r) return 0;
		int mid = (l + r) >> 1, nw = ++ tot;
		//cout << a[mid].fi << " " << tot << endl;
		rk[vl[a[mid].fi]] = tot; val[tot] = a[mid].fi; fa[tot] = f; cnt[tot] = 1; mark[tot] = 0; //TODO
		ch[nw][0] = build(nw, l, mid - 1); ch[nw][1] = build(nw, mid + 1, r); //TODO
		maintian(nw);
		return nw; 
	}
	
	int rnk(int k) {
		int cur = rt;
		while (1) {
			pushdown(cur);
			if (k <= sz[ch[cur][0]]) cur = ch[cur][0];
			else {
				k -= sz[ch[cur][0]] + cnt[cur];
				if (k == 0) return cur;
				cur = ch[cur][1];
			}
		}
	}
	
	void print(int cur) {
		pushdown(cur);
		//cout << "cur:" << cur << endl;
		if (ch[cur][0]) print(ch[cur][0]);
		//if (val[cur] != -P && val[cur] != P) cout << val[cur] << " "; 
		//cout << "val:" << val[cur] << " mark;" << mark[cur] << " cur:" << cur << " ls:" << ch[cur][0] << " rs:" << ch[cur][1] << endl; 
		if (ch[cur][1]) print(ch[cur][1]);
	}
	
	void move(int x, int y) {
		x = rnk(x), y = rnk(y + 2);
		cout << "x:" << x << " y:" << y << endl;
		splay(x, 0), splay(y, x);
		mark[ch[y][0]] ^= 1;
	}
} T;
 
/*======================Define Area======================*/
void Mod(int &x) {(x >= P) && (x -= P);}

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    lfor(i, 2, n + 1) cin >> a[i].fi, a[i].se = i, raw[i] = a[i].fi;
    a[1] = mp(-P, 1); a[n + 2] = mp(P, n + 2); raw[1] = -P, raw[n + 2] = P;
    sort(raw + 1, raw + 1 + n + 2);
    lfor(i, 1, n + 2) vl[raw[i]] = i; 
	T.rt = T.build(0, 1, n + 2); 
	sort(a + 1, a + 1 + n + 2);
	lfor(i, 2, n + 1) {
		cout << "i:" << i << " se:" << a[i].fi << " vl:" << vl[a[i].fi] << " rk:" << rk[vl[a[i].fi]] << endl;
		T.splay(rk[vl[a[i].fi]], 0); 
		T.print(T.rt);
		cout << T.sz[T.ch[T.rt][0]] << " ";
		//T.print(T.rt);
		T.move(i - 1, T.sz[T.ch[T.rt][0]]);
	}
	return 0;
}