【算法】splay
【题解】
splay维护序列，用权值(离散化)作为编号。每次找第i小的话直接找对应编号splay即可。
但是这样splay没有下传翻转标记？直接暴力找到路径然后从根到改结点pushdown。暴力出奇迹！
如果没有find就直接splay，一定记得更新设置splay为传值调用并且在过程中更新地址才能更新root。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=;
int f[maxn],t[maxn][],s[maxn],first[maxn],second[maxn],ord[maxn],a[maxn],node[maxn],n,root,ans[maxn];
bool g[maxn];
int read()
{
char c;int s=;
while(!isdigit(c=getchar()));
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s;
}
bool cmp(int x,int y)
{return (first[x]<first[y])||(first[x]==first[y]&&second[x]<second[y]);}
void pushdown(int x)
{
if(g[x])
{
g[t[x][]]^=;g[t[x][]]^=;
swap(t[x][],t[x][]);
g[x]=;
}
}
void count(int x)
{s[x]=s[t[x][]]++s[t[x][]];}
void rotate(int x)
{
int k=x==t[f[x]][];
int y=f[x];
t[y][k]=t[x][!k];f[t[x][!k]]=y;
if(f[y])t[f[y]][y==t[f[y]][]]=x;f[x]=f[y];f[y]=x;
t[x][!k]=y;s[x]=s[y];//因为已经pushdown了所以不用传翻转标记
count(y);
}
void splay(int &r,int x)
{
int tot=;
for(int i=x;i!=r;i=f[i])node[++tot]=i;node[++tot]=r;
for(int i=tot;i>=;i--)pushdown(node[i]);
for(int fa=f[r];f[x]!=fa;)
{
if(f[f[x]]==fa){rotate(x);break;}//return之前要记得传参……所以还是break好……
int X=x==t[f[x]][],Y=f[x]==t[f[f[x]]][];
if(X^Y)rotate(x),rotate(x);
else rotate(f[x]),rotate(x);
}
r=x;
}
void find(int &r,int k)
{
for(int x=r;x;)
{
pushdown(x);
if(k<=s[t[x][]]){x=t[x][];continue;}
if(k==s[t[x][]]+){splay(r,x);return;}
k-=s[t[x][]]+;x=t[x][];
}
}
void build(int fa,int &x,int l,int r)
{
if(l>r)return;
int mid=(l+r)>>;
x=a[mid];f[x]=fa;g[x]=;s[x]=;
build(x,t[x][],l,mid-);
build(x,t[x][],mid+,r);
count(x);
}
//void writes()
//{
// printf("------------------------------------------\n");
// for(int i=0;i<=n+2;i++)printf("[%d]t1=%d t2=%d fa=%d g=%d s=%d\n",i,t[i][0],t[i][1],f[i],g[i],s[i]);
// printf("------------------------------------------\n");
//}
int main()
{
n=read();
for(int i=;i<=n;i++)
{
first[i]=read();
second[i]=i;
ord[i]=i;
}
sort(ord+,ord+n+,cmp);
for(int i=;i<=n;i++)a[ord[i]]=i;
a[]=n+;a[n+]=n+;
build(,root,,n+);
for(int i=;i<=n;i++)
{
splay(root,i);
int p=s[t[root][]];
ans[i]=p;
find(root,i);
find(t[root][],p-i+);
g[t[t[root][]][]]^=;
}
for(int i=;i<n;i++)printf("%d ",ans[i]);
printf("%d",ans[n]);
return ;
}
update：现在已改用fhq-treap代替splay。