为什么改掉read之后就A了？

zhengjiawei @ 2022-07-28 16:45:57

by zhengjiawei @ 2022-07-28 16:46:41

我写的是带旋的Treap

by Register_int @ 2022-07-28 16:49:21

@zhengjiawei 您好，代码

by zhengjiawei @ 2022-07-28 16:49:54

这是改之前的代码

#include<bits/stdc++.h>

const int INF=0x7fffffff;

using namespace std;

int n,m,tot,last,root,x,opt,ans;

struct Treap{
    int l,r;
    int val,dat;
    int cnt,size; 
}a[1100005];

int New(int val){
    a[++tot].val=val;
    a[tot].dat=rand();
    a[tot].size=a[tot].cnt=1;
    return tot;
}

void update(int p){
    a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;
}

void build(){
    New(-INF);New(INF);
    root=1;a[1].r=2;
    update(root); 
}

void zig(int &p){
    int q=a[p].l;a[p].l=a[q].r,a[q].r=p;p=q;
    update(a[p].r);update(p);
}

void zag(int &p){
    int q=a[p].r;a[p].r=a[q].l,a[q].l=p;p=q;
    update(a[p].l);update(p);
}

void insert(int &p,int val){
    if(!p){
        p=New(val);
        return;
    }
    if(a[p].val==val){
        a[p].cnt++;
    } 
    if(a[p].val<val){
        insert(a[p].r,val);
        if(a[p].dat<a[a[p].r].dat)
            zag(p);
    }
    else if(a[p].val>val){
        insert(a[p].l,val);
        if(a[p].dat<a[a[p].l].dat)
            zig(p);
    }
    update(p);
}

void remove(int &p,int val){
    if(!p) return;
    if(a[p].val==val){
        if(a[p].cnt>1){
            a[p].cnt--;
            update(p);
            return;
        }
        if(a[p].l||a[p].r){
            if(!a[p].r||a[a[p].l].dat>a[a[p].r].dat){
                zig(p);
                remove(a[p].r,val);
            }
            else{
                zag(p);
                remove(a[p].l,val);
            }
            update(p);
        }
        else
            p=0;
        return;
    }
    val<a[p].val?remove(a[p].l,val):remove(a[p].r,val);
    update(p);
}

int getrank(int p,int val){
    if(!p) return 1;
    if(a[p].val==val) return a[a[p].l].size+1;
    if(val<a[p].val) return getrank(a[p].l,val);
    return getrank(a[p].r,val)+a[a[p].l].size+a[p].cnt;
}

int getval(int p,int rank){
    if(!p) return INF;
    if(a[a[p].l].size>=rank) return getval(a[p].l,rank);
    if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
    return getval(a[p].r,rank-a[a[p].l].size-a[p].cnt); 
}

int getpre(int val){
    int p=root,ans=1;
    while(p){
        if(a[p].val==val){
            p=a[p].l;
            while(a[p].r) p=a[p].r;
        } 
        if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
        p=val<a[p].val?a[p].l:a[p].r;
    } 
    return a[ans].val;
}

int getnext(int val){
    int ans=2,p=root;
    while(p){
        if(a[p].val==val){
            p=a[p].r;
            while(a[p].l) p=a[p].l;
        } 
        if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
        p=val<a[p].val?a[p].l:a[p].r; 
    } 
    return a[ans].val;
}

int read(int &x){
    int w=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            f=-1;
        c=getchar();
    }   
    while(c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+c-'0';
        c=getchar();
    }
    x=w*f;
}

int main(){
    srand(time(0));
    build();
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(x);
        insert(root,x);
    }
    for(int i=1;i<=m;i++){
        read(opt);read(x);
        x^=last;
        switch(opt){
            case 1:
                insert(root,x);
                break;
            case 2:
                remove(root,x);
                break;
            case 3:
                last=getrank(root,x)-1,ans^=last;
                break;
            case 4:
                last=getval(root,x+1),ans^=last;
                break;
            case 5:
                last=getpre(x),ans^=last;
                break;
            case 6:
                last=getnext(x),ans^=last;
                break;
        } 
    }
    printf("%d\n",ans);
    return 0;
} 

这是改之后的代码

#include<bits/stdc++.h>

const int INF=0x7fffffff;

using namespace std;

int n,m,tot,last,root,x,opt,ans;

struct Treap{
    int l,r;
    int val,dat;
    int cnt,size; 
}a[1100005];

int New(int val){
    a[++tot].val=val;
    a[tot].dat=rand();
    a[tot].size=a[tot].cnt=1;
    return tot;
}

void update(int p){
    a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;
}

void build(){
    New(-INF);New(INF);
    root=1;a[1].r=2;
    update(root); 
}

void zig(int &p){
    int q=a[p].l;a[p].l=a[q].r,a[q].r=p;p=q;
    update(a[p].r);update(p);
}

void zag(int &p){
    int q=a[p].r;a[p].r=a[q].l,a[q].l=p;p=q;
    update(a[p].l);update(p);
}

void insert(int &p,int val){
    if(!p){
        p=New(val);
        return;
    }
    if(a[p].val==val){
        a[p].cnt++;
    } 
    if(a[p].val<val){
        insert(a[p].r,val);
        if(a[p].dat<a[a[p].r].dat)
            zag(p);
    }
    else if(a[p].val>val){
        insert(a[p].l,val);
        if(a[p].dat<a[a[p].l].dat)
            zig(p);
    }
    update(p);
}

void remove(int &p,int val){
    if(!p) return;
    if(a[p].val==val){
        if(a[p].cnt>1){
            a[p].cnt--;
            update(p);
            return;
        }
        if(a[p].l||a[p].r){
            if(!a[p].r||a[a[p].l].dat>a[a[p].r].dat){
                zig(p);
                remove(a[p].r,val);
            }
            else{
                zag(p);
                remove(a[p].l,val);
            }
            update(p);
        }
        else
            p=0;
        return;
    }
    val<a[p].val?remove(a[p].l,val):remove(a[p].r,val);
    update(p);
}

int getrank(int p,int val){
    if(!p) return 1;
    if(a[p].val==val) return a[a[p].l].size+1;
    if(val<a[p].val) return getrank(a[p].l,val);
    return getrank(a[p].r,val)+a[a[p].l].size+a[p].cnt;
}

int getval(int p,int rank){
    if(!p) return INF;
    if(a[a[p].l].size>=rank) return getval(a[p].l,rank);
    if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
    return getval(a[p].r,rank-a[a[p].l].size-a[p].cnt); 
}

int getpre(int val){
    int p=root,ans=1;
    while(p){
        if(a[p].val==val){
            p=a[p].l;
            while(a[p].r) p=a[p].r;
        } 
        if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
        p=val<a[p].val?a[p].l:a[p].r;
    } 
    return a[ans].val;
}

int getnext(int val){
    int ans=2,p=root;
    while(p){
        if(a[p].val==val){
            p=a[p].r;
            while(a[p].l) p=a[p].l;
        } 
        if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
        p=val<a[p].val?a[p].l:a[p].r; 
    } 
    return a[ans].val;
}

void read(int &x){
    int w=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+c-'0';
        c=getchar();
    }
    x=w;
}

int main(){
    srand(time(0));
    build();
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(x);
        insert(root,x);
    }
    for(int i=1;i<=m;i++){
        read(opt);read(x);
        x^=last;
        switch(opt){
            case 1:
                insert(root,x);
                break;
            case 2:
                remove(root,x);
                break;
            case 3:
                last=getrank(root,x)-1,ans^=last;
                break;
            case 4:
                last=getval(root,x+1),ans^=last;
                break;
            case 5:
                last=getpre(x),ans^=last;
                break;
            case 6:
                last=getnext(x),ans^=last;
                break;
        } 
    }
    printf("%d\n",ans);
    return 0;
} 

by zhengjiawei @ 2022-07-28 16:50:26

@Register_int发上来了

by lrq090403 @ 2022-07-28 17:01:28

两份代码只有这两处差异（int->void,signed unsigned）。

int read(int &x){
    int w=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+c-'0';
        c=getchar();
    }
    x=w*f;
}

void read(int &x){
    int w=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+c-'0';
        c=getchar();
    }
    x=w;
}

by 野生小卒 @ 2022-07-28 17:03:28

是从wa变成a还是从tle变成a

by _cyle_King @ 2022-07-28 17:08:03

@zhengjiawei 函数没有返回值会厌氧的。

by zhengjiawei @ 2022-07-28 21:29:14

@野生小卒 是从MLE到AC