about Min-Max Deletion

first, the result is the sum of the minimums of each pair

then, for each query, when I will change the $$$i_{th}$$$ element, I will erase the minimums from its pairs (its neighbours), then change the element, add the minimums again

here is my solution:

void solve()
{
  int n, q;
  cin >> n >> q;
  vec<int> a(n);
  for (auto &i : a)
    cin >> i;
  ll sum = 0;
  for (int i = 1; i < n; i++)
  {
    sum += min(a[i], a[i - 1]);
  }
  while (q--)
  {
    int i, x;
    cin >> i >> x;
    --i;

    if (i + 1 < n and a[i] < a[i + 1])
      sum -= a[i];
    else if(i + 1 < n)
      sum -= a[i + 1];
    if (i - 1 >= 0 and a[i] < a[i - 1])
      sum -= a[i];
    else if(i - 1 >= 0)
      sum -= a[i - 1];
    a[i] = x;
    if (i + 1 < n and a[i] < a[i + 1])
      sum += a[i];
    else if (i + 1 < n)
      sum += a[i + 1];
    if (i - 1 >= 0 and a[i] < a[i - 1])
      sum += a[i];
    else if (i - 1 >= 0)
      sum += a[i - 1];

    cout << sum << '\n';
  }
}

Min-Max Deletion had a pretty simple approach. since we had to maximize the minimum pairwise sum over all indices from 1 to n-1, we first pair up the larger numbers, followed by the smaller ones. after brute-forcing this once on paper, you'll notice that we could have just obtained the result by pairing up every pair of consecutive indices from 1 to n-1.After this, we'll process the queries from the input. For each query, we'll first subtract the contribution of the number at the particular index. Then we'll replace the old number at that index with the new one, and add back its new contribution. this contribution will come from its pair with index-1 and index+1, if they exist.

For Subsequence Sort : So basically there were a few observations that you could come up with: If a[i]>=a[i-1] you skip ahead, otherwise the best choice would be to make a[i]=a[i-1], let me clarify, if a[i]<a[i-1] this means that there exists some set bit with more significant value in a[i-1] than in a[i]. If you have reached till this bit in the operations , this means you have all the lesser bits covered as well, so you just need to find the maximum msb which is set in a[i] but not in a[i-1] across all elements.

For 5 4 9 11 12 , 5>4,the first disparity occurs at 2nd bit , so you need to set it and the rest of the bits below would be automatically managed as to get the value equal to 5.

Solution : ORSUBSORT

Thanks for sharing your ideas and solutions — they helped me successfully upsolve both problems.