wkjfive @ 2023-01-30 09:44:35

by wkjfive @ 2023-01-30 09:49:04

13仅用时3.04s

https://www.luogu.com.cn/record/100764140

//P6136 【模板】普通平衡树（加强版）96分TLE#13 
#include<bits/stdc++.h>
#include<time.h>
using namespace std;
const int N=1100066,INF=INT_MAX;
inline int fread(){
    int ans=0,d=1; char ch='\0';
    while(!('0'<=ch&&ch<='9')) ch=='-'?d=-d:0,ch=getchar();
    while('0'<=ch&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*d;
}
typedef int Tp;
int n,q,tot=0,rt=0;
int val[N],siz[N],pr[N],cnt[N];//数据,节点数,优先级,副本数 
//优先级大的靠上，0的优先级为0 
int son[N][2];//左右孩子 
inline int neww(Tp v)/*建点*/{
    ++tot;
    val[tot]=v,siz[tot]=1,pr[tot]=rand()+1,cnt[tot]=1;
    return tot;
}
inline void upd(int x)/*更新节点数*/{
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];
}
inline void build()/*初始化*/{
    rt=neww(INF);
    son[rt][0]=neww(-INF),upd(rt);
}
void rotate(int &x,int d)/*左旋0/右旋1*/ {
    int y=son[x][d^1];
    son[x][d^1]=son[y][d];
    son[y][d]=x;
    upd(x),upd(y);
    x=y;
}
void insert(int &x,Tp v)/*插入*/{
    if(x==0){x=neww(v); return;}
    if(v==val[x]) cnt[x]++;
    else{
        int d=v<val[x]?0:1;//插入左/右 
        insert(son[x][d],v);
        if(pr[x]<pr[son[x][d]]) rotate(x,d^1); //与插入的交换 
    }
    upd(x);
}
void remove(int &x,Tp v)/*删除*/{
    if(x==0) return;//找不到 
    if(v==val[x])/*检索到*/{
        if(cnt[x]>1){cnt[x]--,upd(x); return;}//有副本 
        if(son[x][0]==0&&son[x][1]==0){x=0;return;}//叶子节点 
        if(son[x][1]==0||pr[son[x][0]>pr[son[x][1]]])
            rotate(x,1),remove(son[x][1],v);//与左孩子交换 
        else 
            rotate(x,0),remove(son[x][0],v);//与右孩子交换 
    }else{
        int d=v<val[x]?0:1;//删除左/右 
        remove(son[x][d],v);
    } upd(x);
}
int grank(int x,Tp v){
    if(x==0) return 1;//找不到,排名定义为比x小的数个数+1 
    if(v<val[x]) return grank(son[x][0],v);//左 
    else if(v==val[x]) return siz[son[x][0]]+1;//该点 
    else return siz[son[x][0]]+cnt[x]+grank(son[x][1],v);//右 
}
int gval(int x,int rnk){
    if(x==0) return INF;//向右找不到 
    if(rnk<=siz[son[x][0]]) return gval(son[x][0],rnk);//左 
    else if(rnk<=siz[son[x][0]]+cnt[x]) return val[x];//该点 
    else return gval(son[x][1],rnk-siz[son[x][0]]-cnt[x]);//右 
}
inline Tp gpre(Tp v){
    int x=rt; Tp pre;
    while(x){
        if(v>val[x]) pre=val[x],x=son[x][1];//右 
        else x=son[x][0];//左 
    }
    return pre;
}
inline Tp gnxt(Tp v){
    int x=rt; Tp nxt;
    while(x){
        if(v<val[x]) nxt=val[x],x=son[x][0];//左 
        else x=son[x][1];//右 
    }
    return nxt;
}

int main(int argc,char* args[]){
    srand(time(NULL)); build();
    n=fread(),q=fread();
    for(int i=1;i<=n;i++){
        int ai=fread(); insert(rt,ai);
    }
    int lst=0,ans=0;
    for(int i=1;i<=q;i++){
        int t=fread(),x=fread();
        x^=lst;
        if(t==1) insert(rt,x);
        if(t==2) remove(rt,x);
        if(t==3) ans^=(lst=grank(rt,x)-1);//减去-INF节点 
        if(t==4) ans^=(lst=gval(rt,x+1));//加上-INF节点 
        if(t==5) ans^=(lst=gpre(x));
        if(t==6) ans^=(lst=gnxt(x));
        if(t>=3) printf("{%d,%d}=%d\n",t,x,lst); 
        else printf("{%d,%d}\n",t,x);
    }
    printf("%d",ans);
    return 0;
}

by 小明小红 @ 2023-01-30 09:50:19

换个算法？用splay或fhq？

by Loser_Syx @ 2023-01-30 09:56:48

@wkjfive 你这代码好坑啊，数组删小点就过了，

const int N=1100006,INF=INT_MAX;
typedef int Tp;
int n,q,tot,rt,lst,ans;
int val[N],siz[N],pr[N],cnt[N];//数据,节点数,优先级,副本数 

by wkjfive @ 2023-01-30 10:22:50

过不了

by wkjfive @ 2023-01-30 10:49:32

好像有时能过有时过不了

by Ming_Yu @ 2023-01-30 16:30:38

巨佬orz太强力