警示后人：如果你数据未加强版AC，却在只拿到了不到一半的分数

P6136 【模板】普通平衡树（数据加强版）

retamian @ 2023-10-15 20:15:05

可能原因1：

int getrank(int u, int key) {
    if (u == 0) return 1;//这里必须return 1，即使不存在比该值小的也应该加上自己
    if (tr[u].key == key) return tr[tr[u].l].size + 1;
    else if (tr[u].key > key) return getrank(tr[u].l, key);
    else return tr[tr[u].l].size + tr[u].cnt + getrank(tr[u].r, key);
}

可能原因2：

const int N = 2e6 + 10, INF = 2147483647;

检查你的数组有没有开到2e6？如果使用无穷大，是否大于2^{30}？只开1e9是不够的。

针对Treap选手，其他选手也可借鉴，被数据卡了好久。

by 262620zzj @ 2023-10-18 21:25:00

数组为什么要开到2e6啊

by 大眼仔Happy @ 2023-10-26 09:48:48

@retamian 第一个 return 1 好像在未加强版也要

by h_rains @ 2023-10-27 21:22:32

@262620zzj 实际上你只需要开到 1e6+1e5 因为你的数组大小实际上是你 insert 的次数/fad

by 262620zzj @ 2023-11-12 22:19:14

@h_rains 我开1.1\times 10^6 超空间怎么办

by WanderingTrader @ 2023-12-08 06:18:51

@retamian 谢谢，4pts -> 100pts

by Sakura_Love @ 2023-12-25 17:49:10

orz AC了

by w9095 @ 2024-07-04 14:20:01

orz thx

好人一生平安

|