求助fhq

P3391 【模板】文艺平衡树

Prean @ 2020-05-01 14:10:38

直接输出1 2 3 4 5

我:。。。。。。

求助QwQ

Code:

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<ctime>
const int M=1e5+5;
class Treap
{
private:
    int s[M],val[M],rnd[M],lazy[M],chi[M][2];
    int cnt,root;
    int undate(int);
    void pushdown(int);
    int merge(int,int);
    void split(int,int,int&,int&);
public:
    int father();
    void push(int);
    void print(int);
    void swap(int,int);
}BST;
int Treap::undate(int now)
{
    s[now]=s[chi[now][0]]+s[chi[now][1]]+1;
}
void Treap::pushdown(int now)
{
    std::swap(chi[now][1],chi[now][0]);
    if(chi[now][0])lazy[chi[now][0]]^=1;
    if(chi[now][1])lazy[chi[now][1]]^=1;
    lazy[now]=0;
}
int Treap::merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(rnd[x]<rnd[y])
    {
        if(lazy[x])pushdown(x);
        return chi[x][1]=merge(chi[x][1],y),undate(x),x;
    }
    else
    {
        if(lazy[y])pushdown(y);
        return chi[y][0]=merge(x,chi[y][0]),undate(y),y;
    }
}
void Treap::split(int now,int k,int&x,int&y)
{
    if(!now)return(void)(x=y=0);
    if(lazy[now])pushdown(now);
    if(k<=s[chi[now][0]])split(chi[y=now][0],k,x,chi[now][0]);
    else split(chi[x=now][1],k-s[chi[now][0]]-1,chi[now][1],y);
    undate(now);
}
int Treap::father()
{
    return root;
}
void Treap::push(int value)
{
    int x,y;
    split(root,value,x,y);++cnt;
    s[cnt]=1;val[cnt]=value;rnd[cnt]=rand();
    root=merge(merge(x,cnt),y);
}
void Treap::print(int now)
{
    if(lazy[now])pushdown(now);
    if(chi[now][0])print(chi[now][0]);
    printf("%d ",val[now]);
    if(chi[now][1])print(chi[now][1]);
}
void Treap::swap(int L,int R)
{
    int x,y,z;
    split(root,R,x,z);split(x,L-1,x,y);
    lazy[x]^=1;root=merge(merge(x,y),z);
}
signed main(void)
{
    srand((unsigned)time(NULL));
    int n,m,L,R;scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)BST.push(i);
    while(m--)scanf("%d%d",&L,&R),BST.swap(L,R);BST.print(BST.father());
}

by serene_analysis @ 2020-05-02 12:01:30

我***


上一页 |