There are many ways to solve this problem. One of which is described here.

All we have to do is find the maximum number of indices such that both strings have different values. We can do this by sorting one string in increasing order and another one in decreasing order. Now count of these indices gives us the number of set bits and the remaining are unset bits.

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

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	string s, t;
	cin >> s >> t;
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	string ans = "";
	for(int i = 0; i < (int) s.size(); i ++) {
		if(s[i] != t[i]) ans += "1";
		else ans += "0";
	}
	sort(ans.begin(), ans.end());
	reverse(ans.begin(), ans.end());
	cout << ans;
	
	return 0;
}

Go for the tutorial of GS more like BS(Hard version)

Like in Kadane's Algorithm, in update section we check for the max_ending_here only if the current index is a good index.

Unlike the easy version, we cannot iterate for each coin as $$$k \le {10^9}$$$. Instead, we can use binary search to obtain the maximum flow. First, let us assume $$$x$$$ to be the maximum flow, now we can check if we can achieve this flow using at most $$$k$$$ coins. If $$$x$$$ can be achieved then $$$x$$$ is our answer and we look for a bigger $$$x$$$, otherwise we look for a smaller $$$x$$$.

NOTE: Since answer can be bigger than $$$10^{18}$$$, it is better to use upper bound as $$$2 \cdot 10^{18}$$$.

Time Complexity: $$$O(n \log ({2 \cdot 10^{18}}))$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 10;
ll n, k, c[MAX], x[MAX];
bool f(ll val) {
	ll cost = 0;
	for(int i = 1; i <= n; i ++) {
		if(c[i] >= val) continue;
		ll diff = val - c[i];
		cost += diff / x[i];
		if(diff % x[i] != 0) cost ++;
		if(cost > k) return false;
	}
	return cost <= k;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> c[i] >> x[i];
	ll l = 0, r = 2e18;
	while(r - l > 1) {
		ll m = (l + r) / 2;
		if(f(m)) l = m;
		else r = m;
	}
	cout << l;
	
	return 0;
}

Consider an example $$$mmeeooww$$$, here every letter is repeated 2 times. Here we can form a total of 18 good strings. How are we calculating the number of good strings? Let's see.

First observation: Number of picked $$$m$$$ and $$$w$$$ do not affect good string. So we first calculate total number of ways to pick non-zero number of $$$m$$$, which is equal to $$$({2^{n_m}}-1)$$$, similarly for $$$w$$$ the number of ways are $$$({2^{n_w}}-1)$$$.

Second Observation: We cannot pick only one $$$e$$$. Because then after we cannot pick any $$$o$$$ as $$$n_e > n_o$$$ must hold. So let's pick $$$k$$$ number of $$$e's$$$, so good strings can have $$${1, 2 \dots k-1}$$$ numbers of $$$o$$$. Picking $$$1$$$ $$$o$$$ from $$$n_o$$$ number of $$$o's$$$ is $$$\binom{n_o}{1}$$$, for $$$2$$$ is $$$\binom{n_o}{2}$$$ $$$\dots$$$ for $$$k-1$$$ is $$$\binom{n_o}{k-1}$$$. We can precompute each binomail coefficient. Now answer for $$$k$$$ number of $$$e$$$ is $$$({2^{n_m}}-1) \space \binom{n_e}{k} \space (\sum_{x=1}^{k-1} \binom{n_o}{x}) \space ({2^{n_w}}-1)$$$. We can do this for each $$$k$$$ from 2 to $$${n_e}$$$.

Time Complexity: $$$O(n)$$$

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

#define endl '\n'
#define all(v) v.begin(), v.end()
typedef long long ll;

const ll mod = 1e9 + 7;

ll power(ll x, ll y) {
    ll res = 1;
    while(y) {
        if (y & 1)  res = (res*x) % mod;
        y >>= 1;
        x = (x*x) % mod;
    }
    return res;
}

vector<ll> fact;

void preprocess(int n) {
    fact.resize(n+1, 1);
    for(int i = 2; i <= n; i++)
        fact[i] = (fact[i-1] * i) % mod;
    return;
}

ll nCr(ll n, ll r) {
    return fact[n] * power(fact[r], mod-2) % mod * power(fact[n-r], mod-2) % mod;
}

int main() {
	int n;		cin>>n;
	string s;	cin>>s;
	
	int n_m = count(all(s), 'm');
	int n_e = count(all(s), 'e');
	int n_o = count(all(s), 'o');
	int n_w = count(all(s), 'w');

	if(n_m == 0 or n_e == 0 or n_o == 0 or n_w == 0) {
		cout << 0 << endl;
		exit(0);
	}
	
	preprocess(n);
	
	ll tot_ways_m = 1, tot_ways_w = 1;
	for(int i = 1; i <= n_m; ++i)
		tot_ways_m = (tot_ways_m << 1) % mod;
	tot_ways_m = (mod + tot_ways_m - 1) % mod;
	
	for(int i = 1; i <= n_w; ++i)
		tot_ways_w = (tot_ways_w << 1) % mod;
	tot_ways_w = (mod + tot_ways_w - 1) % mod;

	vector<ll> ncr(n + 1);
	for(int i = 1; i <= n_o; ++i)
		ncr[i] = nCr(n_o, i);
	for(int i = 1; i <= n_e; ++i)
		ncr[i] = (ncr[i] + ncr[i-1]) % mod;

	ll ans = 0;

	for(int i = 2; i <= n_e; ++i) {
		ll temp = 1;
		temp = temp * tot_ways_m % mod;
		temp = temp * nCr(n_e, i) % mod;
		temp = temp * ncr[i-1] % mod;
		temp = temp * tot_ways_w % mod;
		ans = (ans + temp) % mod;
	}

	cout << ans << endl;
}

Initially, there were two subtasks for this problem. In the first task, you need to find a valid numbering for a given tree and in second subtask you need to validate for a given tree and numbering if it is optimal or not. The first subtask was just a modified version of problem 1325C so I decided to remove it.

Let the maximum value of $$$MEX(u, v)$$$ be $$$x$$$. The most important observation for this problem is that we put numbers $$$0,1,2 \dots x-1$$$ on a path which is longest among all the paths. This path is known as $$$diameter$$$ and is easy to find. Now we have to check if values $$$0,1,2 \dots x-1$$$ lie on a diameter. How can we do that? Let's create a new graph $$$G$$$ using the edges with numbers $$$0,1,2 \dots x-1$$$, we know if the numbering is optimal, these edges form a line graph. We can check if $$$G$$$ is a line graph and that will be the answer.

Time Complexity: $$$O(n)$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 10;
vector <int> g[MAX];
bool vis[MAX];
int x[MAX], d[MAX], U[MAX], V[MAX];
void dfs(int u, int p = 0) {
	for(int v : g[u]) {
		if(v != p) {
			d[v] = d[u] + 1;
			dfs(v, u);
		}
	}
}
void dfs1(int u) {
	vis[u] = true;
	for(int v : g[u]) if(!vis[v]) dfs1(v);
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	set <int> used;
	for(int i = 1; i < n; i ++) {
		cin >> U[i] >> V[i] >> x[i];
		used.insert(x[i]);
		g[U[i]].push_back(V[i]);
		g[V[i]].push_back(U[i]);
	}
	if((int) used.size() != n - 1) return cout << "No", 0;
	dfs(1);
	int a = max_element(d, d + MAX) - d;
	memset(d, 0, sizeof(d));
	dfs(a);
	int dim = *max_element(d, d + MAX);
	for(int i = 1; i <= n; i ++) g[i].clear();
	for(int i = 1; i < n; i ++) {
		if(x[i] < dim) {
			g[U[i]].push_back(V[i]);
			g[V[i]].push_back(U[i]);
		}
	}
	int comp = 0, one = 0, two = 0;
	for(int i = 1; i <= n; i ++) {
		int deg = g[i].size();
		if(deg == 0) continue;
		if(deg == 1) one ++;
		else if(deg == 2) two ++;
		else return cout << "No", 0;
		if(!vis[i]) {
			dfs1(i);
			comp ++;
		}
	}
	if(one == 2 && two == dim - 1 && comp == 1) cout << "Yes";
	else cout << "No";
	
	return 0;
}

Since the array $$$p$$$ is a static array and the queries may overlap with each other, we can use Mo's Algorithm to solve this problem. When adding an element $$$x$$$, we add to our answer the number of elements in range $$$[0, x-k]$$$ and $$$[x+k, 10^6]$$$. When removing an element $$$x$$$, we subtract from out answer the number of elements in range $$$[0, x-k]$$$ and $$$[x+k, 10^6]$$$. To find number of element in these ranges, we can use Fenwick Tree.

Time Complexity: $$$O((n+q)\sqrt{n} \log ({10^6}))$$$

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int BLK = 900;
const int MAX = 1e5 + 10;
const int MAXV = 1e6 + 10;
int n, k, q, p[MAX];
struct Query {
	int l, r, id;
	void read(int _i) {
		cin >> l >> r;
		id = _i;
	}
	bool operator < (Query a) {
		if(l / BLK != a.l / BLK) return l / BLK < a.l / BLK;
		return ((l / BLK) & 1 ? r < a.r : r > a.r);
	}
} Q[MAX];
ll ans[MAX], cur = 0;
struct FenwickTree {
	int n;
	vector <int> BIT;
	FenwickTree(int n):
		n(n), BIT(2 * n) {}
	void update(int x, int val) {
		while(x <= n) {
			BIT[x] += val;
			x += x & (-x);
		}
	}
	int get(int x) {
		int sum = 0;
		while(x > 0) {
			sum += BIT[x];
			x -= x & (-x);
		}
		return sum;
	}
};
FenwickTree FW(MAXV + 100);
int query(int l, int r) {
	if(l < 2) return FW.get(r);
	return FW.get(r) - FW.get(l - 1);
}
void add(int x) {
	cur += query(0, x - k) + query(min(x + k, MAXV), MAXV);
	FW.update(x, 1);
}
void remove(int x) {
	cur -= query(0, x - k) + query(min(x + k, MAXV), MAXV);
	FW.update(x, -1);
}
void mos_algorithm() {
	int l = Q[0].l, r = Q[0].l - 1;
	for(int i = 0; i < q; i ++) {
		while(l < Q[i].l) remove(p[l ++]);
		while(l > Q[i].l) add(p[-- l]);
		while(r < Q[i].r) add(p[++ r]);
		while(r > Q[i].r) remove(p[r --]);
		ans[Q[i].id] = cur;
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i ++) cin >> p[i];
	for(int i = 0; i < q; i ++) Q[i].read(i);
	sort(Q, Q + q);
	mos_algorithm();
	for(int i = 0; i < q; i ++) cout << ans[i] << "\n";
	
	return 0;
}