[文章目录]
Description
1<=N<=100000
splay。发现还有坑啊。
有影响查询的标记，并且只能定位节点地址的查询怎么办？？？
由于标记下传是不影响节点的fa的，所以，我们可以将路径上的节点扔到栈里，然后一路pushdown。
如果是查排名的话，其实还可以进行递归，由于儿子的排名跟父亲的排名有一定的关系，所以先查询父亲的排名，将其pushdown，再计算当前节点的排名，注意root需要pushdown。
两种方法好像都可以，感性理解上感觉好像第一种全能一些。
建树的时候维护序列，然后下标为rank，便于直接找节点。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
struct ques
{
int w,id,rank;
}a[101000];
bool cmp(ques x,ques y){return x.w==y.w?x.id<y.id:x.w<y.w;}
bool cmp1(ques x,ques y){return x.id<y.id;}
struct node
{
node *fa,*c[2];
bool tur;int siz;
node();
void pushup(){siz=c[0]->siz+c[1]->siz+1;}
void reverse(){swap(c[0],c[1]); tur^=1;}
void pushdown();
}*null=new node(),*root,*tre[101000];
node:: node()
{
fa=c[0]=c[1]=null;
siz=null?1:0;
tur=0;
}
void node:: pushdown()
{
if(tur)
{
if(c[0]!=null) c[0]->reverse();
if(c[1]!=null) c[1]->reverse();
tur^=1;
}
}
node *build(int l,int r)
{
if(r<l) return null;
int mid=l+r>>1;
tre[a[mid].rank]=new node();
tre[a[mid].rank]->c[0]=build(l,mid-1);
tre[a[mid].rank]->c[1]=build(mid+1,r);
tre[a[mid].rank]->c[0]->fa=tre[a[mid].rank];
tre[a[mid].rank]->c[1]->fa=tre[a[mid].rank];
tre[a[mid].rank]->pushup();
}
void initialize()
{
root=new node();
root->c[1]=new node();
root->c[1]->fa=root;
root->c[1]->c[0]=build(1,n);
root->c[1]->c[0]->fa=root->c[1];
root->c[1]->pushup();
root->pushup();
}
int getrank(node *x)//返回节点左面的节点个数
{
if(root==x) {x->pushdown(); return x->c[0]->siz;}
int tmp=getrank(x->fa);
x->pushdown();
if(x==x->fa->c[0]) return tmp-x->c[1]->siz-1;
else return tmp+x->c[0]->siz+1;
}
void rotate(node *x)
{
node *y=x->fa; bool l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->fa=y->fa; x->c[r]=y;
if(y==y->fa->c[0]) y->fa->c[0]=x;
else y->fa->c[1]=x;
y->fa=x; y->pushup(); x->pushup();
if(root==y) root=x;
}
void splay(node *x,node *tar)
{
while(x->fa!=tar)
{
node *y=x->fa,*z=y->fa;
if(z==tar) {rotate(x); break;}
if((x==y->c[0])^(y==z->c[0])) rotate(x);
else rotate(y); rotate(x);
}
}
void find(node *x,int y,node *z)
{
while(1)
{
x->pushdown();
if(y<=x->c[0]->siz) x=x->c[0];
else
{
y-=x->c[0]->siz+1;
if(!y) break;
x=x->c[1];
}
}
splay(x,z);
}
void Reverse(int l,int r)
{
find(root,l,null);
find(root,r+2,root);
root->c[1]->c[0]->reverse();
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].w);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++) a[i].rank=i;
sort(a+1,a+n+1,cmp1);
initialize();
for(int i=1;i<=n;i++)
{
int tmp=getrank(tre[i]);
printf("%d%c",tmp,(i==n)?'\n':' ');
Reverse(i,tmp);
}
return 0;
}