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];
inline int read()
{
    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()
{
    n=read();
    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].val=read();
        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

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。