# 70分求助

@绝顶我为峰  2020-02-14 17:23 回复

QAQ，求大佬帮忙

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct num
{
int id,val;
bool operator <(const num &other) const
{
return val^other.val? val<other.val:id<other.id;
}
}a[1000005];
int n,rt,tot,fa[1000005],ch[1000005][2],cnt[1000005],val[1000005],sz[1000005],tag[1000005];
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void maintain(int x)
{
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
inline bool get(int x)
{
return x==ch[fa[x]][1];
}
inline void push_down(int x)
{
if(tag[x])
{
tag[ch[x][0]]^=1;
tag[ch[x][1]]^=1;
ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];
tag[x]=0;
}
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y];
push_down(y);
push_down(x);
int k=get(x);
ch[y][k]=ch[x][k^1];
fa[ch[x][k^1]]=y;
ch[x][k^1]=y;
fa[y]=x;
fa[x]=z;
if(z)
ch[z][y==ch[z][1]]=x;
maintain(y);
maintain(x);
}
inline void splay(int x,int goal)
{
for(register int f;(f=fa[x])!=goal;rotate(x))
if(fa[f]!=goal)
rotate(get(f)==get(x)? f:x);
if(!goal)
rt=x;
}
inline int kth(int k)
{
int node=rt;
while(1)
{
push_down(node);
if(ch[node][0]&&k<=sz[ch[node][0]])
node=ch[node][0];
else
{
k-=sz[ch[node][0]]+cnt[node];
if(k<=0)
return node;
node=ch[node][1];
}
}
}
inline void build(int l,int r,int f)
{
if(l>r)
return;
int mid=(l+r)>>1;
if(mid<f)
ch[f][0]=mid;
else
ch[f][1]=mid;
sz[mid]=cnt[mid]=1;
fa[mid]=f;
if(l==r)
return;
build(l,mid-1,mid);
build(mid+1,r,mid);
maintain(mid);
}
inline void update(int k)
{
splay(a[k].id,0);
printf("%d ",sz[ch[rt][0]]);
int x=kth(k-1);
int y=kth(sz[ch[rt][0]]+2);
splay(x,0);
splay(y,x);
tag[ch[ch[rt][1]][0]]^=1;
}
int main()
{
a[1].id=1;
a[1].val=-1<<20;
a[n+2].id=n+2;
a[n+2].val=1<<20;
for(register int i=2;i<=n+1;++i)
{
a[i].id=i;
}
sort(a+1,a+n+3);
build(1,n+2,0);
rt=(n+3)>>1;
for(register int i=2;i<=n;++i)
update(i);
printf("%d\n",n);
return 0;
}
@hly1204 2020-02-14 17:39 回复 举报

kth的pushdown我会写在最前面和循环最后，不过这题有个简化的做法不用kth