fhq_treap全WA求助

enor2017 @ 2018-11-19 19:22:56

#include<cstdio>
#include<algorithm>
#define isdigit(c) (c>='0'&&c<='9')
#define lc(x) e[x].lch
#define rc(x) e[x].rch
using namespace std;
typedef long long ll;
const ll MAXN=1e5+50;
struct Treap{
    ll size,lch,rch,val,key;
    ll rev;
}e[MAXN];
ll cnt=0,root=0,seed=233;
ll get_key(){
    return seed=(seed*19260817)%998244353;
}
ll newnode(ll val){
    e[++cnt].val=val;
    e[cnt].key=get_key();
    lc(cnt)=rc(cnt)=0;
    e[cnt].size=1;
    e[cnt].rev=0;
    return cnt;
}
void update(ll now){
    e[now].size=e[lc(now)].size+e[rc(now)].size+1;
}
void pushdown(ll now){
    if(lc(now)) e[lc(now)].rev^=1;
    if(rc(now)) e[rc(now)].rev^=1;
    swap(lc(now),rc(now));
    e[now].rev=0;
}
void split(ll now,ll &a,ll &b,ll val){
    if(now==0){
        a=b=0;
        return;
    }
    if(e[now].rev) pushdown(now);
    if(e[now].val<=val){
        a=now;
        split(rc(now),rc(a),b,val);
    }else{
        b=now;
        split(lc(now),a,lc(b),val);
    }
    update(now);
}
void merge(ll &now,ll a,ll b){
    if(a==0||b==0){
        now=a+b;
        return;
    }
    if(e[a].key<e[b].key){
        if(e[a].rev) pushdown(a);
        now=a;
        merge(rc(now),rc(a),b);
    }else{
        if(e[b].rev) pushdown(b);
        now=b;
        merge(lc(now),a,lc(b));
    }
    update(now);
}
void reverse(ll l,ll r){
    ll a=0,b=0,c=0;
    split(root,a,b,l-1);
    split(b,b,c,r-l+1);
    e[b].rev=(e[b].rev^1);
    merge(b,b,c);
    merge(root,a,b);
}
void dfs(ll x){
    if(!x) return;
    if(e[x].rev) pushdown(x);
    dfs(lc(x));
    printf("%lld ",e[x].val);
    dfs(rc(x));
}
int main(){
    ll n,m,l,r;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;++i) insert(i);
    while(m--){
        scanf("%lld%lld",&l,&r);
        reverse(l,r);
    }
    dfs(root);
    return 0;
}

by enor2017 @ 2018-11-20 22:36:17

没人QwQ

by Bobh @ 2018-11-24 21:25:01

你的insert函数在哪里

by xhhkwy @ 2018-12-02 21:23:32

@enor2017 fhq-Treap处理区间问题是不能按权分裂的哦...

by enor2017 @ 2018-12-02 22:20:30

@xhhkwy 谢dalao

by xhhkwy @ 2018-12-02 23:14:03

@enor2017 要写排名分裂的..

by COUPDETAT @ 2019-02-13 10:19:33

同求qwq

#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; 
}