求巨佬帮忙,为什么wa了

P3391 【模板】文艺平衡树

陈曦 @ 2018-07-31 21:13:11

求巨佬帮忙,为什么wa了,样例都过了

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 100010
using namespace std;
int n,m,val[maxn],rnd[maxn],son[maxn][3],size[maxn],sum_p;
int tag[maxn],root=0;
inline void read(int &x)
{
    x=0; 
    int f=1; 
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') 
        f=-1; 
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}
inline int newnode(int x)
{
    ++sum_p;size[sum_p]=1;
    val[sum_p]=x;rnd[sum_p]=rand();
    tag[sum_p]=0;
    return sum_p; 
}
inline void update(int x)
{
    size[x]=size[son[x][1]]+size[son[x][2]];   
    if(x&&tag[x])
    {
        tag[x]^=1;
        swap(son[x][1],son[x][2]);
        tag[son[x][1]]^=1,tag[son[x][2]]^=1;
    }
}
inline void split(int &x,int &y,int k,int pos)
{
    if(!pos)
    x=y=0;
    else
    {
        if(val[pos]<=k)
        {
            x=pos;
            split(son[pos][2],y,k,son[pos][2]);
        }
        else
        {
            y=pos;
            split(x,son[pos][1],k,son[pos][1]);
        }
        update(pos);
    }
}
inline int merge(int x,int y)
{
    if(x==0||y==0) return x+y;
    if(rnd[x]<rnd[y]) 
    {
        son[x][2]=merge(son[x][2],y);
        update(x);
        return x;
    }
    else
    {
        son[y][1]=merge(x,son[y][1]);
        update(y);
        return y;
    }
}
void rev(int l,int r)
{
    int a,b,c,d;
    split(a,b,r+1,root);
    split(c,d,l,a);
    tag[d]=1;
    root=merge(merge(c,d),b);
}
inline int find(int pos,int rank)
{
    while(1)
    {
        if(size[son[pos][1]]>=rank)
        {
            pos=son[pos][1];
        }
        else 
        if(size[son[pos][1]]+1==rank)
        return pos;
        else
        {
            rank-=size[son[pos][1]]+1;
            pos=son[pos][2];
        }
    }
}
inline void print(int x)
{
    if (!x) return;
    update(x);
    print(son[x][1]);
    if (val[x]>=1&&val[x]<=n) printf("%d ",val[x]);
    print(son[x][2]);
}
int main()
{
    srand((unsigned)time(NULL));
    read(n),read(m);
    int op,a,x,y,z,k,mid;
    for(register int i=1;i<=n;i++)
    {
        split(x,y,i,root);
        root=merge(merge(x,newnode(i)),y);
    }
    for(register int i=1;i<=m;i++)
    {
        read(op),read(a);
        rev(op-1,a-1);
    }
    print(root);
}

by Juanzhang @ 2018-08-02 17:26:09

splay


|