Let's have a value $$$a_i$$$ $$$(1 \le i \le n)$$$.

What if the $$$k'th$$$ $$$(0 \le k \le 16)$$$ bit of $$$a_i$$$ is $$$1$$$? It will contribute $$$2^k$$$ to the answer if the $$$k'th$$$ bit of $$$b_j$$$ $$$(1 \le j \le n)$$$ is $$$0$$$. Let's assume, $$$x$$$ $$$(1 \le x \le n)$$$ number of values are present in array $$$b$$$ where the $$$k'th$$$ bit is $$$0$$$. Then $$$a_i$$$ will contribute $$$x*2^k$$$ to the answer. If the $$$k'th$$$ bit is $$$0$$$ of $$$a_i$$$, it will contribute $$$(n-x)2^k$$$ to the answer. Now, compute the number of times $$$a_i$$$ will make a pair with $$$b_j$$$. It's $$$(n-1)!$$$.

So, the final result is the sum of $$$x*2^k(n-1)!$$$ if the $$$k'th$$$ bit is $$$1$$$ of $$$a_i$$$, $$$(n-x)2^k(n-1)!$$$ otherwise.

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n; cin >> n;
    std::vector<int> v1(30);
    ll gun = 1, ans = 0;
    for(int i = 1; i < n; i++) {
        gun = (gun * i) % mod;
    } for(int i = 0; i < n; i++) {
        int a; cin >> a;
        for(int j = 0; j < 20; j++) {
            int a1 = (a >> j)&1;
            if(a1) v1[j]++;
        }
    } for(int i = 0; i < n; i++) {
        int a; cin >> a;
        for(int j = 0; j < 20; j++) {
            int a1 = (a >> j)&1;
            ll b1 = gun * ( 1 << j) % mod;
            if(a1) {
                ans += (n - v1[j]) * b1 % mod;
            } else {
                ans += v1[j] * b1 % mod;
            }
        }
    } cout << ans % mod << "\n";

}

Calculate the contribution of $$$k'th$$$ $$$(0 \le k \le 27)$$$ bit to the answer. Count the number of ways $$$x$$$, in which $$$k'th$$$ bit is $$$1$$$ within $$$n!$$$ permutations. Add $$$x*2^k$$$ to the answer.

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

const int mx = 16, mod = 1e9 + 7;
int n, a[mx], b[mx], d, dp[2][1 << mx];
int f(int i = 0, int mask = 0, int p = 0) {
    if(i >= n) {
        return p * (1 << d);
    }
    int &res = dp[p][mask]; if(~res) return res; res = 0;
    for(int j = 0; j < n; j++) {
        if(!(mask & (1 << j))) {
            res += f(i + 1, mask | (1 << j), p ^ (((a[j] + b[i]) >> d) & 1));
            if(res >= mod) res -= mod;
        }
    }
    return res;
}
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];    
    for(int i = 0; i < n; i++) cin >> b[i];
    int ans = 0;
    for(d = 0; d <= 27; d++) {
        memset(dp, -1, sizeof dp);
        ans = (ans + f()) % mod;
    }
    cout << ans << '\n';
    return 0;
}

Our intended solution was using Manachar algorithm.

From manacher algorithm, you can find every palindrome's start and end point. There can not have more than n palindrome (n = string-length).

Sort Reversely. Take the maximum length unused palindrome and still for those index not cover by any previous palindrome, cover it by the current palindrome length and erase those index as we find the maximum palindrome length for that specific index. Finally, print the index answer.

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

// l[2 * i] = len of palindrome centered at s[i]
// l[2*i+1] = len of palindrome centered at s[i], s[i+1]
vector<int> manacher(string &s) {
	int n = s.size(); vector<int> l(2 * n); 
	for (int i = 0, j = 0, k; i < n * 2; i += k, j = max(j - k, 0)) {
		while (i >= j && i + j + 1 < n * 2 && s[(i - j) / 2] == s[(i + j + 1) / 2]) ++j;
		l[i] = j;
		for (k = 1; i >= k && j >= k && l[i - k] != j - k; ++k) 
			l[i + k] = min(l[i - k], j - k);
	} return l;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		int n; cin >> n;
		vector<vector<int>> o(n + 1);
		string s; cin >> s;
		auto T = manacher(s);
		for(int i = 0; i < n; i++) {
			int val, l, r;
			val = T[i * 2], l = i - val / 2, r = i + val / 2, o[l].push_back(val), o[r + 1].push_back(-val);
			if(T[i * 2 + 1]) val = T[i * 2 + 1], l = i - val / 2 + 1, r = i + val / 2, o[l].push_back(val), o[r + 1].push_back(-val);
		}
		multiset<int> ms;
		for(int i = 0; i < n; i++) {
			for(int j: o[i]) {
				if(j < 0) {
					ms.erase(ms.find(-j));
				} else {
					ms.insert(j);
				}
			}
			cout << *ms.rbegin() << " \n"[i + 1 == n];
		}
	}	
	return 0;
}

Calculate all possible distinct subsequence sums using coin change dp and store them in array $$$x$$$. Also calculate the minimum possible and maximum subsequence sum. Relax your answer by $$$|2⋅x−(p+q)|$$$.

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

const int mx = 500 * 500 + 2;
int dp[mx * 2 + 4];
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    dp[mx + 2] = 1;
    int n, p = 0, q = 0; cin >> n;
    for(int i = 0, x; i < n; i++) {
        cin >> x;
        if(x > 0) {
            p += x;
            for(int i = mx; i >= -mx; i--) if(i + x <= mx) dp[i + x + (mx + 2)] |= dp[i + (mx + 2)];
        } else {
            q += x;
            for(int i = -mx; i <= mx; i++) if(i + x >= -mx) dp[i + x + (mx + 2)] |= dp[i + (mx + 2)];
        }
    }
    int mi = INT_MAX;
    for(int i = -mx; i <= mx; i++) if(dp[i + (mx + 2)]) mi = min(mi, abs(2 * i - p - q));
    cout << mi << '\n';
    return 0;
}

You just have to implement the basic expected value equation. Let's think about a state, in which the first $$$q$$$ cities are not explored and $$$n-q$$$ cities are. $$$E(q)$$$ is the expected cost to explore the remaining q cities.

$$$E(q) = \frac{1}{n}{E(q-1)+a_1}+......+\frac{1}{n}{E(q-1)+a_q}+\frac{1}{n}{E(q)+a_{p+1}}+......+\frac{1}{n}{E(q)+a_n}$$$

$$$E(q) = \frac{q}{n}E(q-1)+\frac{n-q}{n}E(q)+\frac{1}{n}(a_1+a_2+......+a_n)$$$

$$$(1-\frac{n-q}{n})E(q)=\frac{q}{n}E(q-1)+\frac{1}{n}(a_1+a_2+......+a_n)$$$

$$$\frac{q}{n}E(q)=\frac{q}{n}E(q-1)+\frac{1}{n}(a_1+a_2+......+a_n)$$$

$$$E(q)=E(q-1)+\frac{1}{q}(a_1+a_2+......+a_n)$$$

Then

$$$E(q-1)=E(q-2)+\frac{1}{q-1}(a_1+a_2+......+a_n)$$$

So

$$$E(q)=E(q-2)+\frac{1}{q-1}(a_1+a_2+......+a_n)+\frac{1}{q}(a_1+a_2+......+a_n)$$$

$$$E(q)=E(q-2)+(\frac{1}{q}+\frac{1}{q-1})(a_1+a_2+......+a_n)$$$

As

$$$E(0)=0$$$

$$$E(q)=(\frac{1}{q}+\frac{1}{q-1}+......+\frac{1}{2}+1)(a_1+a_2+......+a_n)$$$

Initially, All of the n cities are not explored. So, the answer is $$$E(n)$$$, where

$$$E(n)=(\frac{1}{n}+\frac{1}{n-1}+......+\frac{1}{2}+1)(a_1+a_2+......+a_n)$$$

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int power(long long a, long long b) {
	long long x = 1;
	while (b) {
		if (b & 1)x = x * a % mod;
		a = a * a % mod;
		b >>= 1;
	} return x;
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, s = 0, a = 0; cin >> n;
	for(int i = 1, x; i <= n; i++) {
		cin >> x;
		a = (a + x) % mod;
		s = (s + power(i, mod - 2)) % mod;
	}
	a = 1LL * a * s % mod;
	cout << a << '\n';
	return 0;
}

Save everything and solve query reversely. Can use DSU to merge two componentand and for update/max_value_find can use multiset.

Hint: Save all the query and solve offline.

Initially, merge all the edge as component using DSU which not deleted at all. Then,

1st query: just merge the edge.

2nd query: Find the vertex's parent and erase the previous value and insert the new one from that component. Here, can use multiset cause there can be duplicate value.

3rd query: Find the maximum value from the vertex parent's component and store it.

Finally print the stored value reversely, as we solved query reversely.

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

const int mx = 1e5 + 10;
int p[mx], type[mx], f[mx], s[mx], rs[mx], n, m, q, u[mx], v[mx], vis[mx], par[mx];
multiset<int> score[mx];

int find(int u) {return par[u] == u ? u: par[u] = find(par[u]);}
void add(int u, int v) {
    u = find(u);
    v = find(v);
    if(u != v) {
        if(score[u].size() > score[v].size()) swap(u, v);
        for(int x: score[u]) score[v].insert(x);
        par[u] = v;
    }
}
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) par[i] = i;
    for(int i = 1; i <= n; i++) cin >> p[i];
    for(int i = 1; i <= m; i++) cin >> u[i] >> v[i];
    cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> type[i];
        if(type[i] == 1) {
            cin >> f[i];
            vis[f[i]] = 1;
        } else if(type[i] == 2) {
            cin >> f[i] >> s[i];
            rs[i] = p[f[i]];
            p[f[i]] = s[i];
        } else if(type[i] == 3) {
            cin >> f[i];
        }
    }
    for(int i = 1; i <= n; i++) score[i].insert(p[i]);
    for(int i = 1; i <= m; i++) {
        if(!vis[i]) {
            add(u[i], v[i]);
        }
    }
    vector<int> ans;
    for(int i = q; i > 0; i--) {
        if(type[i] == 1) {
            add(u[f[i]], v[f[i]]);
        } else if(type[i] == 2) {
            int root = find(f[i]);
            score[root].erase(score[root].find(s[i]));
            score[root].insert(rs[i]);
        } else {
            int root = find(f[i]);
            ans.push_back(*score[root].rbegin());
        }
    }
    reverse(ans.begin(), ans.end());
    for(int x: ans) cout << x << '\n';
    return 0;
}

Find out minimum value $$$x_{min}$$$ and $$$x_{max}$$$ from the values of $$$x$$$ of all co-ordinates. Similarly find $$$y_{min}$$$ and $$$y_{max}$$$. Then, the answer is $$$(x_{max}-x_{min})(y_{max}-y_{min})$$$

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

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		int n, nx = INT_MAX, ny = INT_MAX, mx = INT_MIN, my = INT_MIN; cin >> n;
		for(int i = 0; i < n; i++) {
			int x, y; cin >> x >> y;
			nx = min(nx, x);
			mx = max(mx, x);
			ny = min(ny, y);
			my = max(my, y);
		}
		int a = max(mx - nx, my - ny);
		cout << 1LL * a * a << '\n';
	}
	return 0;
}

The answer is $$$max(a_{first_max}*a_{second_max}*a_{third_max},a_{first_max}*a_{first_min}*a_{second_min})$$$

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

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		int n; cin >> n;
		vector<int> v(n); for(int &i: v) cin >> i;
		sort(v.rbegin(), v.rend());
		long long ma = max(1LL * v[0] * v[1] * v[2], 1LL * v[0] * v[n - 2] * v[n - 1]);
		cout << ma << '\n';
	}
	return 0;
}

Let $$$d$$$ is a divisor of $$$a$$$. Then calculate two values $$$v$$$ and $$$m$$$ where $$$v=\frac{a^2}{d}$$$ and $$$m=v-d+1$$$. If $$$v$$$ $$$mod$$$ $$$2=d$$$ $$$mod$$$ $$$2$$$ and $$$\frac{m}{2} \ge a$$$, then there exists a pythagorean tuple in which $$$a$$$ is the minimum side. Count the number of $$$d$$$ for each possible $$$a$$$ $$$(1 \le a \le 10^5)$$$ and get the cummulative sum of them. Then answer each query in $$$O(1)$$$.

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

const int mx = 1e5 + 10;
int lpf[mx], dp[mx];
int p[10], c[10], ind;
int N, curr_ans = 0;
void backtrack(int i = 0, long long curr = 1) {
	if(i >= ind) {
		long long y = curr, x = 1LL * N * N / y;
		if((x & 1) == (y & 1) && x - y >= 2 * N) {
			curr_ans++;
		}
		return;
	}
	for(int j = 0; j <= c[i]; j++) {
		backtrack(i + 1, curr);
		curr *= p[i];
	}
}
int calculate(int n) {
	/*prime factorize*/
	ind = 0;
	int _n = n; while(_n != 1) {
		int P = lpf[_n], C = 0;
		while(lpf[_n] == P) _n /= P, C++;
		p[ind] = P; c[ind++] = C * 2; // as square
	}

	/*backtrack over all divisor*/
	N = n; curr_ans = 0;
	backtrack();
	return curr_ans;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i = 2; i < mx; i += 2) lpf[i] = 2;
	for(int i = 3; i * i < mx; i += 2) {
		if(lpf[i] == 0) {
			for(int j = i * i; j < mx; j += i << 1) {
				if(lpf[j] == 0) {
					lpf[j] = i;
				}
			}
		}
	}
	for(int i = 1; i < mx; i++) if(lpf[i] == 0) lpf[i] = i;

	for(int i = 1; i < mx; i++) {
		dp[i] = dp[i - 1] + calculate(i);
	}

	int t; cin >> t; while(t--) {
		int n; cin >> n;
		cout << dp[n] << '\n';
	}
	return 0;
}

Just print Team_Robust.

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

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout << "Team_Robust\n";
	return 0;
}