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]]);↵
}↵
}↵
}↵
~~~~~↵
↵
Any ideas how to improve it?↵
↵
↵
↵
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]]);↵
}↵
}↵
}↵
~~~~~↵
↵
Any ideas how to improve it?↵
↵
↵
