We claim that the answer is always YES.

Let the direct path from vertex $$$u$$$ to vertex $$$v$$$ consist of $$$d$$$ edges. Since $$$u$$$ and $$$v$$$ are distinct, $$$d \ge 1$$$. Let the sequence of costs along these edges be $$$C = (c_1, c_2, \dots, c_d)$$$.

We claim that there always exists a contiguous subarray of $$$C$$$ whose sum is perfectly divisible by $$$d$$$.

Let $$$S$$$ denote the prefix sum array of $$$C$$$, where the $$$k$$$-th prefix sum is defined as:

Consider the values of these prefix sums modulo $$$d$$$. There are two cases:

• Case $$$1$$$: There exists an index $$$k$$$ such that $$$S_k \equiv 0 \pmod d$$$. In this case, the sum of the prefix subarray $$$(c_1, c_2, \dots, c_k)$$$ is directly divisible by $$$d$$$. The condition is satisfied.

• Case $$$2$$$: For all indices $$$k$$$, $$$S_k \not\equiv 0 \pmod d$$$. Because no prefix sum is congruent to $$$0$$$ modulo $$$d$$$, the remainder of each $$$S_k$$$ modulo $$$d$$$ must belong to the set $$${1, 2, \dots, d-1}$$$.

  We have computed exactly $$$d$$$ prefix sums $$$(S_1, S_2, \dots, S_d)$$$, but there are only $$$d-1$$$ possible remainder values available. By the Pigeonhole Principle, at least two prefix sums must evaluate to the exact same remainder modulo $$$d$$$.

  Therefore, there must exist two distinct indices $$$j$$$ and $$$k$$$ ($$$1 \le j \lt k \le d$$$) such that $$$S_j \equiv S_k \pmod d$$$. This congruence implies: $$$S_k - S_j \equiv 0 \pmod d$$$

  Expanding the definitions of the prefix sums yields: $$$S_k - S_j = \sum_{i=1}^{k} c_i - \sum_{i=1}^{j} c_i = \sum_{i=j+1}^{k} c_i$$$

  Thus, the contiguous subarray spanning from index $$$j+1$$$ to $$$k$$$ has a sum that is strictly divisible by $$$d$$$.

We can simply do a dfs to find the path from $$$u$$$ to $$$v$$$, and apply the above method on that path to find a valid answer.

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  int n, u, v;
  cin >> n >> u >> v;
  vector<vector<array<int, 2>>> tree(n + 1);
  map<array<int, 2>, int> ct;
  for (int i = 0; i < n - 1; i++)
  {
    int a, b, c;
    cin >> a >> b >> c;
    ct[{a, b}] = c;
    ct[{b, a}] = c;
    tree[a].push_back({b, c});
    tree[b].push_back({a, c});
  };

  vector<int> path;
  vector<int> curpath;
  auto dfs = [&](auto &dfs, int uu, int pp) -> void
  {
    curpath.push_back(uu);
    if (uu == v)
    {
      path = curpath;
      return;
    }
    for (auto &[vv, c] : tree[uu])
    {
      if (vv != pp)
      {
        dfs(dfs, vv, uu);
      }
    }
    curpath.pop_back();
  };

  dfs(dfs, u, -1);

  cout << "YES\n";

  int l = path.size();
  vector<int> cost(l - 1);
  map<int, vector<int>> temp;
  temp[0].push_back(-1);

  for (int i = 0; i < l - 1; i++)
  {
    cost[i] = ct[{path[i], path[i + 1]}] % (l - 1);
    if (i)
    {
      cost[i] += cost[i - 1];
      cost[i] %= (l - 1);
    }
    temp[cost[i]].push_back(i);
  }

  int LL = -1, RR = 0;
  for (auto &[v, vec] : temp)
  {
    if (vec.size() >= 2)
    {
      LL = vec[0], RR = vec[1];
      break;
    }
  }

  cout << l - 1 << '\n';
  for (int i = 0; i < l - 1; i++)
  {
    cout << path[i] << ' ' << path[i + 1] << ' ';
    cout << (LL < i && i <= RR) << '\n';
  }
}

int32_t main()
{
  int t;
  cin >> t;
  while (t--)
  {
    solve();
  }
  return 0;
}

Prefix Sum of an array of non negetive integers is non decreasing. Thus taking its prefix max does not change it.

As every $$$a_i$$$ can be written as

Store the prefix sums of the quotients in one array, and the prefix sums of the remainders in another array. Then reverse the second array before printing. So that both of them are unchanged after the first run.

We just need to choose the optimal value of $$$M$$$ so that prefix sums for both quotients and remainders do not exceed $$$10^9$$$

Here $$$n \le 2 \cdot 10^4$$$ and $$$a_i \le 10^9$$$, so choose

So that,

and

So both parts are small enough. As

In the second run with the prefix sum of quotient and remainder you easily find the original array

#include <bits/stdc++.h>
using namespace std;

int main()
{
  const int base = 31623;
  function<void(void)> first = [&](){
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for (auto &x : a) cin >> x;
    for (int i = 0; i < n; i++) b[i] = a[i] / base, c[i] = a[i] % base;
    for (int i = 1; i < n; i++) b[i] += b[i - 1], c[n - i - 1] += c[n - i];
    for (auto &x : b) cout << x << ' ';
    cout << '\n';
    for (auto &x : c) cout << x << ' ';
    cout << '\n';
    cout.flush();
  };
  function<void(void)> second = [&](){
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for (auto &x : b) cin >> x;
    for (auto &x : c) cin >> x;
    for (int i = n - 1; i > 0; i--) b[i] -= b[i - 1], c[n - i - 1] -= c[n - i];
    for (int i = 0; i < n; i++) a[i] = b[i] * base + c[i];
    for (auto &x : a) cout << x << ' ';
    cout << '\n';
    cout.flush();
  };
  string type;
  cin >> type;
  map<string, function<void(void)>> run = {{"first", first}, {"second", second}};
  int t;
  cin >> t;
  while (t--) run[type]();
  
  return 0;
}

Since all elements in $$$a$$$ are non-negative, the sum of a range decreases or remains the same as its length shrinks. To minimize the sum, we need the shortest possible intersection range. Adding more intervals to a chosen subset can only increase the overall left bound or decrease the overall right bound. This means taking more intervals will always shrink (or maintain) the intersection.

Thus, to get the smallest possible intersection, we should simply choose all $$$m$$$ intervals. Let $$$L = \max_{i=1}^m l_i$$$ and $$$R = \min_{i=1}^m r_i$$$. If $$$L \le R$$$, the answer is $$$\sum_{i=L}^{R} a_i$$$. If $$$L \gt R$$$, the intersection is empty, making the answer $$$0$$$.

Time Complexity: $$$O(n + m)$$$ Space Complexity: $$$O(1)$$$

#include <bits/stdc++.h>
using namespace std;

void solve()
{
  int n, m;
  cin >> n >> m;
  vector<int> v(n);
  for (auto &x : v) cin >> x;
  int l = -1, r = n;
  for (int i = 0; i < m; i++)
  {
    int x, y;
    cin >> x >> y;
    l = max(l, x);
    r = min(r, y);
  }
  cout << accumulate(v.begin() + min(l - 1, r), v.begin() + r, 0ll) << '\n';
}

int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    solve();
  }
  return 0;
}

Think of the count of integers you can create. It is around $$$2^{(n + 1)}$$$. Can you reduce our search space?

Think of integers containing only $$$1's$$$ in their decimal form and their remainders with $$$n$$$.

Pigeonhole principle

We have $$$n$$$ different integers containing only $$$1's$$$ in their representation $$$(1, 11, 111, ..., 1...11)$$$. If anyone of them gives a remainder of $$$0$$$, then that integer is our answer.

If none of them gives a remainder $$$0$$$, this means there are at most $$$(n - 1)$$$ possible remainders between $$$1$$$ and $$$(n-1)$$$.

Thus, we have n different integers giving at most $$$(n - 1)$$$ possible remainders. Hence by the Pigeonhole principle, there has to exist atleast 2 such integers with the same remainder. And subtracting the longer one (let's say it has $$$r$$$ $$$1's$$$) from the smaller one (let's say it has $$$l$$$ $$$1's$$$) gives us an integers of the form $$$1...110...00$$$ which has $$$(r - l)$$$ $$$1's$$$ followed by $$$l$$$ $$$0's$$$. And this is our answer.

The expected complexity of this logic is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    int n;
    cin >> n;
    vector<vector<int>> mp(n); // stores count of 1's against the remainder
    int num = 0;
    mp[0].push_back(0); // base case
    for (int i = 1; i <= n; i++)
    {
      num = num * 10 + 1;
      num %= n;
      mp[num].push_back(i);
    }
    for (int i = 0; i < n; i++)
    {
      if (mp[i].size() >= 2)
      {
        int s0 = mp[i][0];
        int s1 = mp[i][1] - s0;
        for (int i = 0; i < s1; i++) cout << '1';
        for (int i = 0; i < s0; i++) cout << '0';
        cout << '\n';
        break;  
      }
    }
  }
  return 0;
}

Symmetry and Pairing is the key.

The solution does not exist only for $$$n=2$$$ and $$$n=3$$$.

We can observe that the pairs $$$(1, 4)$$$ and $$$(2, 3)$$$ contribute equally to the prefix and suffix maximum sums. We can generalize this pattern for any group of four consecutive numbers: the pair $$$(4k + 1, 4k + 4)$$$ mathematically balances out with $$$(4k + 2, 4k + 3)$$$.

Based on this, we can construct the array by placing elements into an empty array of size $$$n$$$ using a two-pointer approach (filling left and right empty slots):

• $$$4k + 1$$$ takes the leftmost available slot.
• $$$4k + 2$$$ takes the rightmost available slot.
• $$$4k + 3$$$ takes the rightmost available slot.
• $$$4k + 4$$$ takes the leftmost available slot.

If we trace this out step-by-step, the array builds like this:

Continuing this pattern until all $$$n$$$ slots are filled, the array looks like:

Let $$$P$$$ be the sum of prefix maximums and $$$S$$$ be the sum of suffix maximums. If $$$n \pmod 4 = 0$$$ or $$$n \pmod 4 = 1$$$, this construction perfectly balances out, and $$$P = S$$$.

However, for $$$n \pmod 4 = 2$$$ and $$$n \pmod 4 = 3$$$, the construction leaves a slight imbalance where $$$S = P - 1$$$.

To fix this, we simply swap the numbers $$$2$$$ and $$$3$$$ at the very end of the array. Because the array natively ends in ... 3, 2, swapping them to ... 2, 3 increases the suffix maximum sum by exactly $$$1$$$ (since the suffix maximum of just the last element changes from $$$2$$$ to $$$3$$$). This brings $$$S$$$ up by $$$1$$$ without affecting $$$P$$$, perfectly satisfying $$$P = S$$$.

(Note: For $$$n = 2$$$ and $$$n = 3$$$, no valid permutation exists at all, so we simply output -1.)

#include <bits/stdc++.h>
using namespace std;

void solve()
{
  int n;
  cin >> n;
  if (n == 2 || n == 3)
  {
    cout << "-1\n";
    return;
  }
  if (n % 4 == 1)
  {
    for (int i = 1; i <= n - 1; i += 4)
    {
      cout << i << ' ' << i + 3 << ' ';
    }
    cout << n << ' ';
    for (int i = n - 1; i > 0; i -= 4)
    {
      cout << i - 1 << ' ' << i - 2 << ' ';
    }
    cout << '\n';
  }
  else if (n % 4 == 2)
  {
    for (int i = 1; i <= n - 2; i += 4)
    {
      cout << i << ' ' << i + 3 << ' ';
    }
    cout << n << ' ' << n - 1 << ' ';
    for (int i = n - 2; i > 4; i -= 4)
    {
      cout << i - 1 << ' ' << i - 2 << ' ';
    }
    cout << 2 << ' ' << 3 << ' ';
    cout << '\n';
  }
  else if (n % 4 == 3)
  {
    for (int i = 1; i < n - 3; i += 4)
    {
      cout << i << ' ' << i + 3 << ' ';
    }
    cout << n - 1 << ' ' << n << ' ' << n - 2 << ' ';
    for (int i = n - 3; i > 4; i -= 4)
    {
      cout << i - 1 << ' ' << i - 2 << ' ';
    }
    cout << 2 << ' ' << 3 << ' ';
    cout << '\n';
  }
  else
  {
    for (int i = 1; i < n - 4; i += 4)
    {
      cout << i << ' ' << i + 3 << ' ';
    }
    cout << n - 3 << ' ' << n << ' ' << n - 1 << ' ' << n - 2 << ' ';
    for (int i = n - 4; i > 0; i -= 4)
    {
      cout << i - 1 << ' ' << i - 2 << ' ';
    }  
    cout << '\n';
  }
}

int32_t main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--)
  {
    solve();
  }

  return 0;
}

Put $$$2$$$ and $$$n$$$ at the start and $$$n - 1$$$ in the end as shown: $$$[2, n, ..., n - 1]$$$.

Then sum of prefix maximums is $$$2 + (n) \times (n - 1) = n^2 - n + 2$$$,

and sum of suffix maximums is $$$n + n + (n - 1) \times (n - 2) = n^2 - n + 2$$$.

Hence, sum of prefix maximums $$$=$$$ sum of suffix maximums.

What is the answer when $$$m = n$$$?

For a subarray to have a maximum element of $$$k$$$ and a length of at least $$$k$$$, its length must be exactly $$$k$$$. This forces the elements $$$1, 2, \dots, k$$$ to always appear consecutively. Since this requirement holds for all $$$k \le m$$$, the numbers $$$1$$$ through $$$m$$$ must form a continuous subsegment.

To construct this subsegment, start by placing $$$1$$$. Every subsequent number from $$$2$$$ up to $$$m$$$ must be placed immediately adjacent to the already placed numbers. With $$$2$$$ choices (left or right) for each of the $$$m-1$$$ numbers, there are exactly $$$2^{m-1}$$$ ways to arrange them.

Treat this entire subsegment as one unit. We now have this $$$1$$$ unit plus the $$$n - m$$$ remaining numbers, giving $$$n - m + 1$$$ total items. These can be freely permuted in $$$(n - m + 1)!$$$ ways.

Multiplying these choices gives the final answer:

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int M = 1000000007;
int mul(int a, int b) { return ((a % M) * (b % M)) % M; }

void solve()
{
  int n, m;
  cin >> n >> m;
  int ans = 1;
  for (int i = 2; i <= m; i++)
  {
    ans = mul(ans, 2);
  }
  for (int i = 1; i <= (n - m + 1); i++)
  {
    ans = mul(ans, i);
  }
  cout << ans << '\n';
}

int32_t main()
{
  int t;
  cin >> t;
  while (t--) solve();  
  return 0;
}

Find all such cases where it is impossible to make the overall sum zero

Take $$$x = $$$ sum of all the elements.

Case 1: $$$(n = 1)$$$:

• If $$$a_1 = 1$$$, then it is impossible as $$$x \ge 2$$$.

• Otherwise, choose $$$x = a_1$$$. As $$$a_1 \bmod x = 0$$$, the sum becomes $$$0$$$.

Case 2: $$$(n \gt 1)$$$:

• Just choose $$$x = \sum_{i=1}^{n} a_i$$$

• Since $$$x \gt a_i$$$, we have $$$a_i \bmod x = a_i$$$ for all $$$i$$$.

Thus, applying the second operation to $$$a_1$$$ would make it $$$a_1 - x$$$, where $$$x$$$ is the sum of all the elements. This makes the overall sum of all the elements $$$0$$$.

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    if (n == 1 && v[0] == 1)
    {
      cout << "NO\n";
      continue;
    }
    long long sm = accumulate(v.begin(), v.end(), 0ll);
    cout << "YES\n";
    cout << "1 " << sm << '\n';
    cout << "1\n";
    cout << (n != 1) << '\n'; // if it's just 1 element, we make that element 0 using operation of type 0, else we do operation of type 1. 
  }
  return 0;
}

The key insight is that the intersection of any subset of intervals can always be formed by intersecting at most two intervals. If a subset yields an intersection range $$$[L, R]$$$, there must be one interval in the subset providing the left bound $$$L$$$ and another providing the right bound $$$R$$$. Therefore, we only need to minimize the sum over all single intervals and all valid intersections of pairs of intervals.

Let $$$Pref$$$ be the prefix sum array, where the sum of a range $$$[L, R]$$$ is $$$Pref[R] - Pref[L-1]$$$. Sort the intervals by their left endpoints $$$l_i$$$ and process them in order.

For the current interval $$$[l, r]$$$, pairing it with a previously processed interval $$$[l_1, r_1]$$$ yields an intersection of $$$[l, \min(r, r_1)]$$$ (since $$$l_1 \le l$$$). To minimize the intersection sum $$$P[\min(r, r_1)] - P[l-1]$$$, we need to minimize $$$P[\min(r, r_1)]$$$:

• If $$$r_1 \ge r$$$, the intersection is simply $$$[l, r]$$$, giving a sum of $$$P[r] - P[l-1]$$$.

• If $$$r_1 \lt r$$$, the intersection is $$$[l, r_1]$$$. We need the minimum $$$P[r_1]$$$ among all previously seen intervals where $$$l \le r_1 \lt r$$$.

We can solve this by maintaining a point-update, range-minimum segment tree over the coordinates $$$1 \dots n$$$. As we iterate through each interval $$$[l, r]$$$:

• Update the global minimum answer with the interval itself: $$$P[r] - P[l-1]$$$.

• Query the segment tree for the minimum value $$$P_{min}$$$ in the range $$$[l, r-1]$$$. If it exists, update the answer with $$$P_{min} - P[l-1]$$$.

• Insert this interval into the segment tree by updating position $$$r$$$ with $$$P[r]$$$.

Time Complexity: $$$O(m \log m + m \log n)$$$

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
// multi -> less_equal and s.erase(s.upper_bound(val)) to erase
#define int long long
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define fr(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define frr(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define vi vector<int>
#define vvi vector<vi>
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define vvpi vector<vpi>
const long long mod = 1e9 + 7;
#define pb push_back
#define endl "\n"
#define LL int
//  int p,q
// cout << mod_mul(p, modulo_inverse(q, mod)) << endl;
template <typename T>
struct segTree
{
    T unit;
    T (*f)(T obj1, T obj2);
    vector<T> s;
    int n;
    segTree(int n, T (*c)(T obj1, T obj2), T def) : s(2 * n, def), n(n), f(c), unit(def) {}
    void update(int pos, T val)
    {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e)
    { // query [b, e]
        e++;
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2)
        {
            if (b % 2)
                ra = f(ra, s[b++]);
            if (e % 2)
                rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};
int join(int a, int b)
{
    return min(a, b);
}
void solve()
{
    int n, m;
    cin >> n >> m;
    int a[n];
    segTree<int> tree(n + 1, join, 1e18);
    vi pref(n + 1, 0);
    int sum = 0;
    fr(i, 0, n)
    {
        cin >> a[i];
        sum += a[i];
        pref[i + 1] = sum;
    }
    int mx = 0, mn = 1e18;
    vpi wow;
    fr(i, 0, m)
    {
        int x, y;
        cin >> x >> y;
        wow.pb({x, y});
        mx = max(mx, x);
        mn = min(mn, y);
    }
    int ans = 1e18;
    sort(all(wow));
    fr(i, 0, wow.size())
    {
        tree.update(wow[i].second, pref[wow[i].second]);
        int val = pref[wow[i].first - 1];
        int q = tree.query(wow[i].first, wow[i].second);
        ans = min(ans, q - val);
    }
    if (mx > mn)
    {
        ans = min(ans, 0ll);
    }
    cout << ans << endl;
}

signed main()
{
    fast;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

The total score of the array is the sum of the MEX across all subsequences. A well-known identity for any non-negative integer $$$Y$$$ is that its value is the sum of its conditions: $$$Y = \sum_{x=1}^{\infty} [Y \ge x]$$$.

Applying this, a specific $$$MEX$$$ value contributes $$$x$$$ times to the sum for all $$$1 \le x \le MEX$$$. We can rewrite the total score as:

By swapping the summations, we can instead count how many subsequences satisfy the condition for each $$$x$$$:

When is $$$MEX(S) \ge x$$$?

For a subsequence $$$S$$$ to have a MEX of at least $$$x$$$, it must contain at least one occurrence of every integer from $$$0$$$ to $$$x-1$$$.

Let $$$c_i$$$ be the frequency of the integer $$$i$$$ in the array. To form a valid subsequence:

1. For each integer $$$i$$$ from $$$0$$$ to $$$x-1$$$, we must pick at least one of its occurrences. There are $$$(2^{c_i} - 1)$$$ ways to do this per integer.

2. For the remaining elements in the array (elements $$$\ge x$$$), we can freely include or exclude them. There are $$$n - \sum_{i=0}^{x-1} c_i$$$ remaining elements, giving $$$2^{n - \sum_{i=0}^{x-1} c_i}$$$ choices.

Multiplying these gives the number of valid subsequences for a specific $$$x$$$:

We can significantly simplify this formula by rewriting $$$(2^{c_i} - 1)$$$ as $$$2^{c_i}(1 - 2^{-c_i})$$$:

Factoring out the $$$2^{c_i}$$$ terms from the product causes their exponents to sum up perfectly with the exponent of the remaining elements:

This leaves us with a clean, simplified formula for the number of subsequences where $$$MEX(S) \ge x$$$:

Segment Tree Application:

Let's define $$$g(i) = 1 - 2^{-c_i} \pmod{998244353}$$$.

The total score over all $$$x$$$ simplifies to:

When a query updates an element, we only need to decrease the frequency of the old value and increase the frequency of the new value. This means only two point updates — $$$g(\text{old})$$$ and $$$g(\text{new})$$$ — occur per query.

A Segment Tree is perfect for maintaining this prefix sum of products. Each node covering a range $$$[L, R]$$$ maintains two cleanly aligned variables:

• Product: $$$\text{prod}_{[L, R]} = \prod_{i=L}^{R} g(i)$$$
• Sum: $$$\text{sum}_{[L, R]} = \sum_{x=L}^{R} \prod_{i=L}^{x} g(i)$$$

Node Merging:

When merging a left child and a right child to form a parent node, the transitions are:

The answer for each query is simply $$$2^n \times \text{tree.query}(0, n)\text{.sum}$$$. This works optimally in $$$O(\log n)$$$ time per query.

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
// multi -> less_equal and s.erase(s.upper_bound(val)) to erase
#define int long long
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define fr(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define frr(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define vi vector<int>
#define vvi vector<vi>
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define vvpi vector<vpi>
const long long mod = 998244353;
#define pb push_back
#define endl "\n"
#define LL int
//  int p,q
// cout << mod_mul(p, modulo_inverse(q, mod)) << endl;
LL mod_mul(LL a, LL b)
{
    a = a % mod;
    b = b % mod;
    return (((a * b) % mod) + mod) % mod;
}

LL mod_add(LL a, LL b)
{
    a = a % mod;
    b = b % mod;
    return (((a + b) % mod) + mod) % mod;
}
template <typename T>
struct segTree
{
    T unit;
    T (*f)(T obj1, T obj2);
    vector<T> s;
    int n;
    segTree(int n, T (*c)(T obj1, T obj2), T def) : s(2 * n, def), n(n), f(c), unit(def) {}
    void update(int pos, T val)
    {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e)
    { // query [b, e]
        e++;
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2)
        {
            if (b % 2)
                ra = f(ra, s[b++]);
            if (e % 2)
                rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};
pi join(pi a, pi b)
{
    if (a.first == -1e9 && a.second == -1e9)
    {
        return b;
    }
    if (b.first == -1e9 && b.second == -1e9)
    {
        return a;
    }
    return {mod_mul(a.first, b.first), mod_add(a.second, mod_mul(a.first, b.second))};
}
long long BinExpMod(long long a, long long b, long long m)
{
    a %= m;
    long long res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int extended_euclidean(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = extended_euclidean(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
int modulo_inverse(int a, int m)
{
    int x, y;
    int g = extended_euclidean(a, m, x, y);
    if (g != 1)
    {
        return -1;
    }
    else
    {
        x = (x % m + m) % m;
        return x;
    }
}
void solve()
{
    int n, q;
    cin >> n >> q;
    int a[n];
    vi freq(n + 1, 0);
    fr(i, 0, n)
    {
        cin >> a[i];
        freq[a[i]]++;
    }
    segTree<pi> tree(n + 1, join, {-1e9, -1e9});
    fr(i, 0, n + 1)
    {
        int val = mod_add(1, -modulo_inverse(BinExpMod(2, freq[i], mod), mod));
        tree.update(i, {val, val});
    }
    fr(i, 0, q)
    {
        int x, y;
        cin >> x >> y;
        int val = a[x - 1];
        a[x - 1] = y;
        freq[val]--;
        freq[y]++;
        int v = mod_add(1, -modulo_inverse(BinExpMod(2, freq[val], mod), mod));
        tree.update(val, {v, v});
        v = mod_add(1, -modulo_inverse(BinExpMod(2, freq[y], mod), mod));
        tree.update(y, {v, v});
        cout << mod_mul(BinExpMod(2, n, mod), tree.query(0, n).second) << " ";
    }
    cout << endl;
}

signed main()
{
    fast;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Since the upper limit for the hidden integers is very small ($$$16$$$), the total number of possible hidden triplets $$$(a, b, c)$$$ is $$$16 \times 15 \times 14 = 3360$$$.

Because this search space is so small, we don't need to find a mathematical closed-form strategy. Instead, we can use a Minimax Greedy Heuristic to guarantee we find the answer within the 11-query limit.

Every time we ask a query ? x y z, the jury returns an answer $$$k \in {0, 1, 2, 3}$$$. This effectively splits our remaining pool of valid candidates into 4 buckets, based on what answer they would produce.

To minimize our total queries, we want to pick a query that guarantees the search space shrinks as much as possible, even in the absolute worst-case scenario.

The Algorithm:

Step 1: Initialize a list of all 3360 valid, pairwise distinct triplets.

Step 2: While we have more than 1 candidate left, evaluate all 3360 possible queries against our remaining candidate list.

Step 3: For a specific query, simulate asking it against every remaining candidate. Count how many candidates result in an answer of 0, 1, 2, or 3.

Step 4: Find the maximum size among these 4 buckets. This is the worst-case scenario for this specific query.

Step 5: Out of all 3360 possible queries, choose the one that minimizes this worst-case maximum.

Step 6: Ask that chosen query to the interactor, get the actual answer $$$k$$$, and filter our candidate list, keeping only the triplets that would have produced exactly $$$k$$$.

Step 7: Repeat until exactly 1 candidate remains.

Why does this fit in 11 queries?

If the splits were perfectly even, we would divide the search space by 4 each time (which would take around 6 queries). However, the splits are never perfectly even, especially after the first few queries. The greedy minimax heuristic ensures that even with these uneven bucket sizes, the absolute worst-case depth of our decision tree is strictly bounded to 11 queries, perfectly matching the problem's limit.

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
// multi -> less_equal and s.erase(s.upper_bound(val)) to erase
#define int long long
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define fr(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define frr(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define vi vector<int>
#define vvi vector<vi>
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define vvpi vector<vpi>
const long long mod = 1e9 + 7;
#define pb push_back
#define LL int
//  int p,q
// cout << mod_mul(p, modulo_inverse(q, mod)) << endl;

int query(int a, int b, int c)
{
    cout << "? " << a << " " << b << " " << c << endl;
    int x;
    cin >> x;
    return x;
}

void solve()
{
    vvi ok;
    vvi okk;
    fr(i, 1, 17)
    {
        fr(j, 1, 17)
        {
            fr(k, 1, 17)
            {
                if (i != j && j != k && k != i)
                {
                    ok.pb({i, j, k});
                    okk.pb({i, j, k});
                }
            }
        }
    }
    
    while (ok.size() > 1)
    {
        vi stor;
        int mn = 1e18;
        fr(i, 0, okk.size())
        {
            vi ans(4, 0);
            fr(j, 0, ok.size())
            {
                int sum = 0;
                if (ok[j][0] < okk[i][0])
                {
                    sum++;
                }
                if (ok[j][1] < okk[i][1])
                {
                    sum++;
                }
                if (ok[j][2] < okk[i][2])
                {
                    sum++;
                }
                ans[sum]++;
            }
            if (max({ans[0], ans[1], ans[2], ans[3]}) < mn)
            {
                mn = min(max({ans[0], ans[1], ans[2], ans[3]}), mn);
                stor = okk[i];
            }
        }
        
        int wow = query(stor[0], stor[1], stor[2]);
        vvi lmao;
        fr(j, 0, ok.size())
        {
            int sum = 0;
            if (ok[j][0] < stor[0])
            {
                sum++;
            }
            if (ok[j][1] < stor[1])
            {
                sum++;
            }
            if (ok[j][2] < stor[2])
            {
                sum++;
            }
            if (sum == wow)
            {
                lmao.pb(ok[j]);
            }
        }
        ok = lmao;
    }
    
    cout << "! " << ok[0][0] << " " << ok[0][1] << " " << ok[0][2] << endl;
}

signed main()
{
    fast;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Sort the intervals by their left endpoints $$$l_i$$$ and process them in order. Let $$$P$$$ be the prefix sum array, and $$$dp[i]$$$ be the minimum sum of a valid union of intervals ending exactly at index $$$i$$$.

For the current interval $$$[l, r]$$$, we can either take it alone (sum is $$$P[r] - P[l-1]$$$) or extend a previously processed union ending at $$$r_1$$$. Because we process in sorted order, $$$l_1 \le l$$$. We have three cases to consider for $$$r_1$$$:

• If $$$r_1 \lt l$$$: The new sum is $$$dp[r_1] + P[r] - P[l-1]$$$. To optimize this, we need the minimum $$$dp[r_1]$$$ among all previously seen intervals in the range $$$[1, l-1]$$$.

• If $$$l \le r_1 \lt r$$$: The intervals overlap, and the new union ends at $$$r$$$. The sum is $$$dp[r_1] + P[r] - P[r_1]$$$, which can be rewritten as $$$P[r] + (dp[r_1] - P[r_1])$$$. We need the minimum $$$(dp[r_1] - P[r_1])$$$ in the range $$$[l, r-1]$$$.

• If $$$r_1 \ge r$$$: The interval $$$[l, r]$$$ is completely covered by the previous union. Including it doesn't change the bounds or the answer, so we simply ignore this case.

We can solve this by maintaining two point-update, range-minimum segment trees over the coordinates $$$1 \dots n$$$:

• The first tree stores the minimum $$$dp[i]$$$.

• The second tree stores the minimum $$$(dp[i] - P[i])$$$.

As we iterate through each interval $$$[l, r]$$$:

• Calculate the minimum possible sum $$$V$$$ for ending a union at $$$r$$$ by taking the minimum of:

  • $$$P[r] - P[l-1]$$$ (taking the interval alone)
  • $$$\min(dp[r_1]) + P[r] - P[l-1]$$$ (querying the first segment tree on $$$[1, l-1]$$$)
  • $$$P[r] + \min(dp[r_1] - P[r_1])$$$ (querying the second segment tree on $$$[l, r-1]$$$)

• Update the global minimum answer with $$$V$$$.

• Insert this state by updating position $$$r$$$ in the first segment tree with $$$V$$$, and in the second segment tree with $$$V - P[r]$$$.

Time Complexity: $$$O(m \log m + m \log n)$$$

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
// multi -> less_equal and s.erase(s.upper_bound(val)) to erase
#define int long long
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define fr(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define frr(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define vi vector<int>
#define vvi vector<vi>
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define vvpi vector<vpi>
const long long mod = 1e9 + 7;
#define pb push_back
#define endl "\n"
#define LL int
//  int p,q
// cout << mod_mul(p, modulo_inverse(q, mod)) << endl;
template <typename T>
struct segTree
{
    T unit;
    T (*f)(T obj1, T obj2);
    vector<T> s;
    int n;
    segTree(int n, T (*c)(T obj1, T obj2), T def) : s(2 * n, def), n(n), f(c), unit(def) {}
    void update(int pos, T val)
    {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e)
    { // query [b, e]
        e++;
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2)
        {
            if (b % 2)
                ra = f(ra, s[b++]);
            if (e % 2)
                rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};
int join(int a, int b)
{
    return min(a, b);
}
void solve()
{
    int n, m;
    cin >> n >> m;
    int a[n + 1];
    vi pref(n + 1, 0);
    int sum = 0;
    fr(i, 0, n)
    {
        cin >> a[i + 1];
        sum += a[i + 1];
        pref[i + 1] = sum;
    }
    vpi wow;
    fr(i, 0, m)
    {
        int x, y;
        cin >> x >> y;
        wow.pb({x, y});
    }
    segTree<int> dp(n + 1, join, 1e18), dp2(n + 1, join, 1e18);
    sort(all(wow));
    int mn = 1e18;
    fr(i, 0, m)
    {
        int val = min(pref[wow[i].second] - pref[wow[i].first - 1], pref[wow[i].second] - pref[wow[i].first - 1] + dp.query(0, wow[i].first - 1));
        val = min(val, pref[wow[i].second] + dp2.query(wow[i].first, wow[i].second));
        dp.update(wow[i].second, val);
        dp2.update(wow[i].second, val - pref[wow[i].second]);
        mn = min(mn, val);
    }
    cout << mn << endl;
}

signed main()
{
    fast;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}