题解
这道题坑了我好久,其实不难,就是有个地方与模板不一样导致错误(死背模板的后果)
考虑用splay维护区间翻转,每次的翻转左边界是确定的,而右边界则是第i小的数所在位置
输入存在a数组里,按高度排序,每次我们就取出a[i].id,它的位置作为右边界,每次输出它的size
由于每次都单独地splay(a[i].id,rt) ,所以旋转的时候也要下放标记,其实以后都可以这样写,应该也不会T
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<bits/stdc++.h> using namespace std; const int MAXN=100004; int n,rt; int ch[MAXN][2],fa[MAXN],size[MAXN],rev[MAXN]; struct node{ int id,hight; bool operator<(const node& b){ if(hight!=b.hight)return hight<b.hight; else return id<b.id; } }a[MAXN]; inline void pushup(int x){ size[x]=size[ch[x][0]]+size[ch[x][1]]+1; } void pushdown(int x){ if(rev[x]){ swap(ch[x][0],ch[x][1]); rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]=0; } } void rotate(int x,int &k){ int y=fa[x],z=fa[y],kind; pushdown(y);pushdown(x); if(ch[y][0]==x)kind=1; else kind=0; if(y==k)k=x; else { if(ch[z][0]==y)ch[z][0]=x; else ch[z][1]=x; } ch[y][kind^1]=ch[x][kind]; fa[ch[y][kind^1]]=y; ch[x][kind]=y; fa[y]=x; fa[x]=z; pushup(x);pushup(y); } void splay(int x,int &k){ while(x!=k){ int y=fa[x],z=fa[y]; if(y!=k){ if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k); else rotate(y,k); } rotate(x,k); } } void build(int l,int r,int f){ if(l>r)return ; int mid=(l+r)/2; if(mid<f)ch[f][0]=mid;else ch[f][1]=mid; fa[mid]=f;size[mid]=1; if(l==r)return; build(l,mid-1,mid);build(mid+1,r,mid); pushup(mid); } int find(int x,int k){ pushdown(x);int s=size[ch[x][0]]; if(k==s+1)return x; if(k<=s)return find(ch[x][0],k); else return find(ch[x][1],k-s-1); } int main(){ scanf("%d",&n); rt=(n+3)/2; build(1,n+2,rt); for(int i=2;i<=n+1;i++){ scanf("%d",&a[i].hight); a[i].id=i; } sort(a+2,a+n+2); for(int i=2;i<=n+1;i++){ splay(a[i].id,rt); int ans=size[ch[rt][0]]+1; printf("%d ",ans-1); int x1=find(rt,i-1); int y1=find(rt,ans+1); splay(x1,rt);splay(y1,ch[x1][1]); rev[ch[y1][0]]^=1; } return 0; } |