萌新平衡树板子全WA求助，悬3关

_O_v_O_ @ 2024-08-01 23:51:51

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(x) tr[x].lson
#define rs(x) tr[x].rson

const int N=1e5+5;
int n,m,a,last,ans;
struct fhq{
    struct node{int lson,rson;int val,pri;int siz,lazy;};
    int root;node tr[N];
    void pushup(int x){tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}
    void pushdown(int x){
        swap(ls(x),rs(x));
        tr[ls(x)].lazy^=1;tr[rs(x)].lazy^=1;
        tr[x].lazy=0;
    }
    void newnode(int x){tr[x]={0,0,x,rand(),1,0};}
    void split(int u,int v,int &x,int &y){
        if(!u){x=y=0;return;}
        if(tr[u].lazy) pushdown(u);
        if(tr[ls(u)].siz+1<=v) x=u,split(rs(u),v-tr[ls(u)].siz-1,rs(u),y);
        else y=u,split(ls(u),v,x,ls(u));
        pushup(u);
    }
    int merge(int x,int y){
        if(!x||!y) return x+y;
        if(tr[x].pri<tr[y].pri){
            if(tr[x].lazy) pushdown(x);
            rs(x)=merge(rs(x),y);pushup(x);return x;
        }
        else{
            if(tr[y].lazy) pushup(y);
            ls(y)=merge(x,ls(y));pushup(y);return y;
        }
    }
    void rev(int l,int r){
        int x,y,p;
        split(root,r,x,y),split(x,l-1,x,p);
        tr[p].lazy^=1;
        root=merge(merge(x,p),y);
    }
    void print(int x){
        if(tr[x].lazy) pushdown(x);
        if(ls(x)) print(ls(x));
        cout<<tr[x].val<<' ';
        if(rs(x)) print(rs(x));
    }
};
fhq tr;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    srand(time(0));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        tr.newnode(i),tr.root=tr.merge(tr.root,i);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        tr.rev(l,r);
    }
    tr.print(tr.root);
    return 0;
}

by Lu_xZ @ 2024-08-02 00:54:51

@_O_vO

死因：

自己看吧（）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(x) tr[x].lson
#define rs(x) tr[x].rson

const int N=1e5+5;
int n,m,a,last,ans;
struct fhq{
    struct node{int lson,rson;int val,pri;int siz,lazy;};
    int root;node tr[N];
    void pushup(int x){tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}
    void pushdown(int x){
        swap(ls(x),rs(x));
        tr[ls(x)].lazy^=1;tr[rs(x)].lazy^=1;
        tr[x].lazy=0;
    }
    void newnode(int x){tr[x]={0,0,x,rand(),1,0};}
    void split(int u,int v,int &x,int &y){
        if(!u){x=y=0;return;}
        if(tr[u].lazy) pushdown(u);
        if(tr[ls(u)].siz+1<=v) x=u,split(rs(u),v-tr[ls(u)].siz-1,rs(u),y);
        else y=u,split(ls(u),v,x,ls(u));
        pushup(u);
    }
    int merge(int x,int y){
        if(!x||!y) return x+y;
        if(tr[x].pri<tr[y].pri){
            if(tr[x].lazy) pushdown(x);
            rs(x)=merge(rs(x),y);pushup(x);return x;
        }
        else{
            if(tr[y].lazy) pushup(y);               // <----  
            ls(y)=merge(x,ls(y));pushup(y);return y;
        }
    }
    void rev(int l,int r){
        int x,y,p;
        split(root,r,x,y),split(x,l-1,x,p);
        tr[p].lazy^=1;
        root=merge(merge(x,p),y);
    }
    void print(int x){
        if(tr[x].lazy) pushdown(x);
        if(ls(x)) print(ls(x));
        cout<<tr[x].val<<' ';
        if(rs(x)) print(rs(x));
    }
};
fhq tr;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    srand(time(0));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        tr.newnode(i),tr.root=tr.merge(tr.root,i);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        tr.rev(l,r);
    }
    tr.print(tr.root);
    return 0;
}

by _O_v_O_ @ 2024-08-02 10:30:14

@Lu_xZ ok

by _O_v_O_ @ 2024-08-02 16:40:51

草