Code:
#include <bits/stdc++.h>
using namespace std;
int tot = 0;
struct TreapNode* Null;
struct TreapNode {
TreapNode *lc, *rc;
int key, aux, size;
int id;
int sum[5];
TreapNode(int k = 0): key(k), aux(rand()), size(1), lc(Null), rc(Null) {fill(sum, sum + 5, 0); id = ++tot;}
void pushup() {
size = lc -> size + 1 + rc -> size;
for (int i = 0; i < 5; i++) {
sum[i] = lc -> sum[i];
// fprintf(stderr, "sum[%d] of node %d updated to %d\n", i, id, sum[i]);
}
int k = lc -> size;
sum[k % 5] += key;
// fprintf(stderr, "sum[%d] of node %d updated to %d\n", k % 5, id, sum[k % 5]);
k++;
for (int i = 0; i < 5; i++) {
sum[(k + i) % 5] += rc -> sum[i];
// fprintf(stderr, "sum[%d] of node %d updated to %d\n", k % 5, id, sum[k % 5]);
}
}
}*root;
int getRank(TreapNode* u, int v) {
// cerr << u -> id << endl;
if (u == Null) return 0;
return (v < u -> key) ? getRank(u -> lc, v): getRank(u -> rc, v) + u -> lc -> size + 1;
}
typedef pair <TreapNode*, TreapNode*> PNN;
PNN split(TreapNode* u, int k) {
if (u == Null) return make_pair(Null, Null);
PNN ret;
if (u -> lc -> size < k) {
ret = split(u -> rc, k - 1 - u -> lc -> size);
u -> rc = ret.first;
ret.first = u;
} else {
ret = split(u -> lc, k);
u -> lc = ret.second;
ret.second = u;
}
u -> pushup();
return ret;
}
TreapNode* merge(TreapNode* u, TreapNode* v) {
if (u == Null) return v; if (v == Null) return u;
if (u -> aux < v -> aux) {
u -> rc = merge(u -> rc, v);
u -> pushup();
return u;
} else {
v -> lc = merge(u, v -> lc);
v -> pushup();
return v;
}
}
void insert(int v) {
// fprintf(stderr, "insert %d\n", v);
int k = getRank(root, v);
// fprintf(stderr, "ranked %d\n", k);
PNN t = split(root, k);
TreapNode* tmp = new TreapNode(v);
root = merge(merge(t.first, tmp), t.second);
}
void erase(int v) {
int k = getRank(root, v);
PNN t1 = split(root, k - 1), t2 = split(t1.second, 1);
root = merge(t1.first, t2.second);
}
int main() {
srand(2);
int n; cin >> n;
Null = new TreapNode(0); root = new TreapNode(0);
// cerr << Null -> id << endl;
Null -> size = 0;
while (n--) {
string op; cin >> op;
if (op == "add") {
int x; cin >> x;
insert(x);
} else if (op == "del") {
int x; cin >> x;
erase(x);
} else {
cout << root -> sum[3] << endl;
}
}
}
对于输入数据
6
add 4
add 5
add 1
add 2
add 3
sum
在种子为 2 时输出 3(Correct)
为 19260816 时输出 0(Wrong) (试了十几个只有这个会爆)
第二个样例也会出现这种情况,但容易复现的多。