依然是一道splay的区间操作，需要注意的是要把下标离散化后来表示splay的节点，我不知道怎么搞所以索性弄了个$ValuetoNode$,看样子没什么问题，
感觉他那个传下标的方法太暴力了..应该可以优化
//BZOJ 1552
//by Cydiater
//2016.9.7
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
,root=,tol=,ValuetoNode[MAXN],q[MAXN],head,tail;
struct _data{
int id,v;
}a[MAXN];
struct SplayTree{
],fa,siz,v,tag;
}t[MAXN];
namespace solution{
inline ]==node;}
inline bool cmp(_data x,_data y){return x.v==y.v?x.id<y.id:x.v<y.v;}
inline bool re_cmp(_data x,_data y){return x.id<y.id;}
void updata(int node){
if(node){
t[node].siz=;
])t[node].siz+=t[t[node].son[]].siz;
])t[node].siz+=t[t[node].son[]].siz;
}
}
void downit(int node){
if(t[node].tag){
],rightson=t[node].son[];
;;
swap(t[node].son[],t[node].son[]);
t[node].tag=;
}
}
void rotate(int node){
int old=t[node].fa,oldf=t[old].fa,which=get(node);
t[old].son[which]=t[node].son[which^];t[t[old].son[which]].fa=old;
t[old].fa=node;t[node].son[which^]=old;t[node].fa=oldf;
]]=node;
updata(old);updata(node);
}
void build(int leftt,int rightt,int node,int fa){
if(leftt==rightt){
t[node].v=a[leftt].v;t[node].fa=fa;t[node].son[]=t[node].son[]=;
t[node].siz=;ValuetoNode[a[leftt].v]=node;t[node].tag=;
return;
}
t[node].tag=;
t[node].fa=fa;;
t[node].v=a[mid].v;ValuetoNode[a[mid].v]=node;
>=leftt){
t[node].son[]=++tol;build(leftt,mid-,tol,node);
}
<=rightt){
t[node].son[]=++tol;build(mid+,rightt,tol,node);
}
updata(node);
}
void splay(int node,int aim){
for(int fa;(fa=t[node].fa);rotate(node)){
if(node==aim)break;
if(t[node].fa==aim){
rotate(node);
break;
}
if(t[fa].fa==aim){
rotate(get(node)==get(fa)?fa:node);
rotate(node);
break;
}
if(t[fa].fa!=aim)rotate(get(node)==get(fa)?fa:node);
}
if(aim==root)root=node;
}
int find(int num){
int now=root;
){
downit(now);
]?t[t[now].son[]].siz:);
];
else{
)return now;
num-=(tmp+);
now=t[now].son[];
}
}
}
void init(){
N=read();
a[].v=oo;a[].id=;
up(i,,N+){
a[i].v=read();
a[i].id=i;
}N++;
a[++N].v=oo;a[N].id=N;
sort(a+,a+N+,cmp);
up(i,,N)a[i].v=++cnt;//sort by value
root=++tol;
sort(a+,a+N+,re_cmp);
build(,N,root,);
}
void slove(){
up(i,,N-){
int node=ValuetoNode[i];
head=;tail=;q[++tail]=node;;
int tmp=t[node].fa;
while(tmp!=root){
q[++tail]=tmp;
tmp=t[tmp].fa;
}q[++tail]=root;
while(head<=tail){
tmp=q[tail--];
downit(tmp);
}
splay(node,root);right_siz=t[t[root].son[]].siz+;
printf();)printf(" ");
int leftt=find(i),rightt=find(right_siz);
splay(leftt,root);splay(rightt,t[root].son[]);
];
t[Son].tag^=;
}
puts("");
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
;
}