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.