为什么第一个点就是过不去呢?

P6136 【模板】普通平衡树(数据加强版)

青阳buleeyes @ 2023-03-13 15:21:12

#include<bits/stdc++.h>
const int INF=0x7fffffff;
using namespace std;
const int N=1e6+10;
int root,tot,n,q;
struct splay_tree{
    int ff,cnt,ch[2],val,size;
}t[N];
int get(int x){
    int y=t[x].ff;
    return t[y].ch[0]==x?1:0;
}
void update(int x){
    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
inline void rotate(int x){
    int y=t[x].ff,z=t[y].ff,k=t[y].ch[1]==x;
    t[z].ch[t[z].ch[1]==y]=x;
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;
    update(y);
}
void splay(int x,int goal){
    for(int y=t[x].ff;y=t[x].ff,y!=goal;rotate(x)){
        if(t[y].ff!=goal) rotate(get(x)==get(y)?y:x);
    }
    if(goal==0) root=x;
    update(x);
}
inline void find(int x){
    int u=root;
    if(!u) return;
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}
inline void insert(int x){
    int u=root,ff=0;
    while(u&&t[u].val!=x){
        ff=u;u=t[u].ch[x>t[u].val];
    }
    if(u) t[u].cnt++,t[u].size++;
    else{
        u=++tot;
        if(ff) t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;
        t[tot].ff=ff;t[tot].val=x;
        t[tot].cnt=1;t[tot].size=1;
    }
    splay(u,0);
}
inline int Next(int x,int f){
    find(x);
    int u=root;
    if(t[u].val>x&&f) return u;
    if(t[u].val<x&&!f) return u;
    u=t[u].ch[f];
    while(t[u].ch[f^1]) u=t[u].ch[f^1];
    splay(u,0);
    return u;
}
inline void Delete(int x){
    int last=Next(x,0);
    int next=Next(x,1);
    splay(last,0);splay(next,last);
    int del=t[next].ch[0];
    if(t[del].cnt>1)
        t[del].cnt--,t[del].size--,splay(del,0);
    else t[next].ch[0]=0;
}
inline int kth(int x){
    int u=root;
    if(t[u].size<x) return 0;
    while(1){
        int y=t[u].ch[0];
        if(x>t[y].size+t[u].cnt){
            x-=t[y].size+t[u].cnt;
            u=t[u].ch[1];
        }
        else{
            if(t[y].size>=x) u=y;
            else{
                return splay(u,0),t[u].val;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    insert(INF),insert(-INF);
    int now=0,ans=0;
    for(int i=1,j;i<=n;++i)
        cin>>j,insert(j);
    int op,x;
    while(q--){
        cin>>op>>x;
        x^=now;
        if(op==1){
            insert(x);
        }
        else if(op==2){
            Delete(x);
        }
        else if(op==3){
            find(x);
            now=t[t[root].ch[0]].size;
            if(t[root].val<x) now+=t[root].cnt;
            ans^=now;
        }
        else if(op==4){
           now=kth(x+1);
           ans^=now;
        }
        else if(op==5){
            now=t[Next(x,0)].val;
            ans^=now;

        }
        else{
            now=t[Next(x,1)].val,ans^=now;
        } 
    }
    cout<<ans;
    return 0;
}

by 青阳buleeyes @ 2023-03-15 08:28:42

数组开小了


|