Splay求调

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();int x=0;bool f=1;
    while(ch<'0'||'9'<ch){if(ch=='-')f=0;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}
int n,m;
const int N=1e5+5,inf=0x3f3f3f3f;
int id[N];
#define ls(x) spl[x].ch[0]
#define rs(x) spl[x].ch[1]
struct node{
    int fa,ch[2],val,siz,lazy;
}spl[N];
int cnt,root=0;
void newnode(int &now,int fa,int val){
    spl[now=++cnt].val=val;
    spl[now].fa=fa;
    spl[now].siz=1;
    spl[now].lazy=0;
    id[val]=cnt;
}
inline void update(int now){
    spl[now].siz=spl[ls(now)].siz+spl[rs(now)].siz+1;
}
inline void pushdown(int now){
    if(spl[now].lazy){
        swap(ls(now),rs(now));
        spl[ls(now)].lazy^=1;
        spl[rs(now)].lazy^=1;
        spl[now].lazy=0;
    }
    return;
}
inline bool ident(int x,int f){return rs(f)==x;}
inline void connect(int x,int f,int s){
    spl[f].ch[s]=x;spl[x].fa=f;
}
inline void rotate(int x){
    int f=spl[x].fa,ff=spl[f].fa;
    pushdown(f);pushdown(x);
    int k=ident(x,f);
    connect(spl[x].ch[k^1],f,k);
    connect(x,ff,ident(f,ff));
    connect(f,x,k^1);
    update(f),update(x);
}
void splaying(int x,int top){
    if(!top)root=x;
    while(spl[x].fa!=top){
        int f=spl[x].fa,ff=spl[f].fa;
        if(ff!=top)ident(f,ff)^ident(x,f)?rotate(x):rotate(f);
        rotate(x);
    }
}
inline int suf(){
    int now=root;
    pushdown(now);
    now=rs(now);
    while(ls(now))pushdown(now),now=ls(now);
    return now;
}
pair<int,int>a[N];
void build(int l,int r,int &now,int fa){
    int mid=(l+r)>>1;
    newnode(now,fa,a[mid-1].second);
    if(l<mid)build(l,mid-1,ls(now),now);
    if(mid<r)build(mid+1,r,rs(now),now);
    update(now);
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)a[i]={read(),i};
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)a[i]={a[i].second,i};
    sort(a+1,a+n+1);
    a[0]={0,0};
    a[n+1]={n+1,n+1};
    build(1,n+2,root,0);
    for(int i=1;i<=n;i++){
        int l=id[i-1],r=id[i];
        splaying(r,0);
        printf("%d ",spl[ls(r)].siz);
        r=suf();
        splaying(l,0);splaying(r,l);
        spl[ls(r)].lazy^=1;
    }
    return 0;
}