rand()的一次mle

P3369 【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题,我们参考第一篇满是注释的题解,写出一个很像的代码

众所周知,Windows系统下rand()取值为0-32000左右,dat为一个差不多的正数


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5,INF=1e9;
int n;

class treap{
    public:
        int val[N],dat[N],ch[N][2],tot,size[N],cnt[N],root;
        int _new(int x){
            val[++tot]=x;
            dat[tot]+=rand()+N;
            size[tot]=1;
            cnt[tot]=1;
            return tot;
        }
        void pushup(int u){
            size[u]=size[ch[u][0]]+size[ch[u][1]]+cnt[u];
        }
        void built(){
            root=_new(-INF);
        }
        void rotate(int &u,int d){
            int v=ch[u][d^1];
            ch[u][d^1]=ch[v][d];
            ch[v][d]=u;
            u=v;
            pushup(ch[u][d]),pushup(u);
        }
        void insert(int &u,int x){
            if(!u)
              {u=_new(x);return ;}
            if(x==val[u])
              cnt[u]++;
            else{
                int d=x<val[u]?0:1;
                insert(ch[u][d],x);
                if(dat[u]<dat[ch[u][d]]) rotate(u,d^1);
            }
            pushup(u);
        }
        void remove(int &u,int x){
            if(!u) return ;
            if(x==val[u]){
                if(cnt[u]>1){cnt[u]--;pushup(u);return ;}
                if(ch[u][0]||ch[u][1]){
                    int d=dat[ch[u][0]]>dat[ch[u][1]]?0:1;
                    rotate(u,d^1);
                    remove(u,x);
                }
                else
                  u=0;
                return ;
            }
            x<val[u]? remove(ch[u][0],x):remove(ch[u][1],x);
            pushup(u);
        }
        int get_rank(int u,int x){
            if(!u) return 0;
            if(x>val[u])  return size[ch[u][0]]+cnt[u]+get_rank(ch[u][1],x);
            if(x==val[u]) return size[ch[u][0]];
            if(x<val[u])  return get_rank(ch[u][0],x);
            return 0;
        }
        int get_val(int u,int x){
            if(size[ch[u][0]]>=x) return get_val(ch[u][0],x);
            if(size[ch[u][0]]+cnt[u]>=x) return val[u];
            return get_val(ch[u][1],x-size[ch[u][0]]-cnt[u]);
        }
        int get_pre(int u,int x){
            if(!u) return -INF;
            if(val[u]<x) return max(val[u],get_pre(ch[u][1],x));
            else return get_pre(ch[u][0],x);
        }
        int get_nex(int u,int x){
            if(!u) return INF;
            if(val[u]>x) return min(val[u],get_nex(ch[u][0],x));
            else return get_nex(ch[u][1],x);
        }
}t;

int main(){
    t.built();
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1) t.insert(t.root,x);
        if(opt==2) t.remove(t.root,x);
        if(opt==3) printf("%d\n",t.get_rank(t.root,x));
        if(opt==4) printf("%d\n",t.get_val(t.root,x+1));
        if(opt==5) printf("%d\n",t.get_pre(t.root,x));
        if(opt==6) printf("%d\n",t.get_nex(t.root,x));
    }
    return 0;
}

然后就会MLE

真是让人好奇啊,并且ll就AC了,反复测试后,发现rand出问题

随机函数 - OI Wiki (oi-wiki.org)于是乎,Linux的rand()直接开到int上线

所以

rand()要考虑ll取模!

rand()要考虑ll取模!

rand()要考虑ll取模!

鸣谢陈涣焕学长的指导

发表评论

邮箱地址不会被公开。 必填项已用*标注