萌新求教fhq连样例都过不去

henrytb @ 2019-08-04 13:49:44

by henrytb @ 2019-08-04 13:49:58

#include <bits/stdc++.h>
#define ls(rt) T[rt].lc
#define rs(rt) T[rt].rc
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=1e5+5;
struct node{
    int lc,rc,val,rnk,rev,sz;
}T[N];
int tot=1,n,m;
int add(int val){
    T[++tot].val=val;
    ls(tot)=rs(tot)=0;
    T[tot].sz=1;
    T[tot].rev=0;
    T[tot].rnk=rand();
    return tot;
}
void update(int rt){T[rt].sz=T[ls(rt)].sz+T[rs(rt)].sz+1;}
void pushdown(int rt){
    swap(ls(rt),rs(rt));
    T[ls(rt)].rev^=1;
    T[rs(rt)].rev^=1;
    T[rt].rev=0;
}
void split(int rt,int &a,int &b,int sz){
    if(!rt){
        a=b=0;
        return;
    }
    if(T[rt].rev)pushdown(rt);
    if(T[rt].sz<=sz){
        a=rt;
        //if(T[a].rev)pushdown(a);
        split(rs(rt),rs(a),b,sz);
    } else {
        b=rt;
        //if(T[b].rev)pushdown(b);
        split(ls(rt),a,ls(b),sz);
    }
    update(rt);
}
void merge(int &rt,int a,int b){
    if(!a||!b){
        rt=a+b;
        return;
    }
    if(T[a].rev)pushdown(a);
    if(T[b].rev)pushdown(b);
    if(T[a].rnk<T[b].rnk){
        rt=a;
        merge(rs(rt),rs(a),b);
    } else {
        rt=b;
        merge(ls(rt),a,ls(b));
    }
    update(rt);
}
void insert(int &rt,int val){
    int a=0,b=0,newnode=add(val);
    split(rt,a,b,val);
    merge(a,a,newnode);
    merge(rt,a,b);
}
void print(int rt){
    if(!rt)return;
    if(T[rt].rev)pushdown(rt);
    print(ls(rt));
    printf("%d ",T[rt].val);
    print(rs(rt));
}
int main(){
    int root=0;
    srand(19260817);
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        insert(root,i);
    }
    rep(i,1,m){
        int l,r;
        scanf("%d%d",&l,&r);
        int x=0,y=0,z=0;
        split(root,x,y,l-1);
        split(y,y,z,r-l+1);
        T[y].rev^=1;
        merge(y,y,z);
        merge(root,x,y);
    }
    print(root);
    return 0;
}

by XeCtera @ 2019-08-04 13:54:57

srand什么？

by henrytb @ 2019-08-04 13:56:17

。。。不要在意这些细节