Well, the first observation you can note is, you can break a balanced parenthesis in the form of a tree, for example:

       ((())())          -> Node 1
       /      \
      (())     ()         -> Node 2, 3
      /
     ()                   -> Node 4

We can assume the parenthesis at each level as node. Now, let's assign the colors to each node, the color of root node will be the color of first bracket, the color of node 2 will be the color of first bracket of it. Similarly, the color of each node will be the color of the first bracket of it. Now the problem reduces to finding the number of distinct colors in each subtree of the tree formed and outputting the answer in the asked format. This task can be done by using small-to-large merging. So, the overall complexity will be $$$O(n\log^2(n))$$$.

One can also answer the number of distinct elements within a range using either MO's algorithm (in $$$O(n \sqrt{n})$$$) or using segment tree approach in $$$O(n \log(n))$$$.

void solve(int test) {
 
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> color(n + 1);
        for(int i = 0; i < n; i++) {
                cin >> color[i + 1];
        }
        s = '(' + s + ')';
        vector<int> map_color(2 * (n + 1));
        int ind = 0;
        for(int i = 0; i < 2*(n + 1); i++) {
                if(s[i] == '(') {
                        map_color[i] = color[ind++];
                }
        }
        stack<int> st;
        vector<int> corresponding_closing(2*(n + 1));
        vector<int> real_ind(2 * (n + 1));
        for(int i = 0; i < 2*(n + 1); i++) {
                if(s[i] == '(') {
                        st.push(i);
                        real_ind[i] = i;
                } else {
                        corresponding_closing[st.top()] = i;
                        st.pop();
                }
        }
        vector<pair<int, int>> ans;
        map<int, set<int>> m_set;
        function<void(int start, int end)> f = [&](int st, int end) {
                int cur = st + 1;
                vector<pair<int, int>> set_size;
                while(cur < end) {
                        f(cur, corresponding_closing[cur]);
                        set_size.emplace_back(cur, sz(m_set[real_ind[cur]]));
                        cur = corresponding_closing[cur] + 1;
                }
                sort(all(set_size), [&](pair<int, int> p1, pair<int, int> p2){
                        return p1.ss > p2.ss;
                });
                if(sz(set_size) == 0) {
                        set_size.emplace_back(st, 0);
                }
                for(int i = 1; i < sz(set_size); i++) {
                        for(auto ele: m_set[real_ind[set_size[i].first]]) {
                                m_set[real_ind[set_size[0].first]].insert(ele);
                        }
                        m_set[real_ind[set_size[i].first]].clear();
                }
                real_ind[st] = real_ind[set_size[0].first];
                m_set[real_ind[st]].insert(map_color[st]);
                ans.emplace_back(st, sz(m_set[real_ind[st]]));
 
        };
        f(0, 2*(n + 1) - 1);
        sort(all(ans));
        for(int i = 1; i < n + 1; i++) {
                cout << ans[i].ss << " ";
        }
        cout << nl;
}

#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;

typedef tree<int, null_type, less<int>, 
rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<bool>> vvb;
typedef vector<long long> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;

#define F first
#define S second
#define PB push_back
#define sz(x) (int)(x).size()

const int M = 1e9 + 7;
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}

void solve(){
	int n; cin>>n;
	string s; cin>>s;
	vector<int> colors(2*n, -1);
	for(int i = 0; i < 2*n; i++) if(s[i] == '('){
		cin>>colors[i];
	}
	stack<int> st;
	vector<int> closing(2*n, -1);
	for(int i = 0; i < 2*n; i++){
		if(s[i] == '(') st.push(i);
		else {
			closing[st.top()] = i;
			colors[i] = colors[st.top()];
			st.pop();
		}
	}
	vector<pll> queries(0);
	for(int i = 0; i < 2*n; i++) if(closing[i] != -1){
		int l = i, r = closing[i];
		queries.push_back({l,r});
	}
	int rootn = 400;
	// mo's algorithm
	sort(queries.begin(), queries.end());
	int q = queries.size();
	int lidx = 0, ridx = 0;
	for(int l = 0; l < q;){
		int r = l + rootn;
		r = min(r, q);
		while(queries[lidx].F < l) lidx++;
		while(queries[ridx].F < r) ridx++;
		sort(queries.begin()+l, queries.begin()+r);
		l = r;
	}
	vector<int> freq(n+2, 0);
	int distinct = 0;
	auto removecol = [&](int col){
		freq[col]--;
		if(freq[col] == 0) distinct--;
	};
	auto addcol = [&](int col){
		freq[col]++;
		if(freq[col] == 1) distinct++;
	};
	lidx = 0; ridx = -1;
	vector<int> result(2*n, -1);
	for(int i = 0; i < q; i++){
		auto que = queries[i];
		while(lidx > que.F){
			lidx--;
			addcol(colors[lidx]);
		}
		while(ridx < que.S){
			ridx++;
			addcol(colors[ridx]);
		}
		while(lidx < que.F){
			removecol(colors[lidx]);
			lidx++;
		}
		while(ridx > que.S) {
			removecol(colors[ridx]);
			ridx--;
		}
		result[que.F] = distinct;
	}
	for(int i = 0; i < 2*n; i++) if(s[i] == '('){
		cout<<result[i]<<" ";
	}
	cout<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin>>T;
    while(T--){
    	solve();
    }
    return 0;
}

The first key observation is Alice can never win since Bob can always make the GCD equal 1 by adding 1 to the array on his turn which leads to a draw.

Analyzing the possible cases when Alice removes an element. Let gcd of the remaining n-1 elements be x with prime factorization of the form $$$a1^{p1}*a2^{p2}....aN^{pN}$$$, where a1..aN are prime numbers and p1..pN are non-negative integers.

Case 1: p1+p2+...pN is even Bob can add the current GCD to maintain the same GCD with an even exponent sum, leading to his victory.

Case 2: p1+p2+...pN is odd (>1) Bob can add something x of the form $$$a1^{(p1-1)}*a2^{p2}....aN^{pN}$$$. So the new gcd will be now x which leads to Bob victory since p1+p2+..pN — 1 will be even.

Case 3: p1+p2+...pN is odd (=1) ie. x is a prime number Here Bob cannot force a win. Therefore, he will aim for a draw by adding 1.

Case 4: x = 1 Bob cannot force a win in this case and can only aim for a draw.

Analyzing the four cases, it becomes evident that Alice's optimal strategy involves removing an element from the array, resulting in a GCD that is either a prime number (Case 3) or equal to 1 (Case 4). This specific approach ensures that the game concludes in a draw. Any other outcome would invariably lead to Alice's defeat.

So to determine whether removing any element from the original array enables us to achieve a GCD that is either prime or 1 efficiently, we can employ a two-step approach:

Prefix and Suffix GCD Arrays: Firstly, we create both prefix and suffix GCD arrays. This will help us to compute the GCD of the remaining elements efficiently after each element removal.

With the computed GCD value at hand, we need to check whether it is a prime number or equals 1. To accomplish this, we utilize a sieve algorithm to precompute prime numbers.

So the total time complexity will be $$$O(A\log(\log(A)))$$$ where A is the largest element possible in array ie 10^6 for sieve algorithm and rest all computations can be done in $$$O(N\log(A))$$$ per test case.

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

typedef long long ll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<bool>> vvb;
typedef vector<long long> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;

#define F first
#define S second
#define PB push_back
#define sz(x) (int)(x).size()

const int M = 1e9 + 7;
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}

const int maxn = 1000001;
bool notPrime[maxn];
void solve(){
    int n; cin>>n;
    vi arr(n);
    for(int i = 0; i < n; i++){
        cin>>arr[i];
    }
    vi pre(n, 1), suff(n,1);
    pre[0] = arr[0];
    suff[n-1] = arr[n-1];
    for(int i = 1; i < n; i++){
        pre[i] = __gcd(pre[i-1], arr[i]);
    }
    for(int i = n-2; i >= 0; i--){
        suff[i] = __gcd(suff[i+1], arr[i]);
    }
    bool draw = false;
    for(int i = 1; i < n-1; i++){
        int curr = __gcd(pre[i-1], suff[i+1]);
        if(curr == 1 || !notPrime[curr]) draw = true;
    }
    if(suff[1] == 1 || !notPrime[suff[1]]) draw = true;
    if(pre[n-2] == 1 || !notPrime[pre[n-2]]) draw = true;
    if(draw) cout<<"DRAW\n";
    else cout<<"BOB\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T; cin>>T;
    for(int i = 2; i < maxn; i++) {
        if(!notPrime[i]) for(int j = i+i; j <= maxn; j += i){
            notPrime[j] = true;
        }
    }
    while(T--){
        solve();
    }
    return 0;
}

First, we need to get the connected components of the graph. This is straightforward when edges are provided, we can simply run a DFS to get component sizes. In the case of non-edges, we have what is called an inverse graph. The basic idea is that you maintain a global array of unvisited vertices, and then to traverse you start with an unvisited node and try to move to other unvisited vertices from the current vertex. If you do so, you encounter non-edges only O(m) times. Here is a detailed blog explaining this process: cf blog.

Once we have the sizes of the connected components, we can reach the optimal value either by removing none, one, two, or three components. A thing to note is that there will exist an optimal answer where we never remove two components of the same size as that has the same effect as removing no component. Similarly, we will never have three components of the same size, as removing them has the same effect as removing just one component of that size. Therefore one of the optimal solutions will remove components with distinct sizes.

The sum of the sizes of connected components is n. Therefore the number of distinct sizes is $$$O(\sqrt{n})$$$. We can brute force the components that can be removed for each case (no removal, one component removal, ..., three component removal). For the worst case scenario of removal of three components, the brute force iteration will take $$$O(n*\sqrt{n})$$$.

To get the xor of the component after the removal of an element, we can simply xor the xor-score with the component size we need to remove.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<bool>> vvb;
typedef vector<long long> vll;
typedef pair<ll, ll> pll;
 
#define F first
#define S second
#define PB push_back
 
const int M = 1e9 + 7;
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
 
vector<int> getConnectedCompForInverse(int n) {
    int m; cin>>m;
    vector<set<int>> notGraph(n);
    for(int i = 0; i < m; i++){
        int x,y; cin>>x>>y;
        x--; y--;
        notGraph[x].insert(y);
        notGraph[y].insert(x);
    }
    set<int> unvis;
    for(int i = 0; i < n; i++){
        unvis.insert(i);
    }
    int cc = 0;
    vector<int> comps(0);
    for(int i = 0; i < n; i++){
        auto curr = unvis.find(i);
        if(curr == unvis.end()) continue;
        else {
            cc++;
            int compsize = 0;
            queue<int> bfs;
            vector<int> tovis;
            bfs.push(i);
            unvis.erase(curr);
            while(!bfs.empty()){
                int curv = bfs.front(); bfs.pop();
                compsize++;
                for(int nbr: unvis){
                    // no edge between curv and nbr ~ O(m)
                    if(notGraph[curv].find(nbr) != notGraph[curv].end()) continue;
                    else{
                        tovis.push_back(nbr);
                        bfs.push(nbr);
                    }
                }
 
                for(int &nbr: tovis){
                    unvis.erase(nbr);
                }
 
                tovis.clear();
 
            }
            comps.push_back(compsize);
        }
    }
    return comps;
}
vector<int> getConnectedCompNormal(int n){
    int m; cin>>m;
    vector<vector<int>> graph(n+1, vector<int>(0));
    for(int i = 0; i < m; i++){
        int x,y; cin>>x>>y;
        x--; y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    vector<bool> vis(n, false);
    function<int(int)> dfs = [&](int curr) {
        vis[curr] = true;
        int res = 1;
        for(int nbr: graph[curr]) if(!vis[nbr]) {
            res += dfs(nbr);
        }
        return res;
    };
    vector<int> comps(0);
    for(int i = 0; i < n; i++) if(!vis[i]) {
        comps.push_back(dfs(i));
    }
    return comps;
}
 
void solve(){
    int q; cin>>q;
    int n; cin>>n;
    vector<int> comps = (q == 0) 
        ? getConnectedCompNormal(n) 
        : getConnectedCompForInverse(n);
    
    vector<int> freq(n+1, 0);
    int totalxor = 0;
    for(int v: comps) {
        totalxor = totalxor ^ v;
        freq[v]++;
    }
    int result = totalxor;
    // remove one
    for(int i = 1; i <= n; i++) if(freq[i] > 0) {
        result = max(result, totalxor ^ i);
    }
    // remove two
    for(int i = 1; i <= n; i++) if(freq[i] > 0) {
        for(int j = 1; j < i; j++) if(freq[j] > 0){
            result = max(result, totalxor ^ i ^ j);
        }
    }
    // remove three
    for(int i = 1; i <= n; i++) if(freq[i] > 0) {
        for(int j = 1; j < i; j++) if(freq[j] > 0) {
            for(int k = 1; k < j; k++) if(freq[k] > 0) {
                result = max(result, totalxor ^ i ^ j ^ k);
            }
        }
    }
    cout<<result<<"\n";
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin>>t;
    while(t--) {
        solve();
    }
}

It can be shown using mathematical induction that there will always be a path covering all N*N cells of the grid for an NxN grid when N is even. (Proof Sketch: Create a path that always ends at i = N or j = N for N = 2, then extend that path for N = N + 2)

For an NxN grid when N is odd, let (i, j) be the coordinates of the source cell. It can similarly be shown that there will always be a path covering all cells when i + j is even, and a path covering N * N — 1 cells when i + j is odd.

We can prove that no path covering all cells exists for a source cell with odd N and odd i + j, by painting all cells with even i + j Black(B) and all others White(W). Note that we can only go from B to W and from W to B (cannot go B to B or W to W). So all paths look like WBWBW... Now there are (N*N+1)/2 B cells and (N*N-1)/2 W cells. Since we have more B cells than W cells, there can't be a path like WBWBW... that covers moth B cells that W cells, hence there can't be a path covering N*N cells.

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

int main(){
	int T; cin>>T;
	while(T--){
		int n; cin>>n;
		int x,y; cin>>x>>y;
		if(n%2 == 1 && (x + y)%2 == 1) cout<<(n*n-1)<<"\n";
		else cout<<n*n<<"\n";
	}
}

For the first k distinct keys, we will add it directly to our typewriter. Now when the next distinct key arrives and we have already marked all the k keys available on the typewriter, it is always optimal to remove the key from our typewriter that will not occur for the longest time in our array from the current position. This is in accordance with optimal cache replacement policy.

We can get the key that will not occur for the longest time using a set sorted based on the next occurence of the character in $$$O(\log(k))$$$, therefore this problem can be solved in $$$O(n*\log(k))$$$.

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

typedef long long ll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<bool>> vvb;
typedef vector<long long> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;

#define F first
#define S second
#define PB push_back
#define sz(x) (int)(x).size()

const int M = 1e9 + 7;
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}

void solve(){
    int n,k; cin>>n>>k;
    vll arr(n);
    for(int i = 0; i < n; i++) cin>>arr[i];
    map<int, int> lastpos;
    vector<int> nxt(n, n+1);
    for(int i = n-1; i >= 0; i--){
        if(lastpos.find(arr[i]) != lastpos.end()) nxt[i] = lastpos[arr[i]];
        lastpos[arr[i]] = i;
    }
    set<int> keys;
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(keys.find(i) != keys.end()) {
            keys.erase(i);
            keys.insert(nxt[i]);
            continue;
        }
        ans++;
        if(keys.size() < k) {
            keys.insert(nxt[i]);
        } else {
            // keys full need to remove one of them
            keys.erase((*keys.rbegin()));
            keys.insert(nxt[i]);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}