萌新刚学Splay,求大佬改错(啊啊~~)!

P3391 【模板】文艺平衡树

pkh68 @ 2018-09-30 09:10:39


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define N 100010
#define re register
#define lc node[u].ch[0]
#define rc node[u].ch[1]
using namespace std;
int n,m,seq[N];
struct Node{
    int v,ch[2],flip,size;
    Node(){}
    Node(int a ,int b,int c,int d,int e){ v=a,ch[0]=b,ch[1]=c,flip=d;size=e; }
}node[N];
int cmp(int u,int k){ int d=k-node[lc].size;if(d==1) return -1;return d<=0?0:1; }
void Maintain(int u){ node[u].size=1+node[lc].size+node[rc].size; }
void PushDown(int u){
    if(node[u].flip){
        node[u].flip=0;
        swap(lc,rc);node[lc].flip=!node[lc].flip;node[rc].flip=!node[rc].flip;
    }
}
void rotate(int &u,int d){
    int k=node[u].ch[d^1];node[u].ch[d^1]=node[k].ch[d];node[k].ch[d]=u;
    Maintain(u);Maintain(k);u=k;
}
void splay(int &u,int k){
    PushDown(u);
    int d=cmp(u,k);
    if(d==1) k-=node[lc].size+1;
    if(d!=-1){
        int p=node[u].ch[d];
        PushDown(p);
        int d2=cmp(p,k);
        int k2=(d2==0?k:k-node[node[p].ch[0]].size-1);
        if(d2!=-1){ splay(node[p].ch[d2],k2);if(d==d2) rotate(u,d^1);else rotate(node[u].ch[d],d);}
        rotate(u,d^1);
    }
}
int merge(int left,int right){
    splay(left,node[left].size);
    node[left].ch[1]=right;
    Maintain(left);
    return left;
}
void split(int u,int k,int &left,int &right){
    splay(u,k);
    left=u;right=rc;rc=0;
    Maintain(left);
}
struct Splay{
    int tot=0,root;
    int Build(int sz){
        if(!sz) return 0;
        int sn=++tot,l=Build(sz>>1);
        node[tot]=Node(tot,l,Build(sz-(sz>>1)-1),0,0);
        Maintain(sn);
        return sn;
    }
}s;
vector<int> ans;
void print(int u){ if(u){ PushDown(u);print(lc);ans.push_back(node[u].v);print(rc); } }
int main(){
    scanf("%d%d",&n,&m);
    s.root=s.Build(n+1);
    for(re int i=1,l,r;i<=m;++i){
        scanf("%d%d",&l,&r);
        int left,mid,right,u;
        split(s.root,l,left,u);
        split(u,r-l+1,mid,right);
        node[mid].flip^=1;
        s.root=merge(merge(left,mid),right);
    }
    print(s.root);
    for(re int i=1;i<ans.size();++i) printf("%d\n",ans[i]);
    return 0;
}```

by aoweiyin @ 2018-09-30 09:13:48

感觉我又要惭愧一波了QAQ


by Danny_boodman @ 2018-09-30 09:13:58

为什么您要强调萌新呢?


by Danny_boodman @ 2018-09-30 09:15:01

@坐看云起时6b 捕捉大佬


by ACINE @ 2018-09-30 09:27:44

坐看云起时6b啊大佬!


by Ousmane_Dembele @ 2018-10-18 14:09:00

打破无蒟蒻的一帖


by 萌田薰子 @ 2018-10-25 22:46:44

打破只有一蒟蒻的一贴


|