fhq求救,样例过了

P3391 【模板】文艺平衡树

COUPDETAT @ 2019-02-13 10:18:05

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100101;
int n,m,root=0;
void read(int &n)
{
    char c='+';int x=0;bool flag=0;
    while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
    flag==1?n=-x:n=x;
}
int ch[MAXN][3],val[MAXN],pri[MAXN],siz[MAXN],tag[MAXN],sz;
void update(int x)
{
    siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]]; 
} 
void pushdown(int x) 
{
    if (x&&tag[x]) 
    {       
        tag[x]^=1;
        swap(ch[x][0],ch[x][1]);
        if (ch[x][0]) 
        tag[ch[x][0]]^=1;
        if (ch[x][1]) 
        tag[ch[x][1]]^=1;
    }
}
int new_node(int v)
{
    siz[++sz]=1;
    val[sz]=v;
    pri[sz]=rand();
    return sz; 
} 
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    pushdown(x),pushdown(y); 
    if(pri[x]<pri[y])
    {
        ch[x][1]=merge(ch[x][1],y);
        update(x);
        return x; 
    }   
    else
    {
        ch[y][0]=merge(x,ch[y][0]);
        update(y);
        return y; 
    } 
} 
void split(int now,int k,int &x,int &y)
{
    if(!now) x=y=0;
    else 
    {
    pushdown(now); 
    if(val[now]<=k)
        x=now,split(ch[now][1],k,ch[now][1],y);
    else
        y=now,split(ch[now][0],k,x,ch[now][0]); 
    update(now); 
    }
} 
int kth(int now,int k)
{
    while(1)
    {
        if(k<=siz[ch[now][0]])
            now=ch[now][0];
        else if(k==siz[ch[now][0]]+1)
            return now;
        else k-=siz[ch[now][0]]+1,now=ch[now][1]; 
    } 
} 
void rever(int l,int r)
{
    int a,b,c,d;
    split(root,r,a,b);
    split(a,l-1,c,d);
    tag[d]^=1;
    root=merge(merge(c,d),b); 
} 
void print(int x)
{
    if(!x) return ;
    pushdown(x);
    print(ch[x][0]);
    printf("%d ",val[x]);
    print (ch[x][1]); 
} 
int main()
{
    srand((unsigned)time(NULL));

    read(n),read(m);
    for(int i=1;i<=n;i++)
    {
        root=merge(root,new_node(i)); 
    } 
    while(m--)
    {
        int a,b;
        read(a),read(b);
        rever(a,b); 
    } 
    print(root); 
    return 0; 
} 

by 皎月半洒花 @ 2019-02-13 10:30:40

少年郎,数据结构当然是自己调啦……

建议自己copy一篇another kind的平衡树,写一个gen对拍一下qwq


by COUPDETAT @ 2019-02-13 10:52:39

@_皎月半洒花 好叭qwq哭辽


by Thomasguo666 @ 2019-02-14 20:19:53

@COUPDETAT split不能用val,要用siz。


by COUPDETAT @ 2019-02-14 21:31:36

@Thomasguo666 谢谢您了


|