The height of a node, as will be used throughout this blog, refers to the maximum distance in a rooted tree from a node to any of the leaves within its subtree. As a corollary, hereby it is considered that a leaf has a height of 1.

At the beginning of year $$$y$$$, the height of peak $$$i$$$ can be any integer $$$H \in [h_i + y \cdot l_i, h_i + y \cdot r_i]$$$.

Therefore, the problem boils down to finding the maximum number of overlapping segments, where segment $$$i$$$ is $$$[h_i + y \cdot l_i, h_i + y \cdot r_i]$$$. This can be done in many ways, either via greedy, or by using difference arrays.

Time complexity: $$$O(N log N)$$$

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll NMAX = 2e5+9;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll n, y, v, l, r, peaks=0, maxpeaks=0, cnt=0;
    map<ll,ll> dif_array;

    cin>>n>>y;

    for(ll i=0;i<n;i++){
        cin>>v>>l>>r;
        dif_array[v+l*y]++;
        dif_array[v+r*y+1]--;
    }
    for(auto it = dif_array.begin(); it!=prev(dif_array.end());it++){
        peaks+=it->second;
        if(peaks>maxpeaks){
            maxpeaks=peaks;
            cnt = 0;
        }
        if(peaks == maxpeaks)
            cnt+=next(it)->first-it->first;
    }
    cout<<maxpeaks<<" "<<cnt;
    return 0;
}

In this tutorial, we will work in base 5, so every definition of "digit" will refer to the afferent 5-base digit.

Let us first define what is the meaning of the "obligation" of a prefix for a number.

Consider that by some means, we have constructed a prefix of a number $$$a_{1}a_{2}a_{3}...a_{i}$$$ is obligated by some number $$$b_{1}b_{2}b_{3}...b_{n-1}b_{n}$$$, (with $$$n>i$$$, of course) if and only if for each $$$1 \le j \le i$$$, we have $$$a_{j}=b_{j}$$$. Then, from here, we might ask what can happen with $$$a_{i+1}$$$, so we could eventually complete the number.

Let $$$count[i][Lx][Ux][Ly][Uy]$$$ be the number of (pairs for X, respectively Y) suffixes of lenght i with

• $$$Lx=1$$$ if there is still an obligation (given from the precedent digits) for the X-number towards $$$x1$$$, $$$Lx=0$$$ if not

• $$$Ux=1$$$ if there is still an obligation for the X-number towards $$$x2$$$, $$$Ux=0$$$ if not 

• $$$Ly=1$$$ if there is still an obligation for the Y-number towards $$$y1$$$, $$$Ly=0$$$ if not

• $$$Uy=1$$$ if there is still an obligation for the Y-number towards $$$y2$$$, $$$Uy=0$$$ if not 

Now, to establish this value, let us fix the digits on position $$$i$$$ of the X value (let it be x), respectively for the Y value (let it be y). Then, of course, while setting these values we must verify that (x mod $$$3$$$) = (y mod $$$3$$$). Now, if we have $$$(Lx=1)$$$, x must also be greater or equal than the corresponding digit of x1. If it is strictly greater, we will go in a state in which the corresponding Lx will be 0, otherwise it will remain equal to 1. But if the Lx was already 0, by the definition of obligation, x could be any value (with respect to x1, things might change considering x2), and the next Lx would remain 0. Let this value (the "updated" Lx) be called nLx.

After establishing the $$$nLy,nUx,nUy$$$ in a similar manner ($$$nUx$$$ becomes 0 if $$$Ux$$$ was 1 if and only if x is smaller than the corresponding digit in x2, same for $$$nUy$$$), we have

We can initiate this table with $$$count[0][0/1][0/1][0/1][0/1] = 1$$$, because any solution that eventually goes into this state should be considered as valid

After doing this for each possible state (with i varying from 1 to $$$nDig=log_{5}(max(x2,y2))$$$, which you can consider as 28), the answer lies within $$$count[nDig][1][1][1][1]$$$ (because we start forcefully with obligation with respect to the bounds)

So the complexity (in time) for each testcase would be $$$O(MaxLog_{5} * 2^{4} * 5^{2})$$$

#include <iostream>
#define int unsigned long long 
using namespace std;
// in this implementation I merged Lx and Ux in xobl and Ly and Uy in yobl

#define in cin
#define out cout

int dp[28][2*2][2*2];
static inline int bit(int x, int accum) {
  return (x/accum)%5ULL;
}

static void testcase() {
  int x1,y2,x2,y1,newobl[2];
  in >> x1 >> y1 >> x2 >> y2; 
  for(int i=0; i<4ULL; i++)
    for(int j=0; j<4ULL; j++)
      dp[0][i][j]=1ULL;
  for(int i=1,cy1,cy2,cx2,cx1; i<=27ULL; i++) {
    cy1=y1%5;
    cy2=y2%5;
    cx1=x1%5;
    cx2=x2%5;
    for(int xobl=0ULL; xobl<4ULL; xobl++) {
      for(int yobl=0ULL; yobl<4ULL; yobl++) {
        for(int r1=0ULL; r1<5ULL; r1++) {
          for(int r2=0ULL; r2<5ULL; r2++) {
            if( r1%3ULL==r2%3ULL &&
                 (xobl&1ULL || r1<=cx2) && (xobl&2ULL || r1>=cx1) && 
                 (yobl&1ULL || r2<=cy2) && (yobl&2ULL || r2>=cy1) ) {
              newobl[0ULL]=xobl;
              newobl[1ULL]=yobl;
              if(r1<cx2)
                newobl[0ULL]|=1ULL;
              if(r1>cx1)
                newobl[0ULL]|=2ULL;
                
              if(r2<cy2)
                newobl[1ULL]|=1ULL;
              if(r2>cy1)
                newobl[1ULL]|=2ULL;
              dp[i][xobl][yobl]+=dp[i-1ULL][newobl[0ULL]][newobl[1ULL]];
            }
          }
        }
      }
    }
    y1/=5;
    y2/=5;
    x1/=5;
    x2/=5;
  }
  out << dp[27ULL][0ULL][0ULL] << '\n';
  for(int k=0ULL; k<=27ULL; k++) 
    for(int i=0ULL; i<4ULL; i++)
      for(int j=0ULL; j<4ULL; j++)
        dp[k][i][j]=0ULL;
}
signed main() {
  int q;
  in >> q;
  for(int i=0; i<q; i++)
    testcase();
}

Notice how, regardless of the given pairs , $$$A_i = i^2$$$ will always be in range $$$[0,10^9]$$$ , the values will be distinct and the $$$k$$$ given restrictions will always be satisfied. Thus just print the squares of the first $$$N$$$ numbers.

Time Complexity: $$$O(N)$$$

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, k;
	cin >> n >> k;
	while (k--) {
		int useless1, useless2;
		cin >> useless1 >> useless2;
	}
	for (long long i = 1; i <= n; ++i) {
		cout << i * i << ' ';
	}
}

Let there be $$$cnt_0(x)$$$ numbers greater than $$$x$$$ to the left of $$$x$$$ and $$$cnt_1(x)$$$ numbers less than $$$x$$$ to the right of x. Note that $$$cnt_0(x) + cnt_1(x)$$$ is the number of inversions that contain $$$x$$$.

Let $$$prev$$$ be the previous value of $$$x$$$ and $$$inv$$$ the number of inversions before the update.

After an update, the number of inversions becomes $$$inv - cnt_0(prev)- cnt_1(prev) + cnt_0(x) + cnt_1(x)$$$.

Solution 1 (Sqrt Decomposition + Fenwick)

We will cut $$$a$$$ into chunks of $$$\sqrt{N log N}$$$ elements. Each chunk will contain a fenwick tree with the frequencies of the elements from that chunk. Finding the number of elements smaller than $$$x$$$ is done via a prefix sum query in the fenwick trees.

To calculate $$$cnt_0$$$ we will need to iterate through every chunk to the left of $$$x$$$. $$$cnt_1$$$ will be dealt with similarly.

Time complexity: $$$O(Q \sqrt{Nlog N})$$$.

To optimize this even further, we'll need to change the chunk size to the smallest one that fits within the ML (around $$$\sqrt{N}$$$) and create a pseudo-fenwick tree with the chunks themselves, making each query solvable in $$$O(\sqrt{N}+log^2N)$$$.

Solution 2 (Fenwick + Data Structures)

This solution requires setting up a fenwick tree where every node contains an ordered set (bitwise trie, treap, AVL tree, etc) of the elements within it.

Queries and updates will be processed like in a normal fenwick tree, with prefix and suffix sums.

Total time complexity: $$$O((N + Q) \cdot log^2 N)$$$.

#include<bits/stdc++.h>
#define NMAX 200005
//#pragma GCC optimize("O3")
using namespace std;
unordered_map<int,int> id;
set<int> s;
int v[NMAX],n;
pair<int,int> queries[NMAX];
int chunk_size;
int chunks[77][NMAX];
void insert(const int& pos, int val, const int& cnt){
    while(val<NMAX)
        chunks[pos/chunk_size][val]+=cnt,val+=val&-val;
}
int cnt(int pos, const int& val){ /// #less equal before
    if(pos<0) return 0;
    int ans=0;
    while((pos+1)%chunk_size)
        ans+=v[pos--]<=val;
    pos=(pos+1)/chunk_size-1;
    while(pos>=0){
        int v2=val;
        while(v2) ans+=chunks[pos][v2],v2-=v2&-v2;
        pos--;
    }
    return ans;
}
int cnt2(int pos, const int& val){ /// #less equal after
    if(pos<0 || pos>=n) return 0;
    int ans=0;
    while(pos<n && pos%chunk_size)
        ans+=v[pos++]<=val;
    if(pos==n) return ans;
    pos/=chunk_size;
    while(pos*chunk_size<n){
        int v2=val;
        while(v2) ans+=chunks[pos][v2],v2-=v2&-v2;
        pos++;
    }
    return ans;
}
int main()
{
    int q;
    long long inversions=0;
    scanf("%d%d",&n,&q);
    chunk_size=sqrt(n*log2(NMAX));
    for(int i=0;i<n;i++){
        scanf("%d",&v[i]), s.insert(v[i]);
    }
    for(int i=0;i<q;i++){
        scanf("%d%d",&queries[i].first,&queries[i].second), s.insert(queries[i].second);
    }
    for(const auto& it : s) id[it]=id.size()+1;
    for(int i=0;i<n;i++){
        v[i]=id[v[i]];
        inversions+=(long long)(cnt(i-1,NMAX-1)-cnt(i-1,v[i]));
        insert(i,v[i],1);
    }
    for(int i=0;i<q;i++){
        int p=queries[i].first-1,x=id[queries[i].second];
        insert(p,v[p],-1);
        inversions-=(long long)(p-cnt(p-1,v[p])+cnt2(p+1,v[p]-1));
        v[p]=x;
        insert(p,v[p],1);
        inversions+=(long long)(p-cnt(p-1,v[p])+cnt2(p+1,v[p]-1));
        printf("%lld\n",inversions);
    }
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
const int NMAX=1e5+2;
template<size_t bit_count=31>
struct bitwise_trie{
    struct node{
        int subtreeSize=0;
        node* children[2]={NULL,NULL};
    };
    node* root=new node;
    void insert(int num, int cnt=1){
        node* curr=root;
        for(int i=bit_count;i>=0;i--){
            if(curr->children[num>>i&1]==NULL)
                curr->children[num>>i&1] = new node;
            curr=curr->children[num>>i&1];
            curr->subtreeSize+=cnt;
        }
    }
    int order_of_key(int num){
        node* curr=root;
        int cnt_less=0;
        for(int i=bit_count;i>=0;i--){
            if((num>>i&1) && curr->children[0]!=NULL)
                cnt_less+=curr->children[0]->subtreeSize;
            if(curr->children[num>>i&1]==NULL)
                return cnt_less;
            curr=curr->children[num>>i&1];
        }
        return cnt_less;
    }
};
bitwise_trie<17> BIT[NMAX];
void insert(int pos, int num, int cnt=1){
    while(pos<NMAX){
        BIT[pos].insert(num,cnt);
        pos+=pos&-pos;
    }
}
int order_of_key(int pos, int num){
    int cnt=0;
    while(pos){
        cnt+=BIT[pos].order_of_key(num);
        pos-=pos&-pos;
    }
    return cnt;
}
int v[NMAX];
set<int> s;
map<int,int> compressed_value;
pair<int,int> queries[NMAX];
int main()
{
    int n,q;
    long long inversions=0;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        s.insert(v[i]);
    }
    for(int i=0;i<q;i++){
        scanf("%d%d",&queries[i].first,&queries[i].second);
        s.insert(queries[i].second);
    }
    for(auto it : s) compressed_value[it]=compressed_value.size();
    for(int i=1;i<=n;i++){
        v[i]=compressed_value[v[i]];
        insert(i,v[i]);
        inversions+=i-1-order_of_key(i-1,v[i]+1);
    }
    for(int i=0;i<q;i++){
        int p=queries[i].first,x=compressed_value[queries[i].second];
        inversions-=p-1-order_of_key(p-1,v[p]+1);
        inversions+=p-1-order_of_key(p-1,x+1);
        inversions-=order_of_key(n,v[p])-order_of_key(p,v[p]);
        inversions+=order_of_key(n,x)-order_of_key(p,x);
        insert(p,v[p],-1);
        insert(p,x,1);
        v[p]=x;
        printf("%lld\n",inversions);
    }
    return 0;
}

Solution 1 (DP):

Let dp[i][col] be the minimum number of changes required to transform the prefix of length i into a Rubik String ending in col.

Calculating dp[i][col] is pretty straightforward, dp[i][col]=min(dp[i-1][col2]) + (col ≠ s[i])}, across all colours col2 which are compatible with col.

Time complexity: $$$O(N*6^2)$$$

Solution 2 (Greedy):

Lemma: There always exists a colour that is adjacent on the Rubik's Cube to any other two colours.

The optimal answer is obtained by traversing the string from the second colour onward. If the current colour is incompatible with the previous colour, increase the answer by $$$1$$$. Replace the current colour with any colour that is compatible with both the previous colour and the next colour.

Alternatively, instead of replacing the current colour with a compatible colour, one may indeed choose to not process the next colour, simulating its becoming compatible with the current colour.

Time Complexity: $$$O(N)$$$.

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const ll NMAX=1e5+5,MOD=1e9+7;
ll dp[NMAX][6];
void tc(){
    ll n;
    string s;
    cin>>n>>s;
    ll id[128];
    id['W']=0;
    id['R']=1;
    id['B']=2;
    id['G']=3;
    id['O']=4;
    id['Y']=5;
    dp[0][0]=dp[0][1]=dp[0][2]=dp[0][3]=dp[0][4]=dp[0][5]=1;
    dp[0][id[s[0]]]=0;
    for(ll i=1;i<n;i++){
        for(ll new_colour=0;new_colour<6;new_colour++){
            dp[i][new_colour]=INT_MAX;
            for(ll prev_colour=0;prev_colour<6;prev_colour++){
 
                if(prev_colour==new_colour || prev_colour+new_colour==5)
                    continue;
                dp[i][new_colour]=min(dp[i][new_colour],dp[i-1][prev_colour]+(new_colour!=id[s[i]]));
            }
        }
    }
    cout<<min({dp[n-1][0],dp[n-1][1],dp[n-1][2],dp[n-1][3],dp[n-1][4],dp[n-1][5]})<<'\n';
}
int main()
{
    ll t; cin>>t; while(t--)
        tc();
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

void tc(){
    ll n,ans=0;
    string s;
    cin>>n>>s;
    char opposite[128];
    opposite['W']='Y';
    opposite['Y']='W';
    opposite['B']='G';
    opposite['G']='B';
    opposite['R']='O';
    opposite['O']='R';
    for(ll i=1;i<n;i++){
        if(s[i]==opposite[s[i-1]] || s[i]==s[i-1])
            ans++,i++;
    }
    cout<<ans<<'\n';
}
int main()
{
    ll t; cin>>t; while(t--)
        tc();
    return 0;
}

Solution in $$$O(k \cdot n^2 \cdot log(n))$$$

For this solution , we will use dynamic programming. Let $$$dp(i,j)$$$ store the minimum cost to split the first i values into k subarrays. Transitions are simple : Try all possible subarrays that contain value $$$i$$$. Let's say we are currently trying subarray k....i. Thus , transitions are

Answear will be found in $$$dp(n,k)$$$ and for initial state , $$$dp(0,0) = 0$$$.

Solution in $$$O(k \cdot n \cdot log^2(n))$$$

We will need to optimize the above dp solution. Notice how the optimal K for every i is monotonus , so we can apply divide and conquer optimization. This way we will get a solution that passes all testcases. More information about this trick can be found here.

#include <bits/stdc++.h>
using namespace std;
class bit {
private:
    vector<long long> b;
public:
    long long query(long long p) {
        long long t = 0;
        for (long long i = p; i; i -= (i & -i)) {
            t += b[i];
        }
        return t;
    }
    long long query(long long st, long long dr) {
        return query(dr) - query(st - 1);
    }
    void update(long long p, long long val) {
        long long lg = b.size() - 1;
        for (long long i = p; i <= lg; i += (i & -i)) {
            b[i] += val;
        }
    }
    void resize(long long lg) {
        b.resize(lg);
    }
};
vector<long long> curr_dp;
vector<long long> prev_dp;
vector<long long> a;
bit aib;
long long n, k;
long long inv;
long long l, r;
void add(bool c) {
    if (c) {
        l--;
        inv += aib.query(a[l] - 1);
        aib.update(a[l], 1);
    }
    else {
        r++;
        inv += aib.query(a[r] + 1, n);
        aib.update(a[r], 1);
    }
}
void rem(bool c) {
    if (c) {
        inv -= aib.query(a[l] - 1);
        aib.update(a[l], -1);
        l++;
    }
    else {
        inv -= aib.query(a[r] + 1, n);
        aib.update(a[r], -1);
        r--;
    }
}
void move(int st, int dr) {
    while (r < dr) {
        add(false);
    }
    while (l > st) {
        add(true);
    }
    while (l < st) {
        rem(true);
    }
    while (r > dr) {
        rem(false);
    }
}
void solve(long long st, long long dr, long long left, long long right) {
    if (st > dr) {
        return;
    }
    long long mid = (st + dr) / 2;
    long long best = n*n;
    long long split = 0;
    for (long long i = min(right, mid); i >= max(1ll, left); --i) {
        move(i , mid); 
        if (prev_dp[i - 1] + inv < best) {
            best = prev_dp[i - 1] + inv;
            split = i;
        }
    }
    curr_dp[mid] = best;
    solve(st, mid - 1, left, split);
    solve(mid + 1, dr, split, right);
}
int main() { 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    a = vector<long long>(n + 1);
    vector<long long> norm(n + 1);
    for (long long i = 1; i <= n; ++i) {
        cin >> a[i];
        norm[i] = a[i];
    }
    sort(norm.begin() + 1, norm.end());
    map<long long, long long> who;
    long long p = 1;
    for (long long i = 1; i <= n; ++i) {
        if (who.find(norm[i]) == who.end()) {
            who[norm[i]] = p++;
        }
    }
    for (long long i = 1; i <= n; ++i) {
        a[i] = who[a[i]];
    }
    prev_dp.resize(n + 1);
    curr_dp.resize(n + 1);
    aib.resize(n + 1);
    l = 1, r = 0;
    for (long long i = 1; i <= n; ++i) {
        add(false);
    }
    for (long long i = 1; i <= n; ++i) {
        move(1, i);
        prev_dp[i] = inv;
    }
    prev_dp[0] = n*n;
    for (long long i = 2; i <= k; ++i) {
        solve(i, n, 1, n);
        prev_dp = curr_dp;
        curr_dp = vector<long long>(n + 1, n*n);
    }
    cout << prev_dp[n];
}

Since all permutations of the plains array will have the same xorsum, the lexicographically minimal array will always be sorted.

The first $$$n-3$$$ elements should be set as $$$1,2, \ldots, n-3$$$ to ensure that the plains array is lexicographically minimal.

Since the elements of the plains array must be distinct, $$$v_n \neq v_{n-1} \Leftrightarrow v_n \wedge v_{n-1} \gt 0 \Rightarrow v_1 \wedge v_2 \wedge \ldots \wedge v_{n-2} \gt 0$$$. Therefore, we must find a value for $$$v_{n-2}$$$ such that $$$v_1 \wedge v_2 \wedge \ldots \wedge v_{n-2} \gt 0$$$. It turns out that $$$v_{n-2}$$$ can be either $$$n-2$$$ or $$$n-1$$$.

To find the last two elements, one must find the smallest $$$v_{n-1} \gt v_{n-2}$$$ for which $$$v_{n} \gt v_{n-1}$$$. Since $$$v_1 \wedge v_2 \wedge \ldots \wedge v_{n} = 0$$$, $$$v_{n}=v_1 \wedge v_2 \wedge \ldots \wedge v_{n-1}$$$.

It can be proven that $$$v_{n-1}$$$ will never exceed $$$nextPowerOf2(n-2)$$$. When $$$v_{n-1}=nextPowerOf2(n-2)$$$, $$$v_n=v_1 \wedge v_2 \wedge \ldots \wedge v_{n-1}$$$ will be equal to $$$v_1 \wedge v_2 \wedge \ldots \wedge v_{n-2} + v_{n-1} \gt v_{n-1}$$$.

It can additionally be proven that $$$v_n \lt 2 \cdot v_{n-1} \le 4 \cdot n \le 8 \cdot 10^5 \lt 10^6$$$.

Time complexity per testcase: $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll MOD = 1e9+7;

void solve(){
    ll n, currXOR = 0;
    cin>>n;
    for(ll i = 1; i < n - 2; i++){
        cout << i << " ";
        currXOR ^= i;
    }
    ll nextelem;
    if(currXOR ^ (n - 2))
        nextelem = n - 2;
    else
        nextelem = n - 1;

    currXOR ^= nextelem;
    cout << nextelem << " ";
    ll secondToLast = nextelem+1;

    while( (currXOR ^ secondToLast) <= nextelem)
        secondToLast++;

    cout << secondToLast << " " << (secondToLast^currXOR) << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll k;
    cin>>k;
    while(k--)
        solve();
    return 0;
}

We will use the definition of "the depth of a node" as the distance from the root to that node.

Let us begin with a very bad solution for the problem (if it didn't have any updates):

Let $$$preord[i]$$$ be the i-th node from the preorder of the tree, $$$pin[i]$$$ be the position of node i in the preorder and $$$pout[i]$$$ the position of the last element added int the preorder while recurring on the subtree of $$$i$$$. Then, every node $$$preord[j]$$$ with $$$pin[i] \le j \le pout[i]$$$ is a node in the subtree. Then, to determine the height of the node, we take the maximum value of the depth of each node in this segment and from this value we subtract the depth of the node on which we query.

Adapting this structure to tolerate updates is simple, as much as we can update for each node it's height, then modify the corresponding value in the preorder array. The only issue with this solution would be in the case when the values in the corresponding segment of the preorder array of a node do not reflect the actual values in the subtree. This "error" can be manifested in two ways:

1. Some nodes from the corresponding segment of the preorder array of that node still appear in the subtree, but some others do not. In that case, those that do not would have a relative (to the root) depth smaller than whatever we might have in the actual subtree, so the maximum value is still "actual"

2. Every node that once corresponded to the subtree of a node does not belong anymore to that node. In that case, the node is bound to be forever a leaf and every query on it would be equal to 0.

Time complexity: $$$O(QlogN) + O(N)$$$ (for construction)

Memory complexity: $$$O(N)$$$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll NMAX=3e5+5;
ll st[NMAX*4],lnode[NMAX],rnode[NMAX],p[NMAX],d[NMAX],currid=1,n;
bool fell[NMAX];
vector<ll> edg[NMAX];
void Set(ll l, ll r, ll node,ll pos, ll newval){
    if(l>pos || r<pos) return;
    if(l==pos && r==pos) st[node]=newval;
    else{
        ll m=(l+r)/2;
        Set(l,m,node*2+1,pos,newval);
        Set(m+1,r,node*2+2,pos,newval);
        st[node]=max(st[node*2+1],st[node*2+2]);
    }
}
ll rmq(ll l, ll r, ll node, ll pos1, ll pos2){
    if(l>pos2 || r<pos1) return 0;
    if(l>=pos1 && r<=pos2) return st[node];
    ll m=(l+r)/2;
    return max(rmq(l,m,node*2+1,pos1,pos2),rmq(m+1,r,node*2+2,pos1,pos2));
}
void dfs(ll node, ll depth){
    d[node]=depth;
    for(auto it : edg[node]){
        if(it==p[node]) continue;
        dfs(it,depth+1);
        lnode[node]=(lnode[node]==0 || lnode[it]<lnode[node]?lnode[it]:lnode[node]);
    }
    if(lnode[node]==0) lnode[node]=currid;
    rnode[node]=currid++;
    Set(1,n,0,rnode[node],depth);
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll q;
    cin>>n>>q;
    for(ll i=2;i<=n;i++){
        ll u; cin>>u;
        p[i]=u;
        edg[u].push_back(i),edg[i].push_back(u);
    }
    dfs(1,0);
    while(q--){
        ll t,u;
        cin>>t>>u;
        if(t==1){
            if(d[u]>=2) Set(1,n,0,rnode[u],--d[u]);
            fell[u]=1;
        }
        else{
            cout<<(fell[u]?0:rmq(1,n,0,lnode[u],rnode[u])-d[u])<<'\n';
        }
    }
    return 0;
}

I am bad at problemsetting, and this issue was reflected in the scores that were gained in contest at this contest were mostly just optimal brute-force solutions, somehow more optimal than what I already had. By the time when this blog would be posted, I should have a testcase that would fail the solutions that had 100 in the contest. I would've done this mid contest, but the good guys, Gheal and tibinyte2006, wouldn't let me commit such a Popeala. Again, sorry for this inconvenience.

It is very uncomfortable for us to keep track of Gigi's players. More specifically, it's awkward to note the fact that each second we must update all the blocked positions due to their movement. So, we make the following claim: A pass is unsuccesful if the segment $$$[ (x_1,y), (x_2, y + (x_2-x_1)) ]$$$ intersects any player of Gigi's.

the initial arrangement

the arrangement, as defined by the ammendement we made earlier

the arrangement at T=2, as defined by the statement

We can prove this by induction. First, when we refer to (a,b)=1 at some time, it means that this point will be blocked at that time.

Base case: $$$(a+1,b), T=1 <=> (a+1,b+1), T=0$$$ (i.e. they are equivalent points at different times)

This derives from the statement, since if $$$(a+1,b+1), T=0$$$, then $$$(a+1-1,b+1), T=1$$$

Inductive step:

applying the base case on $$$(a+x+1,b+x), T=0$$$ we get

then again, by default, we have

So

And

so

QED

Now, let's assume we have to solve the following problem:

Given some vertical segments, determine for each query consisting of a horisontal segment if this intersects any of the earlier given segments.

This is a classical exaample of a problem that can be solved using the technique of line-sweeping. The solution we know, at least, is the following: sort both the vertical segments and the horizontal ones by their greatest X-coordinate. Then: A vertical segment is an update on all the Y-coordinates it covers. A horizontal segment is a point-query that asks if the latest vertical segment that covers this Y-coordinate happened after the left-X-limit of the segment.

This can be solved using a Segment Tree with lazy propagation.

I do admit that this is a... bad, to say the least, solution for this problem, and there are easier solutions. But I saw this problem and that was the first thing that struck me

The problem is that momentarily we have queries on lines parallel to ( (0,0), (1,1) ), and segments for updates parallel to Oy. With more consideration, we can say that we are currently working in the space defined by

So, we have to transform it to

This can be done by multiplying with the inverse of the first matrix (by the definition of matrixes) and then multiplying it with the latter (which is the identity matrix, so it won't have any effect). The inverse we are talking about is of course:

The effect on this matrix on every vector (which, in our case, would be the endpoints of the segments) in the plane is basically just subtracting the x-coordinate value from the y-coordinate value. So we use this to recalculate the input to the "normal" version. Then we can use the sweep-line algorithm we described earlier to solve the problem.

Time complexity: $$$O((N+M)*(log(N+M)+log(COORDMAX)))$$$

Space complexity: $$$O(N+M+COORDMAX)$$$

I do agree that I might have over-complicated the solution, but all of this was just for rigorous mathematical demonstration purposes. I also note that if we were to give the problem using something of the sorts "passes move with speed X, and players go down with speeds Y", the problem could've easily made it as the easy problem from some Romanian IOI TST (the solution would be to change the first column of the initial transformation to (X,Y)). We decided not to do this, because we didn't want to implement Segment trees over doubles, and neither would the contestant in this case. Also, as "artificial" the problem might seem, the idea for the original problem is as you see it in the statement (except the initial problem didn't have the bounds that the passes were horizontal and the blockers were vertical).

Firstly , let $$$sb(n,k)$$$ be the number of ways of writing n as sum of k values greater or equal to 0. This is well known as "Stars and bars".

How can we encode a way of choosing money ? The conditions of a move are as follows :

• From each bag , substract its amount of money by some value which is $$$\ge 0$$$.
• There must exist at least one bag such that we substracted a value $$$> 0$$$ from it.

Thus , we can encode a way of choosing money as follows :

$$$A_{1,1}$$$ $$$A_{1,2}$$$ $$$\cdots$$$ $$$A_{1,k}$$$

$$$A_{1,1}$$$ $$$A_{1,2}$$$ $$$\cdots$$$ $$$A_{1,k}$$$

$$$\vdots$$$ $$$\, \, \, \, \, \, \, \, \, \, \, \, \, \, \,$$$ $$$\ddots$$$

$$$A_{N,1}$$$ $$$A_{N,2}$$$ $$$\cdots$$$ $$$A_{N,k}$$$

$$$\Sigma^{K}_{j=1} A_{i,j} = A_i$$$ for every $$$i$$$ in range $$$[1,N]$$$

There exists an element in every colum of the matrix such that it is $$$> 0$$$.

Where $$$A_{i,j}$$$ is the amount of money we took from bag i , during the j-th move.

Subtask 1 : $$$K = 2$$$

This subtask needs an $$$O(K)$$$ solution. Let's fix the number of 0 values on the first row of the matrix. Let this value be $$$T$$$. Thus , the second row of the matrix must contain at least $$$T$$$ non-zero value. There are $$${K}\choose{T}$$$ ways of arranging the zero values in the first row. This must be multiplied by sb($$$A_1$$$ , $$$K-T$$$) and sb($$$A_2-T$$$,$$$K$$$).We conclude the final formula as being :

Subtask 2 : $$$N,K \le 2000$$$

In this subtask $$$O((N+K) \cdot K)$$$ is required. Let $$$dp_i$$$ be the number of possible configurations which last $$$i$$$ moves. Initially , $$$dp_0 = 1$$$, if all values are equal to 0, otherwise $$$dp_0=0$$$ if there is a value greater than 0. Let's use the principle of inclusion exclusion. First count all configurations , in which there could be a column full of 0s. Their number is equal to

Now we need to subtract from that number , the number of matrices that contain columns full of 0s. Let's use the previous states. It turns out that the number of matrices that contain columns full of 0s is equal to

This is true because we will subtract the number of matrices with 1 column full of 0s, then the ones with 2 columns full of 0s ... So , our transitions are :

Time complexity $$$O((N+K) \cdot K)$$$

Let some sequence $$$b=[$$$ $$$a[i_1],a[i_2], \ldots a[i_k]$$$ $$$]$$$. If $$$b$$$ is constant, then $$$a[i_1]+1=a[i_2]+2= \ldots = a[i_k]+k$$$. Therefore, $$$b=[$$$ $$$a[i_1],a[i_1]-1, \ldots, a[i_1]-(k-1)$$$ $$$]$$$.

Let dp[i] be the maximum length of a constant subarray ending in $$$a[i]$$$. We'll also need maxdp[x]=max( dp[i] for which $$$a[i]=x$$$).

Let $$$i$$$ be the current position. a[i] can be appended to any subarray ending in a[i]+1. Therefore, *dp[i]=dpmax[a[i]+1]+1(. dpmax[a[i]] will also be updated accordingly: dpmax[a[i]]=max(dpmax[a[i]],dp[i]).

The maximum length of any constant subarray is equal to $$$k=max_{i=1}^n(dp[i])$$$.

Reconstructing a maximal constant subarray will also require prev[i] — the last appearance of a[i]+1 to the left of $$$i$$$. From some position $$$p$$$ where dp[p] is maximal, $$$p$$$ will be replaced repeatedly by prev[p] $$$k-1$$$ times. This traversal will visit, in reverse, all the elements of a constant subarray ending in $$$a[p]$$$.

Is it really necessary to set some segment $$$[l,r]$$$ as the solution, where $$$l != 1$$$ ?

Let's say X is the last element of the solution. How can we find how many elements it overwrites?

let's say the optimal solution is $$$[l,r]$$$ (where $$$[l,r]$$$ denotes the subarray between indexes $$$l$$$ and $$$r$$$). Then, We can prove that l=1 the following way: let's consider $$$[l-1,r]$$$ (which should exist assuming $$$l!=1$$$), then $$$sum[l-1,r] = sum[l,r] + min(v[i] | l-1 \le i \le r)$$$ The second term of the sum is always greater than 1, so $$$sum[l-1,r]>sum[l,r]$$$ (where sum[x,y] denotes the sum of the elements in between indexes x and y after the segment is gorbasorted)

Then, we propose the following soltuion: Let gorba[i]= the sum of elements in $$$[1,i]$$$ after gorbasorted. Then, if X is the greatest position such that $$$X \le i$$$, and $$$v[X] \le v[i]$$$, then gorba[i]=gorba[X]+(X-i)*v[i] (v[i] overwrites all elements between X+1 and i-1). Then how do we find X for each i? This is an easy question that can be solved using a stack. more on that here

Subtask 1 : $$$N,K \le 1000$$$

Since $$$N,K \le 1000$$$ , we can start to develop an $$$O(N \cdot K)$$$ algorithm. Let DP[i][j] store the maximum money i can have if i helped $$$j$$$ homeless men from the first i places. We have 2 cases :

• The value at $$$A_i$$$ is positive ( including 0 ).

• The value at $$$A_i$$$ is negative.

First case is easy , because it is always optimal to withdraw money ( easy proof by contradiction ). So in this case we can just say that

Second case is pretty easy as well. Just like in the well known 0-1 knapsack algorithm , we have 2 choices : either help the i-th homeless man , or ignore him. Transitions are :

• DP[i][j] = max(DP[i][j],DP[i-1][j-1] — $$$|A_i|$$$) if $$$DP[i-1][j-1] - |A_i| \ge 0$$$
• DP[[i][j] = max(DP[i][j] , DP[i-1][j])

So , with $$$O(1)$$$ transitions and $$$O(N \cdot K)$$$ states , the time complexity will be $$$O(N \cdot K)$$$.

Subtask 2 : $$$N,K \le 10^5$$$

For this subtask , we need a better time complexity. First notice that an optimal solution that contains a maximum amount of homeless men , will also contain the optimal solution of any less homeless men as a subsolution. Let's find the best solution in which we help the most homeless men. Let's assume we are currently at the ith place and we know an optimal solution for the first i-1 places. We have two cases :

• The value at $$$A_i$$$ is positive ( including 0 )
• The value at $$$A_i$$$ is negative.

If $$$A_i$$$ is positive , we will just take the money.

If $$$A_i$$$ is negative and we have enough money , we will help the i-th homeless man ( we want maximum number of homeless men ). Else we will look at the optimal solution for the first i-1 places. If in that solution we have a homeless man begging for more money, we will add the homeless man at position i and remove the other homeless man from the optimal solution. Else , there is no reason for us to help that homeless man.

This can easily be simulated using a priority_queue , with at most n removals and n insertions , we have an $$$O(NlogN)$$$ time complexity.