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.

Let's build a segtree/sparse table where each node stores the diameter (as a pair of nodes) for the nodes with $$$in$$$ values in the range $$$[l, r]$$$. To merge two diameters, we can enumerate all $$$4 \choose 2$$$ ways to pick the new diameter and take the best one.

To answer a query, we can first generate a list of banned intervals (just like solution 1) and use that list to generate the list of unbanned intervals. Then we can query our segtree for the diameter of each of ranges. Finally, we can combine the answers of the seperate queries to obtain the diameter of the connected subgraph. We know the farthest node from node $$$x$$$ is one of the two endpoints, so it suffices to just manually check the distance of those two nodes.

Final complexity is $$$O(n \log^2 n + \sum k \log n)$$$.