There are at most $$$8$$$ positions of the knight that can attack a single cell. Therefore, we can find all $$$8$$$ positions that attack the king and the $$$8$$$ positions that attack the queen and count the number of positions that appear in both of these lists.

#include <bits/stdc++.h>
using namespace std;
 
int dx[4] = {-1, 1, -1, 1}, dy[4] = {-1, -1, 1, 1};
 
int main(){
    int t; cin >> t;
    for(int i = 0; i < t; i++){
        int a, b; cin >> a >> b;
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        set<pair<int, int>> st1, st2;
        for(int j = 0; j < 4; j++){
            st1.insert({x1+dx[j]*a, y1+dy[j]*b});
            st2.insert({x2+dx[j]*a, y2+dy[j]*b});
            st1.insert({x1+dx[j]*b, y1+dy[j]*a});
            st2.insert({x2+dx[j]*b, y2+dy[j]*a});
        }
        int ans = 0;
        for(auto x : st1)
            if(st2.find(x) != st2.end())
                ans++;
        cout << ans << '\n';
    }
} 

Let's sort array $$$a$$$. The answer for the largest element is $$$n-1$$$ because the score, which is $$$a_n$$$, cannot be smaller than any of the other elements. Now, consider the second largest element. The answer is at least $$$n-2$$$ because every element that is not greater than $$$a_{n-1}$$$ can be taken. Then, we check if the score is at least $$$a_n$$$. This inspires the following solution: first, we find the prefix sum $$$p$$$ of array $$$a$$$. We calculate the answer in decreasing order of $$$a_i$$$. To calculate the answer for an $$$a_i$$$, we find the largest $$$j$$$ such that $$$p_i\geq a_j$$$ and set the answer for $$$i$$$ equal to the answer of $$$j$$$.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll ceil0(ll a, ll b) {
    return a / b + ((a ^ b) > 0 && a % b);
}

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

int main(){
    setIO();
    int T;
    cin >> T;
    for(int tt = 1; tt <= T; tt++){
        int n;
        cin >> n;
        pii arr[n + 1];
        for(int i = 1; i <= n; i++) cin >> arr[i].ff, arr[i].ss = i;
        sort(arr + 1, arr + n + 1);
        int nxt[n + 1];
        ll sum[n + 1];
        int ans[n + 1];
        nxt[0] = sum[0] = 0;
        for(int i = 1; i <= n; i++){
            if(nxt[i &mdash; 1] >= i){
                nxt[i] = nxt[i &mdash; 1];
                sum[i] = sum[i &mdash; 1];
            } else {
                sum[i] = sum[i &mdash; 1] + arr[i].ff;
                nxt[i] = i;
                while(nxt[i] + 1 <= n && sum[i] >= arr[nxt[i] + 1].ff){
                    nxt[i]++;
                    sum[i] += arr[nxt[i]].ff;
                }
            }
            ans[arr[i].ss] = nxt[i];
        }
        for(int i = 1; i <= n; i++) cout << ans[i] &mdash; 1 << " ";
        cout << endl;
    }
}

If $$$k\geq 3$$$, the answer is equal to $$$0$$$ since after performing an operation on the same pair $$$(i, j)$$$ twice, performing an operation on the two new values (which are the same) results in $$$0$$$.

Therefore, let's consider the case for $$$1\leq k\leq 2$$$.

For $$$k=1$$$, it is sufficient to sort the array and output the minimum between $$$a_i$$$ and $$$a_{i+1} - a_i$$$.

For $$$k=2$$$, let's brute force the first operation. If the newly created value is $$$v$$$, then it is sufficient to find the smallest $$$a_i$$$ satisfying $$$a_i\geq v$$$ and greatest $$$a_i$$$ satisfying $$$a_i\leq v$$$ and relax the answer on $$$|a_i - v|$$$. Also, remember to consider the cases of performing no operation or one operation. This runs in $$$O(N^2\log N)$$$. There also exists a solution in $$$O(N^2)$$$ using a two pointers approach.

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

#define int long long
 
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        if (k >= 3) {
            cout << 0 << endl;
            continue;
        }
        sort(begin(a), end(a));
        int d = a[0];
        for (int i = 0; i < n - 1; i++) d = min(d, a[i + 1] - a[i]);
        if (k == 1) {
            cout << d << endl;
            continue;
        }
        for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) {
            int v = a[i] - a[j];
            int p = lower_bound(begin(a), end(a), v) - begin(a);
            if (p < n) d = min(d, a[p] - v);
            if (p > 0) d = min(d, v - a[p - 1]);
        }
        cout << d << endl;
    }
}

Can we reduce the number of intervals we want to apply an operation on?

What is the necessary condition to perform an operation on an interval

If $$$b_i < a_i$$$ for any $$$i$$$, then it is clearly impossible.

In order for $$$a_i$$$ to become $$$b_i$$$, $$$i$$$ must be contained by an interval that also contains a $$$j$$$ where $$$a_j = b_i$$$. Note that if there is a triple $$$i \le j < k$$$ where $$$a_j = a_k = b_i$$$, then it is never optimal to apply the operation on interval $$$[i, k]$$$, since applying the operation on interval $$$[i, j]$$$ will be sufficient. Thus, for $$$i$$$ we only need to consider the closest $$$a_j = b_i$$$ to the right or left of $$$i$$$.

Lets find the necessary conditions for us to apply an operation on the interval $$$[i, j]$$$. First of all, $$$a_k \le b_i$$$ for $$$i \le k \le j$$$. Second, $$$b_k \ge b_i$$$ for all $$$i \le k \le j$$$. Turns out, these conditions are also sufficient, since we can apply these operations in increasing order of $$$b_i$$$ without them interfering with each other. If we check for every $$$i$$$ there exists an interval $$$[i, j]$$$ or $$$[j, i]$$$ that satisfies the necessary conditions, then there will exist a sequence of operations to transform $$$a$$$ into $$$b$$$. Checking for the conditions can be done with brute force for D1 or using monotonic stacks or segment trees for D2.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll ceil0(ll a, ll b) {
    return a / b + ((a ^ b) > 0 && a % b);
}

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

int main(){
    setIO();
    int T;
    cin >> T;
    for(int tt = 1; tt <= T; tt++){
        int n;
        cin >> n;
        int a[n + 1], b[n + 1];
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> b[i];
        bool val[n + 1];
        memset(val, false, sizeof(val));
        for(int t = 0; t < 2; t++){
            int prvb[n + 1]; //prev smaller
            int nxta[n + 1]; //next greater
            stack<pii> s;
            s.push({INF, n + 1});
            for(int i = n; i >= 1; i--){
                while(s.top().ff <= a[i]) s.pop();
                nxta[i] = s.top().ss;
                s.push({a[i], i});
            }
            while(!s.empty()) s.pop();
            s.push({0, 0});
            for(int i = 1; i <= n; i++){
                while(s.top().ff >= b[i]) s.pop();
                prvb[i] = s.top().ss;
                s.push({b[i], i});
            }
            int m[n + 1];
            memset(m, 0, sizeof(m));
            for(int i = 1; i <= n; i++){
                m[a[i]] = i;
                if(a[i] <= b[i] && m[b[i]]) val[i] |= prvb[i] < m[b[i]] && nxta[m[b[i]]] > i;
            }
            reverse(a + 1, a + n + 1);
            reverse(b + 1, b + n + 1);
            reverse(val + 1, val + n + 1);
        }
        bool ans = true;
        for(int i = 1; i <= n; i++) ans &= val[i];
        cout << (ans ? "YES" : "NO") << endl;
    }
}

The solution doesn't involve virtual tree

What is an easy way to represent the tree?

Consider the Euler tour of the tree where $$$in[u]$$$ is the entry time of each node and $$$out[u]$$$ is the exit time. The interval $$$[in[u], out[u]]$$$ corresponds to the subtree of $$$u$$$.

Removing a node is equivalent to blocking some intervals on the Euler tour. There are two cases when $$$a$$$ is blocked with respect to query node $$$x$$$. If $$$a$$$ is an ancestor of $$$x$$$, then the set of reachable nodes is reduced to the interval $$$[in[nxt_a], out[nxt_a]]$$$, where $$$nxt_a$$$ is the first node on the path from $$$a$$$ to $$$x$$$. This is equivalent to blocking the intervals $$$[0, in[nxt_a])$$$ and $$$(out[nxt_a], n - 1]$$$. If $$$a$$$ is not an ancestor, then the interval $$$[in[a], out[a]]$$$ is blocked.

Lets build a lazy segment tree on the Euler tour of the tree. Each leaf node will correspond to the depth of a node on the tree. We can re-root the tree from $$$a$$$ to $$$b$$$ by subtracting one from all nodes the range $$$[in[b], out[b]]$$$ and adding one to all other nodes. Thus, we can traverse the tree while re-rooting and process our queries offline. When the query node $$$x$$$ is the root, block all the necessary intervals and then find the maximum value in the segment tree.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll ceil0(ll a, ll b) {
    return a / b + ((a ^ b) > 0 && a % b);
}

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

const int MAXN = 2e5;
const int MAXQ = 2e5;

int seg[4*MAXN + 5];
int tag[4*MAXN + 5];
int tim;
vector<int> g[MAXN + 5];
int in[MAXN + 5], out[MAXN + 5];

void push_down(int cur){
    if(!tag[cur]) return;
    for(int i = cur*2 + 1; i <= cur*2 + 2; i++){
        seg[i] += tag[cur];
        tag[i] += tag[cur];
    }
    tag[cur] = 0;
}

void update(int l, int r, int v, int ul = 0, int ur = tim &mdash; 1, int cur = 0){
    if(l <= ul && ur <= r){
        seg[cur] += v;
        tag[cur] += v;
        return;
    }
    push_down(cur);
    int mid = (ul + ur)/2;
    if(l <= mid) update(l, r, v, ul, mid, cur*2 + 1);
    if(r > mid) update(l, r, v, mid + 1, ur, cur*2 + 2);
    seg[cur] = max(seg[cur*2 + 1], seg[cur*2 + 2]);
}

int query(int l, int r, int ul = 0, int ur = tim &mdash; 1, int cur = 0){
    if(l <= ul && ur <= r) return seg[cur];
    push_down(cur);
    int mid = (ul + ur)/2;
    if(r <= mid) return query(l, r, ul, mid, cur*2 + 1);
    if(l > mid) return query(l, r, mid + 1, ur, cur*2 + 2);
    return max(query(l, r, ul, mid, cur*2 + 1), query(l, r, mid + 1, ur, cur*2 + 2));
}

void dfs1(int x, int p = 0){
    in[x] = tim++;
    for(int i : g[x]){
        if(i == p) continue;
        dfs1(i, x);
    }
    out[x] = tim &mdash; 1;
}

vector<pair<int, vector<int>>> que[MAXN + 5];
int nxt[MAXN + 5];
int ans[MAXQ + 5];
int n, q;

void dfs2(int x, int p = 0){
    for(auto &i : que[x]){
        vector<pii> skip;
        bool found = false;
        for(int j : i.ss){
            if(j == x){
                found = true;
                break;
            }
            if(in[j] <= in[x] && in[x] <= out[j]){
                skip.pb({0, in[nxt[j]] &mdash; 1});
                skip.pb({out[nxt[j]] + 1, tim &mdash; 1});
            } else {
                skip.pb({in[j], out[j]});
            }
        }
        if(found) continue;
        sort(skip.begin(), skip.end());
        int prv = 0;
        for(pii j : skip){
            if(prv < j.ff) ans[i.ff] = max(ans[i.ff], query(prv, j.ff &mdash; 1));
            prv = max(prv, j.ss + 1);
        }
        if(prv <= tim &mdash; 1) ans[i.ff] = max(ans[i.ff], query(prv, tim &mdash; 1));
    }
    update(0, tim &mdash; 1, 1);
    for(int i : g[x]){
        if(i == p) continue;
        update(in[i], out[i], -2);
        nxt[x] = i;
        dfs2(i, x);
        update(in[i], out[i], 2);
    }
    update(0, tim &mdash; 1, -1);
}

int main(){
    setIO();
    cin >> n >> q;
    for(int i = 0; i < n &mdash; 1; i++){
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    tim = 0;
    dfs1(1);
    for(int i = 0; i < q; i++){
        int x, k;
        cin >> x >> k;
        vector<int> v(k);
        for(int j = 0; j < k; j++) cin >> v[j];
        que[x].pb({i, v});
    }
    for(int i = 2; i <= n; i++) update(in[i], out[i], 1);
    dfs2(1);
    for(int i = 0; i < q; i++){
        cout << ans[i] << endl;
    }
}

In a tree, one of the farthest nodes from some node $$$x$$$ is one of the two endpoints of the diameter.

Let's try to find the diameter of the connected subgraph node $$$x$$$ is in after the nodes $$$a_{1 \dots n}$$$ are removed.

Consider an euler tour of the tree and order the nodes by their inorder traversal. When $$$k$$$ nodes are removed, the remaining nodes form $$$O(k)$$$ contiguous intervals in the tour.