Splay
离散化+Splay维护序列……
好吧主要说一下我做这道题遇到的几个错误点：
1.离散化
2.由于找到的这个数的位置一定是大于等于 i 的，所以其实在把它splay到根以后，i 结点只能splay到它的左儿子，而不是右儿子……而且相应的，代表这个区间的应该是c[c[root][0]][1]呃……就是root的左儿子的右儿子= =整个反了一下……好吧不要在意这些细节，我也不知道为什么我突然要反过来写[捂脸熊]
3.进行了修改操作以后一定要立即splay修改的结点！在这题中就是当找到最小结点，将其置为无穷大后，一定要splay一下……否则就WA了TAT
/**************************************************************
Problem: 1552
User: Tunix
Language: C++
Result: Accepted
Time:2764 ms
Memory:4888 kb
****************************************************************/ //BZOJ 1552
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;i--)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*+ch-'';
return r*v;
}
const int N=1e5+,INF=~0u>>;
/******************template*********************/
struct node{int v,pos;}a[N];
bool operator < (node a,node b){return a.pos<b.pos;}
bool cmp(node a,node b){return a.v<b.v||(a.v==b.v && a.pos<b.pos);}
int c[N][],fa[N],v[N],mn[N],size[N],tot,root,n;
bool rev[N];
#define L c[x][0]
#define R c[x][1]
void Push_down(int x){
if (rev[x]){
rev[L]^=; rev[R]^=;
swap(L,R); rev[x]=;
}
}
void Push_up(int x){
mn[x]=v[x];
if (L) mn[x]=min(mn[x],mn[L]);
if (R) mn[x]=min(mn[x],mn[R]);
size[x]=size[L]+size[R]+;
}
void Rotate(int x){
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
c[z][c[z][]==y]=x;
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
Push_up(y);
}
int st[N];
void Preview(int x){
int top=; st[++top]=x;
for(int i=x;fa[i];i=fa[i])
st[++top]=fa[i];
D(i,top,) Push_down(st[i]);
}
void splay(int x,int s=){
int y;
for(Preview(x);fa[x]!=s;Rotate(x))
if (fa[y=fa[x]]!=s) Rotate(c[y][]==x^c[fa[y]][]==y?x:y);
Push_up(x);
if (!s) root=x;
}
void New_node(int &x,int f,int key){
x=++tot;
fa[x]=f;
v[x]=mn[x]=key;
rev[x]=L=R=;
size[x]=;
}
void Build(int &x,int f,int l,int r){
if (l>r) return;
int mid=l+r>>;
New_node(x,f,a[mid].v);
Build(L,x,l,mid-);
Build(R,x,mid+,r);
Push_up(x);
}
int kth(int x,int k){
Push_down(x);
if (size[L]+==k) return x;
else if (size[L]>=k) return kth(L,k);
else return kth(R,k-size[L]-);
}
int findmin(int x){
Push_down(x);
if (L && mn[x]==mn[L]) return findmin(L);
else if (R && mn[x]==mn[R]) return findmin(R)+size[L]+;
else {v[x]=INF;Push_up(x); return size[L]+;}
}
int main(){
n=getint();
v[]=mn[]=a[].v=a[n+].v=INF;
F(i,,n) {a[i].v=getint();a[i].pos=i;}
sort(a+,a+n+,cmp);
F(i,,n) a[i].v=i;
sort(a+,a+n+);
Build(root,,,n+);
F(i,,n){
int t1=findmin(root);
splay(kth(root,t1));
printf("%d",t1-); if(i!=n)printf(" ");
splay(kth(root,t1+)); splay(kth(root,i),root);
int pos=c[c[root][]][];
if (pos) rev[pos]^=;
splay(pos);
}
return ;
}
1552: [Cerc2007]robotic sort
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 436 Solved: 186
[Submit][Status][Discuss]
Description
Input
输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。
Output
输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，（1 < = Pi < = N），Pi表示第i次操作前第i小的物品所在的位置。
注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。
注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。
Sample Input
6
3 4 5 1 6 2
3 4 5 1 6 2
Sample Output
4 6 4 5 6 6