Notice that if $$$s$$$ starts with a $$$1$$$ we must move the entire string $$$s$$$ to $$$t$$$ at some point. Also Notice that if we perform the operation, the total number of occurrences of $$$01$$$ and $$$10$$$ across both strings can only decrease by one. This gives us an upper bound on the answer being the number of occurrences of $$$01$$$ and $$$10$$$ in $$$s$$$ adding one to this if it starts with the character $$$1$$$.

Now the following construction uses the same number of moves as the upper bound (thus showing it is the minimum number of moves): If $$$s$$$ begins with $$$1$$$ then select the entire string $$$s$$$ and move it to $$$t$$$. Then repeatedly find the first character in $$$s$$$ or $$$t$$$ which is not equal to the character before it (note under this construction such an index can only exist in one string at a time) and selected the suffix starting from this character and move it to the other string. During this construction some prefix of $$$s$$$ will contain $$$0$$$s and some prefix of $$$t$$$ will contain $$$0$$$s, so after each move the total number of $$$01$$$ and $$$10$$$ will decrease.

So the answer to this problem will be the number of $$$01$$$ and $$$10$$$ in $$$s$$$ adding one to the answer if it starts with $$$1$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (s[i] != s[i + 1]) ans++;
    }

    if (s[0] == '1') ans++;
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

The first thing to notice is that if we remove an element from $$$a$$$ then our score will never increase. Because removing one element will cause $$$|a|$$$ to decrease by $$$1$$$ and $$$\mathrm{distinct}(a)$$$ will decrease by at most $$$1$$$ and so the $$$|a|$$$ — $$$\mathrm{distinct}(a)$$$ will never increase. This means that we should be trying to removing the longest subarray which does not decrease our score.

We can see that removing any element which only occurs once in $$$a$$$ will never decrease our score, and that removing any element which occurs more than once will always decrease our score. Thus we should try to find the longest subarray of elements which only have $$$1$$$ occurrence in $$$a$$$ and this will be the answer. This can be calculated with a single loop in $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> freq(n + 1);
    for (int x : a) freq[x]++;

    vector<int> len(n + 1);
    len[0] = freq[a[0]] == 1;
    for (int i = 1; i < n; i++)
        if (freq[a[i]] == 1)
            len[i] = len[i - 1] + 1;
    
    int mx = *max_element(len.begin(), len.end());
    if (mx == 0){
        cout << "0\n";
        return;
    }

    for (int i = 0; i < n; i++){
        if (len[i] == mx){
            cout << i - len[i] + 2 << " " << i + 1 << "\n";
            return;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

First see that at any point we should either remove the leftmost positive element or the rightmost negative element, as if we were to take a positive element that is not the leftmost one we could have just taken the leftmost one first and had a higher score, a similar argument can be made for taking the rightmost negative element. Now if you do either of these moves some number of times you will always take some prefix of positive numbers and then the remaining suffix of negative numbers, and so to calculate the answer we only need to check all $$$n + 1$$$ ways to split the array into a prefix and suffix and take the maximum across them all which is easy to do in $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a)
        cin >> x;

    vector<ll> pre(n), suf(n);
    if (a[0] > 0)
        pre[0] = a[0];

    for (int i = 1; i < n; i++){
        pre[i] = pre[i - 1];
        if (a[i] > 0)
            pre[i] += a[i];
    }

    if (a[n - 1] < 0)
        suf[n - 1] = -a[n - 1];
    
    for (int i = n - 2; i >= 0; i--){
        suf[i] = suf[i + 1];
        if (a[i] < 0)
            suf[i] -= a[i];
    }

    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, pre[i] + suf[i]);
    
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

First notice that if we are unable to eat the next slime then this slime must have had a $$$\mathrm{msb}$$$ (most significant bit) at least as large as the current value of $$$x$$$. Subsequently this means that if a slime has a $$$\mathrm{msb}$$$ strictly less than $$$x$$$ we can always eat it.

Now see that if we eat a slime with lower $$$\mathrm{msb}$$$ than $$$x$$$ then the $$$\mathrm{msb}$$$ of $$$x$$$ will never decrease and that if we eat a slime with equal $$$\mathrm{msb}$$$ then $$$\mathrm{msb}$$$ of $$$x$$$ will decrease, this inspires us to do the following:

at any point we should eat as many slimes as we can to the left that have smaller $$$\mathrm{msb}$$$ (to calculate the new value of $$$x$$$ after doing this we can just do any range xor query such as prefix sums), after this the next slime will always have $$$\mathrm{msb}$$$ greater than or equal to $$$x$$$ and so we will either not be able to eat it or we will eat it $$$\mathrm{msb}$$$ of $$$x$$$ will decrease. Because the $$$\mathrm{msb}$$$ will always decrease after every operation we will only need to do this operation at most $$$log(x)$$$ times!

And so we should try find some way to calculate fast the first slime to our left with $$$\mathrm{msb}$$$ greater than or equal to the current $$$\mathrm{msb}$$$ of $$$x$$$. There are many ways to do this but I would say the cleanest way is to use prefix sums, store for each $$$i, j$$$ where $$$1 \le i \le n, 1 \le j \le log(W)$$$ (where $$$W$$$ is the max value of $$$w_i$$$ and $$$x$$$), the greatest index before it which has $$$\mathrm{msb}$$$ greater than or equal to $$$j$$$ call this $$$\mathrm{pre}_{i, j}$$$

Now we can update it as follows:

• if $$$\mathrm{msb}(w_i) < j$$$ then $$$\mathrm{pre}_{i, j} = \mathrm{pre}_{i - 1, j}$$$

• else $$$\mathrm{pre}_{i, j} = i$$$

And so the final complexity is $$$O((n + q)log(W))$$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int W = 30;

void solve(){
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int &x : a) cin >> x;
    
    vector<int> pre(n + 1);
    pre[0] = a[0];
    for (int i = 1; i < n; i++){
        pre[i] = pre[i - 1] ^a[i];
    }

    vector<array<int, W>> last(n);
    for (int i = 0; i < n; i++){
            fill(last[i].begin(), last[i].end(), 0);
        if (i > 0) last[i] = last[i - 1];
        last[i][__lg(a[i])] = i;

        for (int j = W - 2; j >= 0; j--){
            last[i][j] = max(last[i][j], last[i][j + 1]);
        }
    }

    while (q--) {
        int x;
        cin >> x;

        int idx = n - 1;
        while (idx >= 0 && x > 0){
            int msb = __lg(x);

            int nxt = last[idx][msb];
            x ^= pre[idx] ^ pre[nxt];
            idx = nxt;
            if (nxt == -1 || a[nxt] > x) break;

            x ^= a[nxt];
            idx--;
        }

        cout << n - idx - 1 << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

The first thing to notice is that the first column of sand will be identical to $$$c$$$ after sorting. This means that it must be true that $$$c' = c$$$.

Now that we know $$$c' = c$$$ we need to find how many ways we can re-arrange $$$p$$$ such that the sand layout is the same. Something we can notice is that $$$p'$$$ must be able to obtainable from $$$p$$$ by only swapping values of the same colour. This is true because if we remove all sand blocks that are not of any specific colour (i.e. keeping only one colour), then by examining the new sand layout we can find what the values of the colour we didn't remove are.

Now lets isolate a single colour and try to find the number of ways we can arrange it. One thing we can notice is that we can swap an arbitrary $$$p_i$$$ and $$$p_j$$$ without changing the final sand layout if and only if every number of different colour between $$$i$$$ and $$$j$$$ is strictly less than both $$$p_i$$$ and $$$p_j$$$. After staring at this operation enough you will see that each number in $$$p_i$$$ has a certain range of positions it can take, this range is the unique range that covers all the positions $$$p_i$$$ can swap with in one move without changing the order.

Now that we have some ranges we just need to place one number in each range such that no two numbers have the same value. Because it is a permutation two ranges will either not intersect, or one will contain the other. This means that the ranges form some kind of tree, and we can solve the problem by fixing a value in a range in reverse order of size.

There is actually no need to build the tree, and instead we can just iterate in reverse order of size use dsu to merge each position with everything in its range and multiply the answer by the size of the component, then decrease the size of the component by $$$1$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://codeforces.me/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

template <class T> struct SegTree{
    vector<T> seg;
    int n;
    const T ID = 0;
    
    T cmb(T a, T b){
        return max(a, b);
    }
    
    SegTree(int _n){
        n = 1;
        while (n < _n) n *= 2;
        seg.assign(2 * n + 1, ID);
    }
    
    void set(int pos, T val){
        seg[pos + n] = val;
    }
    
    void build(){
        for (int i = n - 1; i >= 1; i--) seg[i] = cmb(seg[2 * i], seg[2 * i + 1]);
    }
    
    void upd(int v, int tl, int tr, int pos, T val){
        if (tl == tr){
            seg[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) upd(2 * v, tl, tm, pos, val);
            else upd(2 * v + 1, tm + 1, tr, pos, val);
            seg[v] = cmb(seg[2 * v], seg[2 * v + 1]);
        }
    }
    
    void upd(int pos, T val){
        upd(1, 0, n - 1, pos, val);
    }
    
    T query(int v, int tl, int tr, int l, int r){
        if (l > r) return ID;
        if (l == tl && r == tr) return seg[v];
        int tm = (tl + tr) / 2;
        T res = query(2 * v, tl, tm, l, min(tm, r));
        res = cmb(res, query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        return res;
    }
    
    T query(int l, int r){
        return query(1, 0, n - 1, l, r);
    }
};

struct DSU{
    vector<int> p, sz, used, mn, mx;
    
    DSU(int n){
        p.assign(n, 0);
        sz.assign(n, 1);
        used.assign(n, 0);
        mx.assign(n, 0);
        mn.assign(n, 0);

        for (int i = 0; i < n; i++) p[i] = i;
    }
    
    int find(int u){
        if (p[u] == u) return u;
        p[u] = find(p[u]);
        return p[u];
    }
    
    void unite(int u, int v){
        u = find(u);
        v = find(v);
        if (u == v) return;
        
        if (sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        used[u] += used[v];
        mn[u] = min(mn[u], mn[v]);
        mx[u] = max(mx[u], mx[v]);
    }
    
    bool same(int u, int v){
        return find(u) == find(v);
    }
    
    int size(int u){
        u = find(u);
        return sz[u];
    }
};

void solve(){
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    vector<vector<int>> col(n + 1);
    for (int i = 0; i < n; i++){
        col[b[i]].push_back(i);
    }

    vector<vector<int>> ord(n + 1);

    for (int i = 0; i <= n; i++){
        ord[i] = col[i];
        sort(ord[i].begin(), ord[i].end(), [&](int x, int y) -> bool{
            return a[x] < a[y];
        });
    }

    SegTree<int> seg(n);
    for (int i = 0; i < n; i++){
        seg.set(i, a[i]);
    } seg.build();

    mint ans = 1;
    DSU dsu(n);
    for (int i = 0; i <= n; i++){
        for (int j = 0; j < col[i].size(); j++){
            dsu.mn[col[i][j]] = j;
            dsu.mx[col[i][j]] = j;
        }
    }

    for (int i = 0; i <= n; i++){
        for (int x : ord[i]) seg.upd(x, 0);

        for (int x : ord[i]){
            int idx = lower_bound(col[i].begin(), col[i].end(), x) - col[i].begin();
            for (int j = idx + 1; j < col[i].size(); j++){
                if (seg.query(x, col[i][j]) >= a[x]) break;

                dsu.unite(x, col[i][j]);
                j = dsu.mx[dsu.find(x)];
            }

            for (int j = idx - 1; j >= 0; j--){
                if (seg.query(col[i][j], x) >= a[x]) break;

                dsu.unite(x, col[i][j]);
                j = dsu.mn[dsu.find(x)];
            }

            int u = dsu.find(x);
            ans *= dsu.size(u) - dsu.used[u];
            dsu.used[u]++;
        }

        for (int x : ord[i]) seg.upd(x, a[x]);
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}