链接一下题目：
这里的Splay维护的显然不再是权值排序
现在按照的是序列中的编号排序（不过在这道题目里面就是权值诶。。。）
那么，继续考虑，其实最终的结果也就是整颗Splay的中序遍历（平衡树的性质诶）
那么，现在如果按照权值来维护显然是不正确的
继续找找规律，发现，如果一个点在序列中的位置为第K个
那么，他就是平衡树的第K大（就当做普通的Splay来看的话）
所以，序列中的位置就变成了区间的第K大点
继续考虑如何翻转
翻转也就是整颗子树的每一个节点的左右儿子交换
因此，只要在根节点的地方打一个标记
在旋转之前下方一下标记就行了
最后输出的时候输出的就是Splay的中序遍历
至于初始的Splay怎么建立，可以直接构造完美的Splay
像我这种比较懒得，直接弄了一个insert。。。
#include#include #include #include #include #include #include #include #include #include #define rg register#define lst long long#define N 1000050using namespace std;int n,m,tot,root;struct Node{ int ch[2]; int v,fa; int size; int lazy;}ljl[N];inline int read(){ rg int s=0,m=1;char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')m=0,ch=getchar(); while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar(); return m?s:-s;}inline void Pushup(rg int now){ ljl[now].size=ljl[ljl[now].ch[0]].size+ljl[ljl[now].ch[1]].size+1;}inline void Pushdown(rg int now){ if(ljl[now].lazy) { ljl[ljl[now].ch[0]].lazy^=1; ljl[ljl[now].ch[1]].lazy^=1; swap(ljl[now].ch[0],ljl[now].ch[1]); ljl[now].lazy=0; }}inline void rotate(rg int x){ rg int y=ljl[x].fa,z=ljl[y].fa; rg int k=ljl[y].ch[1]==x; ljl[z].ch[ljl[z].ch[1]==y]=x; ljl[x].fa=z; ljl[y].ch[k]=ljl[x].ch[k^1]; ljl[ljl[x].ch[k^1]].fa=y; ljl[x].ch[k^1]=y; ljl[y].fa=x; Pushup(x),Pushup(y);}inline void splay(rg int x,rg int goal){ while(ljl[x].fa!=goal) { rg int y=ljl[x].fa,z=ljl[y].fa; if(z!=goal)(x==ljl[y].ch[0])^(y==ljl[z].ch[0])?rotate(x):rotate(y); rotate(x); } if(goal==0)root=x;}inline void Insert(rg int x){ int now=root,fa=0; while(now)fa=now,now=ljl[now].ch[x>ljl[now].v]; now=++tot; if(fa)ljl[fa].ch[x>ljl[now].v]=now; ljl[now].ch[0]=ljl[now].ch[1]=0; ljl[now].v=x;ljl[now].fa=fa; ljl[now].size=1; splay(now,0);}inline int Kth(rg int x){ rg int now=root; while(233) { Pushdown(now); if(x>ljl[ljl[now].ch[0]].size+1) x-=ljl[ljl[now].ch[0]].size+1,now=ljl[now].ch[1]; else if(ljl[ljl[now].ch[0]].size>=x)now=ljl[now].ch[0]; else return now; }}inline void Work(rg int le,rg int ri){ rg int qq=Kth(le); rg int hj=Kth(ri+2); splay(qq,0),splay(hj,qq); ljl[ljl[ljl[root].ch[1]].ch[0]].lazy^=1;}void Write(rg int now){ Pushdown(now); if(ljl[now].ch[0])Write(ljl[now].ch[0]); if(ljl[now].v>1&&ljl[now].v