Hi community,
I'm big fan of treaps, but this task makes me feel stupid. https://www.e-olymp.com/en/problems/2957
There is no English translate for some reason. Task: Given N single-element lists with integers 1..10^9, perform next queries: merge L R -> take two already exist lists and create a new one, equal concat(L,R) head L -> create two new lists: first contains first element of L, second — the rest of L. tail L -> create two new lists: first contains all L without last element, second — last element.
For every new list you need to output sum of it's elements.
I've did it with persistent treap — for every merge query: merge(root[L], root[R], root[++versions]), for head — split(root[L], root[nextV()], root[nextV()], 1) for tail — split(root[L], root[nextV()], root[nextV()], cnt[root[L]]-1);
But this fails as for every query it creates at least Log new nodes
typedef long long LL;
#define N 13000005
#define MOD 1000000007
int root[300005] , c;
struct Treap
{
int sum[N];
int nodecnt;
int L[N] , R[N] , cnt[N];
int key[N];
void clear() {
nodecnt = 0;
}
Treap () {clear();}
bool hey(int A , int B) {
return (LL)rand() * (cnt[A] + cnt[B]) < (LL)cnt[A] * RAND_MAX;
}
int newnode(int x) {
++ nodecnt , L[nodecnt] = R[nodecnt] = 0;
cnt[nodecnt] = 1 , key[nodecnt] = x, sum[nodecnt] = x;
return nodecnt;
}
int copynode(int A) {
if (!A) return 0;
++ nodecnt , L[nodecnt] = L[A] , R[nodecnt] = R[A];
cnt[nodecnt] = cnt[A] , key[nodecnt] = key[A], sum[nodecnt] = sum[A];
if (nodecnt == 5000000 — 100) {
printf("TREAP\n");
exit(0);
}
return nodecnt;
}
void pushup(int x) {
cnt[x] = 1;
sum[x] = key[x];
if (L[x]) {
cnt[x] += cnt[L[x]];
sum[x] = (sum[x] + sum[L[x]]) % MOD;
}
if (R[x]) {
cnt[x] += cnt[R[x]];
sum[x] = (sum[x] + sum[R[x]]) % MOD;
}
}
void merge(int& p , int x , int y) {
if (!x || !y) {
p = 0;
if (x) p = copynode(x);
if (y) p = copynode(y);
}
else if ( hey(x , y) ) {
p = copynode(x);
merge(R[p] , R[x] , y) , pushup(p);
}
else {
p = copynode(y);
merge(L[p] , x , L[y]) , pushup(p);
}
}
void split(int p , int& x , int& y , int size) {
if (!size) {
x = 0 , y = copynode(p);
return;
}
if (cnt[L[p]] >= size) {
y = copynode(p);
split(L[p] , x , L[y] , size) , pushup(y);
}
else {
x = copynode(p);
split(R[p] , R[x] , y , size — cnt[L[p]] — 1) , pushup(x);
}
}
void print(int p) {
if (L[p]) print(L[p]);
printf("%d ", key[p]);
if (R[p]) print(R[p]);
}
};
Treap T;
char s[10];
int main(void) {
int n;
scanf("%d", &n);
int version = 0;
REP(i, n) {
int x;
scanf("%d", &x);
root[++version] = T.newnode(x);
}
int q;
scanf("%d", &q);
REP(i, q) {
if (version >= 300005 — 50) {
printf("TREAP2\n");
exit(0);
}
scanf("%s", &s);
if (s[0] == 'm') {
int x,y;
scanf("%d%d", &x, &y);
T.merge(root[++version], root[x], root[y]);
printf("%d\n", T.sum[root[version]]);
}
if (s[0] == 'h') {
int x;
scanf("%d", &x);
int v1 = ++version;
int v2 = ++version;
T.split(root[x], root[v1], root[v2], 1);
printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
}
if (s[0] == 't') {
int x;
scanf("%d", &x);
int v1 = ++version;
int v2 = ++version;
T.split(root[x], root[v1], root[v2], T.cnt[root[x]] - 1);
printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
}
}
}
code — ~~~~~ typedef long long LL;
define N 13000005
define MOD 1000000007
int root[300005] , c; struct Treap { int sum[N]; int nodecnt; int L[N] , R[N] , cnt[N]; int key[N]; void clear() { nodecnt = 0; } Treap () {clear();} bool hey(int A , int B) { return (LL)rand() * (cnt[A] + cnt[B]) < (LL)cnt[A] * RAND_MAX; } int newnode(int x) { ++ nodecnt , L[nodecnt] = R[nodecnt] = 0; cnt[nodecnt] = 1 , key[nodecnt] = x, sum[nodecnt] = x; return nodecnt; } int copynode(int A) { if (!A) return 0; ++ nodecnt , L[nodecnt] = L[A] , R[nodecnt] = R[A]; cnt[nodecnt] = cnt[A] , key[nodecnt] = key[A], sum[nodecnt] = sum[A]; if (nodecnt == 5000000 — 100) { printf("TREAP\n"); exit(0); } return nodecnt; } void pushup(int x) { cnt[x] = 1; sum[x] = key[x]; if (L[x]) { cnt[x] += cnt[L[x]]; sum[x] = (sum[x] + sum[L[x]]) % MOD; } if (R[x]) { cnt[x] += cnt[R[x]]; sum[x] = (sum[x] + sum[R[x]]) % MOD; } } void merge(int& p , int x , int y) { if (!x || !y) { p = 0; if (x) p = copynode(x); if (y) p = copynode(y); } else if ( hey(x , y) ) { p = copynode(x); merge(R[p] , R[x] , y) , pushup(p); } else { p = copynode(y); merge(L[p] , x , L[y]) , pushup(p); } } void split(int p , int& x , int& y , int size) { if (!size) { x = 0 , y = copynode(p); return; } if (cnt[L[p]] >= size) { y = copynode(p); split(L[p] , x , L[y] , size) , pushup(y); } else { x = copynode(p); split(R[p] , R[x] , y , size — cnt[L[p]] — 1) , pushup(x); } } void print(int p) { if (L[p]) print(L[p]); printf("%d ", key[p]); if (R[p]) print(R[p]); } }; Treap T; char s[10];
int main(void) { int n; scanf("%d", &n); int version = 0; REP(i, n) { int x; scanf("%d", &x); root[++version] = T.newnode(x); }
int q; scanf("%d", &q); REP(i, q) { if (version >= 300005 — 50) { printf("TREAP2\n"); exit(0); } scanf("%s", &s); if (s[0] == 'm') { int x,y; scanf("%d%d", &x, &y); T.merge(root[++version], root[x], root[y]); printf("%d\n", T.sum[root[version]]); }
if (s[0] == 'h') {
int x;
scanf("%d", &x);
int v1 = ++version;
int v2 = ++version;
T.split(root[x], root[v1], root[v2], 1);
printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
}
if (s[0] == 't') {
int x;
scanf("%d", &x);
int v1 = ++version;
int v2 = ++version;
T.split(root[x], root[v1], root[v2], T.cnt[root[x]] - 1);
printf("%d\n%d\n", T.sum[root[v1]], T.sum[root[v2]]);
}} } ~~~~~
Any ideas how to improve it?
