fhq treap 求助!

P3391 【模板】文艺平衡树

Froggy @ 2019-05-31 21:13:32

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
#define N 100100
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<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int root,cnt=0,l,r,p,n,m;
struct node{
    int ch[2],val,key,siz,mark;
}t[N];
int NewNode(int data){
    int k=++cnt;
    t[k].val=data;
    t[k].key=rand();
    t[k].ch[0]=t[k].ch[1]=0;
    t[k].siz=1;
    return k;
}
void update(int k){
    t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+1;
}
void pushdown(int k){
    if(t[k].mark){
        swap(t[k].ch[0],t[k].ch[1]);
        if(t[k].ch[0])t[t[k].ch[0]].mark^=1;
        if(t[k].ch[1])t[t[k].ch[1]].mark^=1;
        t[k].mark=0;
    }
}
void Split(int k,int data,int &l,int &r){
    if(!k){
        l=r=0;
        return;
    }
    pushdown(k); 
    if(t[k].val<=data){
        l=k;
        Split(t[k].ch[1],data,t[k].ch[1],r);
    }
    else{
        r=k;
        Split(t[k].ch[0],data,l,t[k].ch[0]);
    }
    update(k);
}
int Merge(int l,int r){
    pushdown(l),pushdown(r);
    if(!l||!r)return l+r;
    if(t[l].key<t[r].key){
        t[l].ch[1]=Merge(t[l].ch[1],r);
        update(l);
        return l;
    }
    else{
        t[r].ch[0]=Merge(l,t[r].ch[0]);
        update(r);
        return r;
    }
}
void Insert(int data){
    Split(root,data,l,r);
    root=Merge(Merge(l,NewNode(data)),r);
}
void Reverse(int x,int y){
    Split(root,y,l,r);
    Split(l,x-1,l,p);
    t[p].mark^=1;
    root=Merge(Merge(l,p),r);
}
void output(int k){
    pushdown(k);
    if(t[k].ch[0])output(t[k].ch[0]);
    cout<<t[k].val<<" ";
    if(t[k].ch[1])output(t[k].ch[1]);
}
int main(){
    srand(time(NULL));
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        Insert(i);
    }
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        Reverse(x,y);
    }
    output(root);
    return 0;
}

by mathemagician @ 2019-05-31 21:22:35

split要根据siz吧


|