Let $$$n$$$ be the length of the string. Output the first $$$n-2$$$ characters of the string (to remove the suffix "us"), then the lowercase letter "i".

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
 
void tc () {
    string str;
    cin >> str;
    str.pop_back();
    str.pop_back();
    cout << str + "i" << '\n';
}
 
int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Note that if you can ever do an operation, the answer is $$$1$$$. This is because once you've done an operation on a string of length $$$k$$$, you are free to choose any character to replace $$$s_i$$$ with. Therefore, if you replace $$$s_i$$$ either with the character directly before it, or the character directly after it, you will end up with a string with length $$$k-1$$$ upon which you can do an operation again. Therefore, by induction, it's clear that you can keep operating on the string until only one character remains.

However, if you cannot perform any operations, the answer is $$$|s|$$$, because you have not modified the original string.

Therefore, the answer is $$$1$$$ if $$$s_i = s_{i+1}$$$ for some $$$i$$$, or $$$n$$$ otherwise.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

void tc () {
    string str;
    cin >> str;
    for (ll i = 1; i < str.size(); i++) {
        if (str[i-1] == str[i]) {
            cout << "1\n";
            return;
        }
    }
    cout << str.size() << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

The overall idea for both subtasks is that you need to iterate from left to right, and upon each element, pick the operation such that you obtain the smallest value of $$$a_i$$$ that is greater than $$$a_{i-1}$$$.

For C1, you only have two values to consider for each index — $$$b_1-a_i$$$ and $$$a_i$$$. First, set $$$a_1 = min(a_1, b_1-a_1)$$$, then for each subsequent element $$$i$$$, consider the two values $$$b_1-a_i$$$ and $$$a_i$$$. If the smaller of these values is greater than or equal to $$$a_{i-1}$$$, then set $$$a_i$$$ to this value. Otherwise, check the larger value. If this value is less than $$$a_{i-1}$$$, you can straight away output $$$NO$$$ and move onto the next testcase. Otherwise, set $$$a_i$$$ as the larger of the two aforementioned values. Time complexity: $$$\mathcal{O}(n)$$$ per testcase.

For C2, you now have $$$m$$$ values in the array $$$b$$$. Clearly, we now need to consider $$$m+1$$$ different possible values per index of $$$a$$$. Solving this problem in $$$\mathcal{O}(nm)$$$ is clearly too slow. Therefore, we need to employ a different technique.

Note that instead of trying every value, you can sort all the values in $$$m$$$, and then binary search for the minimal value of $$$b_j$$$ such that $$$b_j-a_i >= a_{i-1}$$$. Then, you're left with the original problem, where you either leave $$$a_i$$$ untouched or you set it to $$$b_j - a_i$$$ for this optimal index $$$j$$$ that you found using binary search. Now, by proceeding as before, the problem is solved in $$$\mathcal{O}(n \log m)$$$ time.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
 
const ll INF = ll(1E18)+16;
 
void tc () {
    ll n, m;
    cin >> n >> m;
    vll va(n), vb(m);
    for (ll &i : va) cin >> i;
    for (ll &i : vb) cin >> i;
    sort(vb.begin(), vb.end());
    va.insert(va.begin(), -INF);
    n++;
    for (ll i = 1; i < n; i++) {
        auto it = lower_bound(vb.begin(), vb.end(), -15, [&](ll a, ll _) {
            assert(_ == -15);
            return a-va[i] < va[i-1];
        });
        if (it == vb.end()) continue;
        ll j = *it;
        if (va[i] < va[i-1] && j-va[i] < va[i-1]) continue; // OH MY GOD
        va[i] = min((va[i] < va[i-1] ? INF : va[i]), (j-va[i] < va[i-1] ? INF : j-va[i]));
    }
    cout << (is_sorted(va.begin(), va.end()) ? "YES" : "NO") << '\n';
}
 
int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

It is clear that the score of an array $$$b$$$ of length $$$n$$$ can be expressed as $$$n * b_1 + (n-1) * b_2 + (n-2) * c_2 \dots + 1 * b_n$$$.

Let's solve this problem with $$$n=1$$$ for just one array with $$$m$$$ elements in it. Due to the above fact, it's clear that the optimal way to arrange this array is to sort the elements from largest to smallest.

Now, we come to the issue of combining arrays. Suppose you have two arrays $$$a$$$ and $$$b$$$, both of length m. Is there a nice way of expressing the score of $$$a+b$$$ and the score of $$$b+a$$$ (where $$$+$$$ represents concatenation) in terms of $$$score(a)$$$ and $$$score(b)$$$?

Turns out there is. The score of $$$a+b$$$ is equal to $$$n * sum(a) + score(a) + score(b)$$$. This is because of the following:

$$$score(a+b) = (2n * a_1) + ((2n-1) * a_2) \dots + ((n+1) * a_n) + (n * b_1) \dots + (1 * b_n)$$$

Now, we can clearly replace all the $$$b$$$ terms with $$$score(b)$$$ as follows: $$$score(a+b) = (2n * a_1) + ((2n-1) * a_2) \dots + ((n+1) * a_n) + score(b)$$$

Now, we can take out a factor of $$$n$$$ as follows: $$$score(a+b) = ((n+n) * a_1) + ((n + (n-1)) * a_2) \dots + ((n+1) * a_n) + score(b)$$$ $$$score(a+b) = (n * (a_1 + a_2 + a_3)) + (n * a_1) + ((n-1) * a_2) \dots + (1 * a_n) + score(b)$$$ $$$score(a+b) = (n * sum(a)) + score(a) + score(b)$$$

Therefore, whichever of $$$a$$$ and $$$b$$$ has the larger sum should go first, because then you get a larger overall score. This argument also extends beyond two arrays, so the solution is as follows:

Sort the arrays themselves in terms of their sum, from largest sum to smallest Put together the final array Take the score This score is guaranteed to be maximal.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
 
void tc () {
    ll n, m;
    cin >> n >> m;
    vector <vll> ve(n, vll(m));
    for (vll &ve2 : ve) {
        for (ll &i : ve2) cin >> i;
    }
    vll vsum(n, 0);
    for (ll i = 0; i < n; i++) {
        for (ll j : ve[i]) vsum[i] += j;
    }
    vll th(n);
    iota(th.begin(), th.end(), 0);
    sort(th.begin(), th.end(), [&](ll a, ll b) {
        return vsum[a] > vsum[b];
    });
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ans += vsum[th[i]]*(n-1-i)*m;
    }
    for (vll ve2 : ve) {
        for (ll i = 0; i < m; i++) {
            ans += ve2[i]*(m-i);
        }
    }
    cout << ans << '\n';
}
 
int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Claim 1: It is impossible when $$$k < |n-m|$$$

Proof 1: The entire string will have a balance value greater than $$$k$$$.

Claim 2: It is impossible when $$$k > max(n, m)$$$

Proof 2: The maximal possible balance value of any string with $$$n$$$ ones and $$$m$$$ zeroes is $$$max(m, n)$$$, as it is impossible due to the balance value definition.

To complete the construction, WLOG $$$n>m$$$ (because you can invert the string to get the solution for $$$n<=m$$$. Output $$$k$$$ zeroes, then output alternating ones and zeroes, then output the remaining ones at the end. Note that with this construction, a substring with balance value $$$k$$$ exists (as you can take the first $$$k$$$ numbers), but a substring with balance value $$$>k$$$ does not exist (as taking more of the string cannot increase the balance value).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

void tc () {
    ll n, m, k;
    cin >> n >> m >> k;
    if (abs(n-m) > k || max(n, m) < k) {
        cout << "-1\n";
        return;
    }
    string ans;
    if (n > m) {
        ans = string(k, '0');
        n -= k;
        // assert(n >= 0);
        while (m > n) {
            ans += '1';
            m--;
        }
        // assert(n == m);
        while (n--) {
            ans += (ans.back() == '1' ? "01" : "10");
        }
    } else {
        ans = string(k, '1');
        m -= k;
        // assert(m >= 0);
        while (n > m) {
            ans += '0';
            n--;
        }
        // assert(m == n);
        while (m--) {
            ans += (ans.back() == '1' ? "01" : "10");
        }
    }
    cout << ans << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Assume that a sequence a of length $$$n$$$ contains two types of elements, $$$1$$$ denoting majority and $$$0$$$ denoting "not majority".

Then, if a contains a majority and $$$n \ge 2$$$, the following condition holds. a must contain either $$$[1,1]$$$ or $$$[1,0,1]$$$.

This can be shown by contradiction. It is given that there are $$$k$$$ instances of $$$1$$$ and $$$n-k$$$ instances of $$$0$$$. Then it is known that $$$k>n-k$$$, so $$$2k>n$$$. If a does not contain $$$[1,1]$$$, then it needs a $$$0$$$ between every $$$1$$$. The only way this can happen is when $$$n-k \ge k-1$$$. This means $$$n+1 \ge 2k$$$, but because $$$n<2k \le n+1$$$ the only value $$$k$$$ can take is $$$\frac{n+1}{2}$$$. When this happens, the only valid orientation of $$$a$$$ is $$$[1,0,1,0,\ldots,0,1,0,1]$$$, but still this contains $$$[1,0,1]$$$. Therefore, it definitely contains either $$$[1,1]$$$ or $$$[1,0,1]$$$.

But we can notice, the subarrays $$$[1,1]$$$ and $$$[1,0,1]$$$ already contain the majority $$$1$$$. So due to this, we conclude that the tree containing the pattern $$$[k,k]$$$ or $$$[k,x,k]$$$ for some value $$$k$$$, is an equivalent condition to the tree containing a non-trivial path with majority $$$k$$$.

Checking the existence of $$$[k,k]$$$ and $$$[k,x,k]$$$ in the tree for all k can be done in $$$\mathcal{O}(n)$$$ time, due to $$$\sum{\text{deg}} = 2m = 2(n-1)$$$. The problem has been solved in $$$\mathcal{O}(n)$$$ time.

You can solve this problem using the Auxiliary Tree technique. Formally, the auxiliary tree of $$$k$$$ specified vertices is the tree consisting of the specified vertices and their pairwise lowest common ancestors. It can be shown that such a tree will always have $$$\mathcal{O}(k)$$$ vertices and can be found in $$$\mathcal{O}(k \log n)$$$ time using widely known algorithms.

Observe the fact that, when you transform the value $$$x$$$ into $$$1$$$ and all other values into $$$-1$$$, $$$x$$$ is the majority of the sequence if and only if the transformed sequence has a positive sum. This hints us towards finding the maximum sum of any non-trivial path under the transformed tree. If the maximum sum is found to be positive, then we can determine that there exists a path with $$$x$$$ as its majority.

This subproblem can be solved by running a modified version of Kadane's algorithm, adapted for use on a tree. This adaptation is widely known for the case when the given tree is a binary tree, and it is trivial to modify it for use on any tree while keeping the time complexity to be $$$\mathcal{O}(n)$$$.

The only problem is that solving this for all values is $$$\mathcal{O}(n^2)$$$, so we compress the tree for each value using the Auxiliary Tree technique. By getting the auxiliary tree for the specified vertices, you get the specified vertices and their LCAs. If some vertex is specified, the value on it is transformed into $$$1$$$. Otherwise, the value on it is transformed into $$$-1$$$. Meanwhile, now there are lengths on edges, and an edge with length greater than $$$1$$$ means that there are unspecified vertices compressed in the edge. Therefore, if an edge has length $$$l$$$ which is greater than $$$1$$$, make sure to make a new vertex with value $$$-l+1$$$ in the middle of the edge as it means that $$$l-1$$$ vertices are compressed into the edge.

As there are $$$n$$$ specified vertices in total, finding each auxiliary tree takes $$$\mathcal{O}(n \log n)$$$ time. Solving the rest of the problem for each $$$i$$$ only takes $$$\mathcal{O}(n)$$$ time trivially. Thus, the problem has been solved in $$$\mathcal{O}(n \log n)$$$ time.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 5E5+16;
vll adj[MAXN];

void tc () {
    ll n;
    cin >> n;
    vll ve(n);
    for (ll &i : ve) cin >> i, i--;
    fill(adj, adj+n, vll({}));
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    string ans = string(n, '0');
    for (ll u = 0; u < n; u++) {
        map <ll, ll> mp;
        for (ll v : adj[u]) {
            mp[ve[v]]++;
        }
        mp[ve[u]]++;
        for (auto [a, b] : mp) {
            if (b >= 2) ans[a] = '1';
        }
    }
    cout << ans << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

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

#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)

vector<int> adj[500005];
int a[500005];
int s[500005];
int d[500005];
int t[1000005];
vector<int> v[500005];

int timer = 0;
void dfs(int node, int pa) {
    d[node] = d[pa]+1;
    s[node] = ++timer;
    t[timer] = node;
    v[a[node]].push_back(node);
    for (auto it : adj[node]) {
        if (it == pa)continue;
        dfs(it,node);
        t[++timer] = node;
    }
}

// sparse table
pii spt[1000005][20];

void buildspt(int n) {
    for (int i = 1; i <= 2*n-1; ++i) {
        spt[i][0] = {d[t[i]],i};
    }
    for (int j = 1; (1<<j) <= 2*n-1; ++j) {
        for (int i = 1; i+(1<<j)-1 <= 2*n-1; ++i) {
            spt[i][j] = min(spt[i][j-1],spt[i+(1<<(j-1))][j-1]);
        }
    }
    return;
}

pii qry(int l, int r) {
    int dd = __lg(r-l+1);
    return min(spt[l][dd],spt[r-(1<<dd)+1][dd]);
}

int _lca(int l, int r) {
    return t[qry(s[l],s[r]).s];
}

int dp[500005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        for (int i = 1; i <= n-1; ++i) {
            int u, _v;
            cin >> u >> _v;
            adj[u].push_back(_v);
            adj[_v].push_back(u);
        }
        timer = 0;
        dfs(1,0);
        buildspt(n);
        for (int i = 1; i <= n; ++i) {
            vector<int> v2;
            int ans = -2e9;
            for (auto it : v[i]) {
                dp[it] = 1;
                if (v2.size()) {
                    int lca = _lca(v2.back(),it);
                    while (v2.size() && d[lca] < d[v2.back()]) {
                        int z = v2.back();
                        v2.pop_back();
                        if (v2.empty() || d[v2.back()] < d[lca]) {
                            dp[lca] = (a[lca] == i ? 1 : -1);
                            v2.push_back(lca);
                        }
                        amax(ans,dp[v2.back()]+dp[z]-(d[z]-d[v2.back()]-1));
                        amax(dp[v2.back()],dp[z]+(a[v2.back()] == i ? 1 : -1)-(d[z]-d[v2.back()]-1));
                    }
                }
                v2.push_back(it);
            }
            while ((int)v2.size() > 1) {
                int z = v2.back();
                v2.pop_back();
                amax(ans,dp[v2.back()]+dp[z]-(d[z]-d[v2.back()]-1));
                amax(dp[v2.back()],dp[z]+(a[v2.back()] == i ? 1 : -1)-(d[z]-d[v2.back()]-1));
            }
            cout << (ans > 0);
        } cout << '\n';
        for (int i = 1; i <= n; ++i) {
            adj[i].clear();
            v[i].clear();
        }
    }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Let $$$a_i=x$$$ and $$$a_j=y$$$ for any pair $$$(i,j)$$$ that we count.

First, let's note that since $$$x|lcm(x,y)$$$, we don't need to consider any cases where $$$x$$$ or $$$y$$$ has more than two prime factors. There are three cases we must consider:

1. $$$x$$$ and $$$y$$$ are primes, and $$$x\neq y$$$. Then, $$$lcm(x,y)=x\cdot y$$$ and has two prime factors.

2. $$$x$$$ is a semiprime, and $$$y$$$ is a prime factor of $$$x$$$. Then, $$$lcm(x,y)=x$$$.

3. $$$y$$$ is a semiprime, and $$$y=x$$$.

To count this, let's first factorize each number in the array (either by trial division in $$$O(n\sqrt{a_i})$$$ or $$$O(n\log(n))$$$ sieve precomputation). Let's maintain two maps, one mapping each semiprime present in the array to its number of occurrences, and one mapping each prime present in the array to its number of occurrences. Let $$$cnt[x]$$$ be the number of occurrences of $$$x$$$. Then, we can count each case as follows:

1. Let the total number of primes be $$$P$$$. For each prime $$$p$$$, its contribution will be $$$cnt[p]\cdot(P-cnt[p])$$$. Note that we must divide our result by $$$2$$$ as we would have counted each pair twice.

2. For each semiprime $$$pq$$$, add $$$cnt[pq]\cdot cnt[p]+cnt[pq]\cdot cnt[q]$$$.

3. For each semiprime $$$pq$$$, add $$$cnt[pq]\cdot (cnt[pq]+1)/2$$$.

All of these can be done in $$$O(n\log n)$$$ time. Be sure to not use dictionary, counter, or unordered_map as they can be hacked!

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 2E5+16;
bool isComp[MAXN];
vll ps;
vector <array <ll, 3> > semiPs;

void tc () {
    ll n;
    cin >> n;
    vll ve(n);
    for (ll &i : ve) cin >> i;
    vll freq(n+2, 0);
    for (ll i : ve) freq[i]++;
    ll ans = 0;
    for (auto [v, i, j] : semiPs) {
        if (v > n) break;
        ans += freq[v]*(freq[v]+1)/2;
        if (i != j)
            ans += freq[v]*(freq[i] + freq[j]);
        else {
            ans += freq[v]*freq[i];
        }
    }
    ll acc = 0;
    for (ll i : ps) {
        if (i > n) break;
        ans += freq[i]*acc;
        acc += freq[i];
    }
    cout << ans << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    for (ll i = 2; i < MAXN; i++) {
        if (isComp[i]) continue;
        ps.push_back(i);
        for (ll j = i*i; j < MAXN; j += i) {
            isComp[j] = true;
        }
    }
    for (ll i : ps) {
        for (ll j : ps) {
            if (i*j > MAXN) break;
            if (j < i) continue;
            semiPs.push_back({ i*j, i, j });
        }
    }
    sort(semiPs.begin(), semiPs.end());
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

A brute attempt at a solution would be to go through each non-empty subset of $$${1,2,...,n}$$$ and, for every pair of adjacent indices $$$(i, j)$$$ in the subset, increase $$$ans$$$ if $$$s[i] \neq s[j]$$$ In other words, increase ans every time $$$s[i]$$$ and $$$s[j]$$$ create a new border

This is extremely slow at $$$O(2^n*n)$$$; however, we can notice that every adjacent pair is independent from the rest in the subset. We may ask ourselves: for a fixed $$$(i, j)$$$, how many subsets increase ans through that $$$(i, j)$$$? The conditions are that:

• $$$i$$$ and $$$j$$$ are in the subset
• $$$i$$$ and $$$j$$$ are adjacent in the subset (there's no other included value in between)
• $$$s[i] \neq s[j]$$$

Which leaves us free to choose the prefix and the suffix. $$$(2^{i-1}*2^{n-j})$$$.

An $$$O(n^2)$$$ solution is:

ans := 2^n-1
for j (1<=j<=n):
    for i (1<=i<j):
        if (s[i] != s[j])
            ans += 2^(i-1)*2^(n-j)

The rest of the solution will try to optimize how to compute that sum, and then how to maintain the answer through updates. We may notice we can pull out the $$$2^{n-j}$$$ factor and rewrite the loops as:

ans := 2^n-1
for j (1<=j<=n):
    sumI := 0
    for i (1<=i<j):
        if (s[i] != s[j])
            sumI += 2^(i-1)
    ans += sumI*2^(n-j)

Since the second for loop only cares about what $$$s[j]$$$ is (nothing else about $$$j$$$), we can again easily optimize it as:

ans := 2^n-1
sumI := [0, 0]
for j (1<=j<=n):
    ans += sumI[s[j]]*2^(n-j)
    sumI[s[j]\oplus1] += 2^(j-1)

In other words, we don't need to recalculate $$$sumI$$$ each new $$$j$$$. Instead, we can maintain its $$$2$$$ possible values ($$$s[j]=0, s[j]=1$$$) as we increase $$$j$$$ (since $$$sumI$$$ cares about ($$$1\leq i<j$$$))

We can run this $$$O(n)$$$ solution once before any updates, but not after each update because $$$O(q*n)$$$ is too slow. Instead, we can make the minimal adjustments needed to maintain ans correctly. Let's call the toggled index $$$k$$$: How much does $$$s[k]$$$ contribute to ans in the first place? We can partition $$$s[k]$$$'s contribution to the answer in $$$2$$$ cases: - When $$$j=k$$$, $$$ans += sumI[s[k]]*2^{n-k}$$$ - After $$$sumI[s[k]\oplus1] += 2^{k-1}$$$, every time $$$sumI[s[k]\oplus 1]$$$ is used to increase ans

As for the first case, we can calculate the value of $$$sumI[s[k]]$$$ at $$$j=k$$$ using the sum of $$$2^{i-1}$$$ for $$$i < k$$$ and $$$s[i]=s[k]\oplus1$$$. As for the second case, it's only slightly trickier, but along the same general idea. It can be calculated using the sum of $$$2^{n-j}$$$ for $$$j > k$$$ and $$$s[j]=s[k]\oplus 1$$$.

Fenwick (or segment) tree solves both cases, which are essentially dynamically calculating range sums on an array. Since for both cases we may consider when $$$s[k]=0$$$ or $$$s[k]=1$$$, a total of $$$4$$$ different fenwick trees will be needed. $$$(2^{i-1}$$$ when $$$s[i]=0, 0$$$ otherwise); ($$$2^{i-1}$$$ when $$$s[i]=1, 0$$$ otherwise); $$$(2^{n-j}$$$ when $$$s[j]=0, 0$$$ otherwise); $$$(2^{n-j}$$$ when $$$s[j]=1, 0$$$ otherwise)

The procedure is thus: before toggling a bit, subtract its contribution from ans. After toggling the bit, add its new contribution to ans. Also, update the $$$4$$$ fenwick trees accordingly. This correctly maintains ans in $$$O(log(n))$$$ per update.

So, the final complexity is $$$O(n+q*log(n))$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 2E5+16, MOD = 998244353;
ll pw2[MAXN];

struct SegTree {
    vll tree;
    ll n;

    SegTree (ll n): tree(2*n, 0), n(n) {}

    void update (ll id, ll val) {
        for (tree[id += n] = val; id > 1; id >>= 1)
            tree[id>>1] = (tree[id] + tree[id^1]) % MOD;
    }

    ll query (ll ql, ll qr) {
        ll ans = 0;
        for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql&1) (ans += tree[ql++]) %= MOD;
            if (qr&1) (ans += tree[--qr]) %= MOD;
        }
        return ans;
    }
};

void tc () {
    string str;
    cin >> str;
    ll n = str.size();
    SegTree stFreq0(n), stFreq1(n), st0(n), st1(n);
    for (ll i = 0; i < n; i++) {
        (str[i] == '0' ? stFreq0 : stFreq1).update(i, pw2[n-1-i]);
        (str[i] == '0' ? st0 : st1).update(i, pw2[i]);
    }
    ll ans = pw2[n]-1;
    {ll acc0 = 0, acc1 = 0;
    for (ll i = 0; i < n; i++) {
        (ans += (str[i] == '0' ? acc1 : acc0)*pw2[n-1-i]) %= MOD;
        ((str[i] == '0' ? acc0 : acc1) += pw2[i]) %= MOD;
    }}
    ll Q;
    cin >> Q;
    while (Q--) {
        ll at;
        cin >> at;
        at--;
        (ans -= (str[at] == '0' ? st1 : st0).query(0, at-1)*pw2[n-1-at]) %= MOD;
        (ans -= (str[at] == '0' ? stFreq1 : stFreq0).query(at+1, n-1)*pw2[at]) %= MOD;
        (ans += MOD) %= MOD;
        (str[at] == '0' ? stFreq0 : stFreq1).update(at, 0);
        (str[at] == '0' ? st0 : st1).update(at, 0);
        str[at] = (str[at] == '0' ? '1' : '0');
        (str[at] == '0' ? stFreq0 : stFreq1).update(at, pw2[n-1-at]);
        (str[at] == '0' ? st0 : st1).update(at, pw2[at]);
        (ans += (str[at] == '0' ? st1 : st0).query(0, at-1)*pw2[n-1-at]) %= MOD;
        (ans += (str[at] == '0' ? stFreq1 : stFreq0).query(at+1, n-1)*pw2[at]) %= MOD;
        cout << ans << ' ';
    }
    cout << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    pw2[0] = 1;
    for (ll i = 1; i < MAXN; i++) pw2[i] = pw2[i-1]*2 % MOD;
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve