Recently, I started learning about Treaps. I watched the Algorithms Live video on youtube and read the cp-algorithms blog on Treaps, however the way they implement the treap is different. I tried reading the code on cp-algorithms and i cannot understand how the split operation works.

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (key < t->key)
        split (t->l, key, l, t->l),  r = t;
    else
        split (t->r, key, t->r, r),  l = t;
}

I don't understand how the references to l and r works and how the values are assigned. Is there an easy way to understand how it works?

Thanks in advance. Here is a link to the full tutorial: https://cp-algorithms.com/data_structures/treap.html

I often come across problems that involve deleting both rows and columns in matrix in order to create some special matrix. One example I noticed today is the problem Coin Grid from the CSES problem set (link). I couldn't find an editorial for the task, and I never knew how to approach such problems, even thought I have seen couple of them. Can you give me some general hints and advices on how to approach such problems, when you need to find minimum moves and you can modify both rows and columns at the same time.

I couldn't find the older problems I have seen, but if you know some, please share them in the comments.

During the second day of this year's Balkan Olympiad in Informatics held in Greece there was a problem on implementing Alien's trick from IOI 2016 — Aliens but on trees. Link to the problem.. Shortly the problem askes us to choose $$$K$$$ edges from the tree of $$$N$$$ nodes, such that none of the chosen edges share a common node or report that this is not possible for the given tree. Both $$$N$$$ and $$$K$$$ are up to $$$10^6$$$.

I got a solution in $$$O(N \cdot K)$$$, however I couldn't optimize it further until I was told that it requires implementation of the Alien's trick. Since I haven't used this trick before, I'm not sure on how to use the cost function here. Do we still need two DP tables, and how to merge with the children, how do we keep track on how many edges we have picked in solution with the current cost, how are we sure whether exactly $$$K$$$ edges are taken or less.

I was trying to find a solution to precompute for each $$$i, inv_i = (k^i)^{-1} \mod{p}$$$. I know the standard method using binary exponention, that is $$$inv_i = (k^i)^{p - 2}$$$ however this precomputation works in $$$O(N \log P)$$$. Is there any faster method to do this.

I know that if we instead precompute $$$inv_i = i^{-1} \mod{p}$$$ we can use this code to do this in $$$O(N)$$$, however I'm not sure how to modify this to work for any $$$k^i$$$.

Here is the code we can use for computing $$$inv_i = i^{-1} \mod{p}$$$

Edit: I just noticed that we can rewrite $$$inv_i = inv_{i-1} * k^{-1} \mod{p}$$$. So we just compute $$$k^{\mod - 2}$$$ and then use this relation.

Hello everyone,

Recently I was trying to implement a working persistent segment tree, and I managed to solve couple problems with it.

However for one problem I needed to implement persistent segment tree with $$$100000$$$ values in the leafs, and two long long values in each node while the memory limit is only $$$64$$$ megabytes. Firstly I created version that works with pointers, however later I replaced the pointers with integers representing each node, but neither of those version is not working in the memory limit.

What is the best way to implement such tree, are there any tricks to reduce the memory usage?

I was trying to solve this problem from APIO 2016 (link here) and I found that it is very similar to the second problem on Topcoder SRM 728 Medium (link here)

Namely, in the topcoder we only want to count the valid sequences of length $$$N$$$, but for the APIO version we want to count all valid sequences of length from $$$1$$$ to $$$N$$$ instead of just the whole array.

I have read the tutorial for the Topcoder version and I understand how it works, however I cannot understand how to make this DP solution work for each subset of the array instead of working for the whole array.

Here is link for the tutorial for the Topcoder problem

Recently I read about LiChao Tree for convex hull trick, however I couldn't find any resource on internet showing on how to perform delete operations on LiChao trees. Is it even possible to do delete operations on such segment tree?

I tried solving this problem and I coded the first two subtasks easily. However, for the other two subtasks I tried reading the editorial. Even after reading I don't understand the solution. Here is link for the problem: https://ioinformatics.org/files/ioi2016problem2.pdf and the link of editorial https://ioinformatics.org/files/ioi2016solutions.pdf (3rd page)

I don't really get what the balance array does in the third subtask. I tried looking at every "special sections" as things that change the speed of the train from s[i] to t[i]. But I don't really get why the balance array has to be equal to all zeros and why the graph has to be connected and how in the forth subtask it is reduced to MST problem.

Thanks in advance for any help.

I'm not sure if we are allowed to discuss about other judges on codeforces, however solving problems from IOI is not available on codeforces.

I was trying to solve problem Holiday from IOI 2014. I know two judges that have this problem available — Oj.uz and Wcipeg. Namely my solution works on Wcipeg and gets accepted, while it fails on Oj.uz due to error message: Execution killed with signal 9 (could be triggered by violating memory limits). I don't know whether my solution is correct or not, also if it is correct why it doesn't work on Oj.uz

I have given my both codes below, since the way those two judges work is different, wcipeg gives us the variables on standard input, while on oj.uz we need to code function that will solve the problem.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100500;
ll value[maxn], d;
int arr[maxn];

class node {
public:
    ll sum;
    int cnt;
    node *leftchild, *rightchild;

    node(ll _sum, ll _cnt) {
        sum = _sum;
        cnt = _cnt;
    }
    node(node *a, node *b) {
        leftchild = a;
        rightchild = b;

        sum = a->sum + b->sum;
        cnt = a->cnt + b->cnt;
    }
};

node* build(int li=1, int ri=d) {
    if(li == ri) return new node(0LL, 0LL);
    else {
        int mid = (li + ri) / 2;
        return new node(build(li, mid), build(mid+1, ri));
    }
}

node* update(node *curr, ll uind, ll uval, int li=1, int ri=d) {
    if(li == ri) {
        return new node(curr->sum + uval, curr->cnt + 1);
    }
    else {
        int mid = (li + ri) / 2;
        if(uind <= mid) return new node(update(curr->leftchild, uind, uval, li, mid), curr->rightchild);
        else return new node(curr->leftchild, update(curr->rightchild, uind, uval, mid+1, ri));
    }
}

ll solve(node *p, node *pm, ll k, int li=1, int ri=d) {
    ll total = p->cnt - pm->cnt;
    if(k == 0) return 0LL;
    if(total < k) return (p->sum - pm->sum);

    if(li == ri) {
        return k * value[li];
    }
    else {
        int mid = (li + ri) / 2;

        ll total_right = p->rightchild->cnt - pm->rightchild->cnt;
        if(total_right >= k) return solve(p->rightchild, pm->rightchild, k, mid+1, ri);
        else return (p->rightchild->sum - pm->rightchild->sum) + solve(p->leftchild, pm->leftchild, k - total_right, li, mid);
    }
}

node *prefix[maxn];
set<int>st;
map<int,int>ind;
int n, start, c;
ll dp[maxn];

void solvedp(int l=1, int r=start, int optl=start, int optr=n) {
    if(l > r) return;
    int mid = (l + r) / 2;

    dp[mid] = -1;
    int optmid = -1;
    for(int i=optl;i<=optr;i++) {
        ll walk = i - mid + min(start - mid, i - start);
        ll curr = solve(prefix[i], prefix[mid-1], max(0LL, c - walk));
        if(curr > dp[mid]) {
            dp[mid] = curr;
            optmid = i;
        }
    }

    solvedp(l, mid-1, optl, optmid);
    solvedp(mid+1, r, optmid, optr);
}

int main() {
    cin>>n>>start>>c;
    start++;
    for(int i=0;i<n;i++) {
        cin>>arr[i];
        st.insert(arr[i]);
    }

    int br = 1;
    for(int i:st) {
        value[br] = i;
        ind[i] = br++;
    }
    d = br - 1;
    for(int i=n-1;i>=0;i--) {
        arr[i+1] = ind[arr[i]];
    }

    node *curr = build();
    prefix[0] = curr;
    for(int i=1;i<=n;i++) {
        curr = update(curr, arr[i], value[arr[i]]);
        prefix[i] = curr;
    }

    solvedp();
    ll result = 0LL;
    for(int i=1;i<=n;i++) {
        result = max(result, dp[i]);
    }
    cout<<result<<"\n";
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100500;
ll value[maxn], d;
int arr[maxn];
 
class node {
public:
    ll sum;
    int cnt;
    node *leftchild, *rightchild;
 
    node(ll _sum, ll _cnt) {
        sum = _sum;
        cnt = _cnt;
    }
    node(node *a, node *b) {
        leftchild = a;
        rightchild = b;
 
        sum = a->sum + b->sum;
        cnt = a->cnt + b->cnt;
    }
};
 
node* build(int li=1, int ri=d) {
    if(li == ri) return new node(0LL, 0LL);
    else {
        int mid = (li + ri) / 2;
        return new node(build(li, mid), build(mid+1, ri));
    }
}
 
node* update(node *curr, ll uind, ll uval, int li=1, int ri=d) {
    if(li == ri) {
        return new node(curr->sum + uval, curr->cnt + 1);
    }
    else {
        int mid = (li + ri) / 2;
        if(uind <= mid) return new node(update(curr->leftchild, uind, uval, li, mid), curr->rightchild);
        else return new node(curr->leftchild, update(curr->rightchild, uind, uval, mid+1, ri));
    }
}
 
ll solve(node *p, node *pm, ll k, int li=1, int ri=d) {
    ll total = p->cnt - pm->cnt;
    if(k == 0) return 0LL;
    if(total < k) return (p->sum - pm->sum);
 
    if(li == ri) {
        return k * value[li];
    }
    else {
        int mid = (li + ri) / 2;
 
        ll total_right = p->rightchild->cnt - pm->rightchild->cnt;
        if(total_right >= k) return solve(p->rightchild, pm->rightchild, k, mid+1, ri);
        else return (p->rightchild->sum - pm->rightchild->sum) + solve(p->leftchild, pm->leftchild, k - total_right, li, mid);
    }
}
 
node *prefix[maxn];
set<int>st;
map<int,int>ind;
int n, start, c;
ll dp[maxn];
 
void solvedp(int l=1, int r=start, int optl=start, int optr=n) {
    if(l > r) return;
    int mid = (l + r) / 2;
 
    dp[mid] = -1;
    int optmid = -1;
    for(int i=optl;i<=optr;i++) {
        ll walk = i - mid + min(start - mid, i - start);
        ll curr = solve(prefix[i], prefix[mid-1], max(0LL, c - walk));
        if(curr > dp[mid]) {
            dp[mid] = curr;
            optmid = i;
        }
    }
 
    solvedp(l, mid-1, optl, optmid);
    solvedp(mid+1, r, optmid, optr);
}
 
ll findMaxAttraction(int _n, int _start, int _c, int _attractions[]) {
    n = _n;
    start = _start;
    c = _c;
    start++;
    for(int i=0;i<n;i++) {
        arr[i] = _attractions[i];
        st.insert(arr[i]);
    }
 
    int br = 1;
    for(int i:st) {
        value[br] = i;
        ind[i] = br++;
    }
    d = br - 1;
    for(int i=n-1;i>=0;i--) {
        arr[i+1] = ind[arr[i]];
    }
 
    node *curr = build();
    prefix[0] = curr;
    for(int i=1;i<=n;i++) {
        curr = update(curr, arr[i], value[arr[i]]);
        prefix[i] = curr;
    }
 
    solvedp();
    ll result = 0LL;
    for(int i=1;i<=n;i++) {
        result = max(result, dp[i]);
    }
    return result;
}

If you had similar experiences, please share them, also I would like to know why my solutions fails on oj.uz.