If there is a subarray containing $$$k - 1$$$ zeros, then the next element cannot be prevented from being hit. So any time we see $$$k - 1$$$ zeros follwed by a one then the one must be protected.

From Hint 1, lets protect every $$$\mathtt{1}$$$ that fits the pattern. Furthermore we should always protect the first $$$1$$$ in the string so lets do that. It turns out that this is all that we need to do, to prove this think inductively: every element that is not protected will always have a $$$\mathtt{1}$$$ in the last $$$k - 1$$$ elements and so it will be unchanged. So to solve the problem we can check the distance between each consecutive $$$\mathtt{1}$$$, if the gap is at least $$$k$$$ then add $$$1$$$ to the answer. Final time complexity $$$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, k;
    cin >> n >> k;

    string s;
    cin >> s;

    int ans = 0;
    int last = -1e9;
    for (int i = 0; i < n; i++){
        if (s[i] == '1' && i - last >= k)
            ans++;
        if (s[i] == '1')
            last = i;
    }

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

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

https://youtu.be/5Xku9F6Rbqo

You want odd-indexed values to be small, and even-indexed values to be large. In other words, it is beneficial to apply operation 1 on even indices, and operation 2 on odd indices.

Since operation 1 is free, you may as well apply it to every even index. None of the operations can increase a prefix max, so you can't possibly do any better than just applying operation 1 immediately to every even index.

Let's first apply operation 1 to every even index. Now, we can't further increase any even-indexed values, so we just need to decrease odd-indexed values by using operation 2. All of the odd indices are independent from one another, so let's just consider each one separately. For a fixed odd index $$$i$$$, the number of instances of operation 2 needed to make it smaller than $$$a_{i-1}$$$ and $$$a_{i+1}$$$ is given by $$$\max(0, a_i - \min(a_{i-1}, a_{i+1}) + 1)$$$. (Be careful with indices $$$1$$$ and $$$n$$$ as well; you can treat the out of bounds values as being arbitrarily large, or just take care of them separately.) Now, we sum this value, across all odd indices $$$i$$$.

#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> pre(n);
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
        pre[i] = max(pre[i - 1], a[i]);

    ll ans = 0;
    for (int i = 0; i < n; i += 2){
        int dif = -1;
        if (i > 0)
            dif = max(dif, a[i] - pre[i - 1]);

        if (i < n - 1)
            dif = max(dif, a[i] - pre[i + 1]);

        ans += dif + 1;
    }

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

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

You can make an element divisible by $$$2$$$ in $$$1$$$ move.

Can you check if the answer is $$$0$$$ or if the answer is $$$1$$$?

By result of Hint 1, the answer cannot be more than $$$2$$$, as we can always pick two elements and make them both divisible by $$$2$$$ using at most $$$1$$$ move on each. So now we just need to check if the answer is $$$0$$$ or $$$1$$$.

To check if the answer is $$$0$$$, we need to determine if there is a common divisor between two elements. Note that it is sufficient to only check if there is a common prime divisor. So, for each element, iterate through all its prime divisors and check if there is another element with the same prime divisor.

To check if the answer is $$$1$$$, we can do the same as $$$0$$$. This time, for each $$$i$$$ we check if $$$a_i + 1$$$ shares a common prime divisor with another element.

Prime divisors can be pre-calculated with the Sieve of Eratosthenes in $$$O(N\log\log N)$$$ where $$$N$$$ is the maximum possible element (so $$$2 \cdot 10^5$$$ for this problem). However, the constraints are lenient enough to allow $$$O(n\sqrt{N})$$$ as well.

The final complexity comes out to $$$O(n\omega(N) + N\log\log N)$$$, where $$$\omega(x)$$$ is used to denote the number of distinct prime divisors of $$$x$$$. Note that the editorial implementation is $$$O(n\omega(N)\log(n\omega(N)) + N\log\log N)$$$ due to use of c++ std::map for the sake of readability.

#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 N = 2e5 + 10;
vector<vector<int>> pfac(N + 1);

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

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

    int ans = 2;
    map<int, int> cnt;
    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]]){
            if (cnt[x] > 0)
                ans = 0;
            cnt[x]++;
        }
    }

    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]])
            cnt[x]--;

        for (int x : pfac[a[i] + 1]){
            if (cnt[x] > 0)
                ans= min(ans, 1);
        }

        for (int x : pfac[a[i]])
            cnt[x]++;
    }

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 2; i <= N; i++){
        if (!pfac[i].empty())
            continue;

        for (int j = i; j <= N; j += i)
            pfac[j].push_back(i);
    }
    
    int t;
    cin >> t;
    while (t--) solve();
}

Solve the easy version.

We can always make two elements $$$i, j$$$ divisible by $$$2$$$ with no more than $$$b_i + b_j$$$ cost.

By hint 2, we should never perform more than one operation on more than one element.

Lets say we are trying to make the elements at index $$$i, j$$$ have a common divisor. From hint 2 and 3 there are only two cases to consider here. The first case where we make $$$0$$$ or $$$1$$$ operation on both $$$i$$$ and $$$j$$$. Or the second case where we make more than $$$1$$$ operation on a single element. We should never do more than $$$1$$$ operation on both elements because we can always do better by making both elements divisible by $$$2$$$.

So now to solve the problem on the entire array, we should try to solve both of the cases. For convenience lets reorder the elements so that $$$b$$$ is in sorted order.

The first case can be solve almost identically to the easy version of the problem. We can always do at least as good as $$$b_1 + b_2$$$, the only other possibility is only making one operation. To do this we just check if $$$a_i + 1$$$ has a common prime divisor with another element.

The second case is the more tricky case, we need to check the optimal way to make more than one operations for each element, and it is probably the crux of the problem. The key thing to notice is that we actually do not need to check every element, in fact we can only check the element with the smallest value of $$$b_i$$$ ($$$b_1$$$ because $$$b$$$ is sorted). To prove this lets argue by contradiction, supposed we made $$$k$$$ ($$$k \ge 2$$$) operations on element $$$x$$$ ($$$x \ge 2$$$). The total cost of this is $$$k \cdot b_x$$$, we know from hint 2 that we can do $$$b_1 + b_x$$$ or better, since $$$b_1$$$ is the smallest element we know that $$$b_1 + b_x \le k \cdot b_x$$$ and thus we do not need to consider this case!

So now we need to quickly check what is the optimal way to use multiple operations on the first element. To do this we can iterate through all the prime divisors of the other elements and determine the minimum number of operations to make $$$a_1$$$ divisible by it.

The final time complexity comes out to $$$O(n\omega(N) + N\log\log N)$$$, where $$$\omega(x)$$$ is used to denote the number of distinct prime divisors of $$$x$$$. Note that the editorial implementation is $$$O(n\omega(N)\log(n\omega(N)) + N\log\log N)$$$ due to use of c++ std::map for the sake of readability.

#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 N = 2e5 + 10;
vector<vector<int>> pfac(N + 1);

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<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) -> bool{
        return b[x] < b[y];
    });

    int ans = b[ord[0]] + b[ord[1]];
    map<int, int> cnt;
    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]]){
            if (cnt[x] > 0)
                ans = 0;
            cnt[x]++;
        }
    }

    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]])
            cnt[x]--;

        for (int x : pfac[a[i] + 1]){
            if (cnt[x] > 0)
                ans= min(ans, b[i]);
        }

        for (int x : pfac[a[i]])
            cnt[x]++;
    }

    int idx = ord[0];
    vector<int> check;
    for (int i = 0; i < n; i++){
        if (i == idx)
            continue;

        for (int x : pfac[a[i]])
            check.push_back(x);
    }

    for (int x : check){
        int times = x - (a[idx] % x);
        if (times == x)
            times = 0;

        ans = min(1LL * ans, 1LL * times * b[idx]);
    }

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 2; i <= N; i++){
        if (!pfac[i].empty())
            continue;

        for (int j = i; j <= N; j += i)
            pfac[j].push_back(i);
    }
    
    int t;
    cin >> t;
    while (t--) solve();
}

Destroying a leaf will never split the tree.

Trees are bipartite. In particular, you can root the tree arbitrarily, then partition vertices into those with even depth and those with odd depth. All edges connect an even depth vertex to an odd depth vertex.

We would like to decrease the size of the tree by one vertex using no more than three moves. To do so, we will pick an arbitrary leaf $$$v$$$ and destroy it. However, we must make sure that we do not destroy the vertex we are standing on, and that we do not have two consecutive instances of the second instruction. To do so, let's root the tree arbitrarily, and color vertices with even depth red and vertices with odd depth blue. We maintain the color of the vertex we are standing on, noting that every instance of instruction 1 flips the color. Now, if we are standing on the same color as $$$v$$$, we apply operation 1 once. Otherwise, we apply operation 1 twice. Thus, we are not currently standing on leaf $$$v$$$, so now we can destroy $$$v$$$. Since we applied at least one instance of instruction 1, we do not have two consecutive instances of instruction 2. By iterating this process until the only remaining vertex is vertex $$$n$$$, we guarantee that we have reached vertex $$$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<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dep(n), par(n), ch(n);
    auto dfs = [&](auto self, int c, int p) -> void{
        if (p != -1)
            dep[c] = dep[p] + 1;
        par[c] = p;
        
        for (int x : g[c]){
            if (x == p) continue;
            
            self(self, x, c);
            ch[c]++;
        }
    };
    dfs(dfs, n - 1, -1);

    array<vector<int>, 2> leaves;
    leaves[0];

    for (int i = 0; i < n; i++){
        if (ch[i] == 0)
            leaves[dep[i] & 1].push_back(i);
    }

    vector<array<int, 2>> ans;
    int col = dep[0] & 1;
    for (int i = 0; i < n - 1; i++){
        if (leaves[col ^ 1].empty()){
            ans.push_back({1, -1});
            col ^= 1;
        }

        int nxt = leaves[col ^ 1].back();
        leaves[col ^ 1].pop_back();
        ans.push_back({2, nxt});

        int p = par[nxt];
        ch[p]--;
        if (ch[p] == 0)
            leaves[dep[p] & 1].push_back(p);

        ans.push_back({1, -1});
        col ^= 1;
    }

    cout << ans.size() << "\n";
    for (auto [x, y] : ans){
        if (x == 1)
            cout << "1\n";
        else
            cout << "2 " << y + 1 << "\n";
    }
}

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

Can you implement the checker?

Without loss of generality, assume the array is sorted. Let's fix $$$x = 2y+1$$$, and let's also fix the median of a given operation $$$a_i$$$, for some $$$y+1 \leq i\leq n-y$$$. Now, we see that the best subsequence to choose is $$$a_1, a_2, \dots, a_y, a_i, a_{i+1}, \dots, a_{i+y}$$$, because we must choose $$$y$$$ values to the left of $$$a_i$$$ and $$$y$$$ values to the right of $$$a_i$$$, and we would like to change the smallest values possible.

Suppose you have applied one operation with median $$$a_i$$$ and another operation with median $$$a_j$$$, for $$$y+1 \leq i \lt j \leq n-y$$$. Now, you have increased up to $$$\min(2y, j-1)$$$ of the smallest values to either $$$a_i$$$ or $$$a_j$$$, since you can increase up to $$$y$$$ values smaller than the median each operation. However, you have also decreased $$$y$$$ values after $$$a_i$$$, and $$$y$$$ values after $$$a_j$$$. Instead, you might as well have just applied two operations with median $$$a_j$$$, which allows you to increase $$$\min(2y, j-1)$$$ of the smallest values to $$$a_j$$$, and decrease only the $$$y$$$ values after $$$a_j$$$. Therefore, there exists some optimal sequence of operations where we use the same median across all operations.

By the result of Hint 2, there exists some optimal sequence of operations where we use the same median across all operations. Let's fix the median at $$$a_i$$$. Now, if we choose $$$x = 2y+1$$$ for some $$$0\leq y \leq \min(i-1, n-i)$$$, we are able to increase the values of $$$a_1, a_2, \dots, a_{\min(ky, i-1)}$$$ to $$$a_i$$$, but we must also decrease the values of $$$a_{i+1}, a_{i+2}, \dots, a_{i+y}$$$ to $$$a_i$$$.

The benefits of increasing $$$y$$$ are that we can increase more values, but notice that these benefits are getting less and less, because we are increasing values that are already larger. For example, the benefit of increasing $$$y$$$ from $$$0$$$ to $$$1$$$ is that now we can increase the values $$$a_1, a_2, \dots, a_k$$$, but the benefit from increasing $$$y$$$ from $$$1$$$ to $$$2$$$ is that now we can increase the values $$$a_{k+1}, a_{k+2}, \dots, a_{2k}$$$; increasing $$$y$$$ from $$$1$$$ to $$$2$$$ is not as beneficial as increasing $$$y$$$ from $$$0$$$ to $$$1$$$, because the values we are increasing are already relatively big. (There's a small case to think about, when $$$ky$$$ first exceeds $$$i-1$$$, but note that the number of values you can increase is also monotonically decreasing, so this doesn't cause any issues.) The same reasoning goes for the losses. The losses of increasing $$$y$$$ are that we are forced to decrease more values, and these losses are getting greater and greater. If we increase $$$y$$$ from $$$0$$$ to $$$1$$$, we are only forced to decrease $$$a_{i+1}$$$, but if we increase $$$y$$$ from $$$1$$$ to $$$2$$$, we now have to decrease $$$a_{i+2}$$$, which is worse because $$$a_{i+2}$$$ is relatively big. In other words, our net gains (that is, the benefits minus the losses) are monotonically decreasing.

We want to keep incrementing $$$y$$$ as long as our net gains are positive, then stop incrementing $$$y$$$ once our net gains become negative. Since our net gains are monotonically decreasing, we can binary search for this point. (Alternative solutions might use ternary search instead.) So we iterate over all choices of $$$i$$$, then binary search for the optimal choice of $$$y$$$, which in total takes $$$O(n\log{n})$$$ time. Note that all computations can be done quickly with prefix sums.

#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, k;
    cin >> n >> k;

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

    sort(a.begin(), a.end());

    vector<ll> pre(n);
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + a[i];

    ll ans = pre[n - 1];

    auto query = [&](int l, int r) -> ll{
        ll res = pre[r];
        if (l > 0)
            res -= pre[l - 1];
        return res;
    };

    for (int i = 0; i < n; i++){
        int l = 1, r = min(i, n - i - 1) + 1;
        while (l < r){
            int mid = (l + r) / 2;
            
            int left = min(1LL * (mid - 1) * k, 1LL * i);
            int right = min(1LL * mid * k - 1, 1LL * i);
            ll cost = query(left, right) + a[i + mid];
            if (cost <= 1LL * a[i] * (right - left + 1 + 1))
                l = mid + 1;
            else
                r = mid;
        }
        l--;
        if (l == 0)
            continue;

        int right = min(1LL * l * k - 1, 1LL * i);
        ll len = right + 1 + l;
        ll cost = len * a[i] - (query(0, right) + query(i + 1, i + l));
        ans = max(ans, pre[n - 1] + cost);
    }

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

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

For every valid permutation we can always determine the index $$$k$$$ used as the split in the riffle shuffle operation, unless it is the sorted permutation.

Find the number of riffle shuffles for each split.

Lets prove Hint 1. For a valid permutation $$$q$$$, consider the first $$$k$$$ such that $$$k$$$ appers after $$$k + 1$$$ in $$$q$$$, if $$$q$$$ is a riffle shuffle of $$$[1, 2, \ldots, n]$$$ then we know that $$$k$$$ must be the split used. The only permutation where such a item does not exist is the one where the permutation is already sorted.

Now lets try finding the number of solutions for a specific split point $$$k$$$ in sub-quadratic time. We can think of it like this, colour all the numbers less than or equal to $$$k$$$ in blue and the elements bigger than $$$k$$$ in red. Now when we replace all $$$-1$$$ in $$$p$$$ the following must be true after, for each blue element $$$x$$$ exactly $$$x$$$ elements are blue in its prefix and for each red element $$$x$$$ exactly $$$x - k$$$ elements are red in its prefix. So now we just need to count the number of ways to insert red and blue elements so that this condition is satisfied. To find this iterate over each index that is not $$$-1$$$ and insert the number of elements of its colour that it demands and fill the remaining elements in its prefix with the other colour. This will have worst case $$$O(n)$$$ run time if we can calculate the required binomial coefficients in $$$O(1)$$$ which can be done by pre-calculating factorials.

So we can just iterate over each split and sum in $$$O(n^2)$$$ making sure to remember that we might overcount the sorted permutation.

#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://mirror.codeforces.com/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>;

struct Combi{
    vector<mint> _fac, _ifac;
    int n;
    
    Combi() {
        n = 1;
        _fac.assign(n + 1, 1);
        _ifac.assign(n + 1, 1);
    }
    
    void check_size(int m){
        int need = n;
        while (need < m) need *= 2;
        m = need;
        if (m <= n) return;
        
        _fac.resize(m + 1);
        _ifac.resize(m + 1);
        for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1];
        
        _ifac[m] = _fac[m].inv();
        for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
        n = m;
    }
    
    mint fac(int m){
        check_size(m);
        return _fac[m];
    }
    
    mint ifac(int m){
        check_size(m);
        return _ifac[m];
    }
    
    mint ncr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r) * ifac(r);
    }
    
    mint npr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r);
    }
} comb;

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

    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
        if (x != -1)
            x--;
    }

    mint ans = 0;

    for (int i = 0; i < n - 1; i++){
        mint res = 1;
        int spaces = 0;
        int less = -1;
        int more = i;
        for (int j = 0; j < n; j++){
            if (a[j] == -1){
                spaces++;
                continue;
            }

            if (a[j] <= i){
                int need = a[j] - less - 1;
                res *= comb.ncr(spaces, need);
                more += spaces - need;
                less = a[j];

            }

            if (a[j] > i){
                int need = a[j] - more - 1;
                res *= comb.ncr(spaces, need);
                less += spaces - need;
                more = a[j];
            }

            spaces = 0;
        }

        res *= comb.ncr(spaces, i - less);

        ans += res;
    }

    bool sorted = true;
    for (int i = 0; i < n; i++){
        if (a[i] != i && a[i] != -1)
            sorted = false;
    }

    if (sorted)
        ans -= n - 2;
    cout << ans << "\n";
}

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

Solve the easy version.

If $$$p_i \lt i$$$ we know that $$$p_i$$$ must belong to the left side of the split, similarly if $$$p_i \gt i$$$ we know that $$$p_i$$$ must belong to the right side of the split.

If a permutation p is a riffle shuffle of $$$[1,2,\ldots,n]$$$, then it will have three regions described by two integers $$$l, r$$$ as follows:

• a prefix where for all $$$i$$$ ($$$1 \le i \le l$$$) we have $$$p_i = i$$$.

• a suffix where for all $$$i$$$ ($$$r \le i \le n$$$) we have $$$p_i = i$$$.

• a middle region where for all $$$i$$$ ($$$l \lt i \lt r$$$) we have $$$p_i \ne i$$$.

See that the first region will all belong to the left side of the split, and the last region will all belong to the right side of the split. Additionally, we can deduce the side of the entire middle region from Step 2. There is a single edge case to this where $$$p$$$ is the sorted permutation.

Suppose there is an index $$$i$$$ where $$$a_i \ne i$$$ and $$$a_i \ne -1$$$, or in other words, the sorted permutation is not valid. In this case, from Step 3, we can deduce the side of every element $$$i$$$ where $$$a_i \ne -1$$$.

For the opposite case to Step 4 (i.e, the case where the sorted permutation is valid), can you think of a way to solve this?

Now lets solve the same case as Step 4. For each $$$k$$$, consider a consecutive run of $$$-1$$$ and try to find the number of ways to fill it, lets try to find some nice properties for some cases. Let me introduce some notation, I will type each gap in the following way:

• an $$$l \rightarrow l$$$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the left side of the split.

• an $$$l \rightarrow r$$$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the right side of the split.

• similar notation for $$$r \rightarrow l$$$ and $$$r \rightarrow r$$$.

Now notice that for any $$$k$$$, the number of ways to fill an $$$l \rightarrow l$$$ or $$$r \rightarrow r$$$ gap will always be the same.

For the $$$l \rightarrow r$$$ and $$$r \rightarrow l$$$ gaps, we have to get a bit more creative. The key thing to notice is that each $$$k$$$ will demand a unique number of elements from the left side of the split to be placed inside the gap. Now since the number of left elements must be between $$$0$$$ and the size of the gap, we can restrict the number of $$$k$$$ we need to consider to no more than the size of the gap!

For each gap, calculate this range of valid $$$k$$$, and take the intersection of all the ranges. Now if we use a very similar implementation to the easy version of the problem but only consider $$$k$$$ within this range, and skipping $$$l \rightarrow l$$$ and $$$r \rightarrow r$$$ gaps by calculating their contribution separately, the problem will be solved. Since, say, the range of valid $$$k$$$ has size $$$x$$$, then the number of $$$l \rightarrow r$$$ and $$$r \rightarrow l$$$ gaps will be no more than approximately $$$n/x$$$, and so the final time complexity is $$$O(x \cdot n/x)$$$, which is $$$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); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://mirror.codeforces.com/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>;

struct Combi{
    vector<mint> _fac, _ifac;
    int n;
    
    Combi() {
        n = 1;
        _fac.assign(n + 1, 1);
        _ifac.assign(n + 1, 1);
    }
    
    void check_size(int m){
        int need = n;
        while (need < m) need *= 2;
        m = need;
        if (m <= n) return;
        
        _fac.resize(m + 1);
        _ifac.resize(m + 1);
        for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1];
        
        _ifac[m] = _fac[m].inv();
        for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
        n = m;
    }
    
    mint fac(int m){
        check_size(m);
        return _fac[m];
    }
    
    mint ifac(int m){
        check_size(m);
        return _ifac[m];
    }
    
    mint ncr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r) * ifac(r);
    }
    
    mint npr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r);
    }
} comb;

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

    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
        if (x != -1)
            x--;
    }

    bool fixed = true;
    for (int i = 0; i < n; i++)
        if (a[i] != -1 && a[i] != i)
            fixed = false;

    if (fixed){ //case where all a[i] != -1 has a[i] = i
        vector<mint> prod(n + 1);
        prod[0] = 1;
        for (int i = 1; i <= n; i++)
            prod[i] = prod[i - 1] * 2;

        int last = -1;
        mint ans = 0;
        for (int i = 0; i <= n; i++){
            if (i == n || a[i] != -1){
                int len = i - last - 1;
                ans += prod[len] - len - 1;
                last = i;
            }
        }

        ans += 1;
        cout << ans << "\n";
        return;
    }

    vector<bool> side(n);
    bool found = false;
    for (int i = 0; i < n; i++){
        if (a[i] == -1)
            continue;

        if (a[i] < i)
            side[i] = false; // left side
        if (a[i] > i)
            side[i] = true; // right side
        if (a[i] == i)
            side[i] = found;
        if (a[i] != i)
            found = true;
    }

    int last = -1;
    vector<array<int, 2>> ranges;
    for (int i = 0; i < n; i++){
        if (a[i] == -1)
            continue;
        
        if (last == -1){
            last = i;
            continue;
        }

        if (side[i] && !side[last]){ // left -> right gap
            int mn = last - a[last]; // min right already placed
            int mx = mn + i - last; // max right already placed
            ranges.push_back({a[i] - mx, a[i] - mn + 1});
        }

        if (!side[i] && side[last]){ // right -> left gap
            int mx = i - a[i]; // max right placed by last
            int mn = mx - (i - last); // min right placed by last
            ranges.push_back({a[last] - mx, a[last] - mn + 1});
        }

        last = i;
    }

    int l = 0, r = n - 1;
    for (auto [u, v] : ranges){
        l = max(l, u);
        r = min(r, v);
    }

    mint coef = 1;
    vector<mint> score(n); // score[i] = contribution when splitting at i
    for (int i = l; i <= r; i++)
        score[i] = 1;

    last = -1;
    for (int i = 0; i < n; i++){
        if (a[i] == -1)
            continue;
        
        bool prev = false;
        if (last != -1)
            prev = side[last];
        int spaces = i - last - 1;

        if (side[i] && prev || !side[i] && !prev){
            int cnt = 0;
            if (last == -1)
                cnt = a[i];
            else
                cnt = a[i] - a[last] - 1;

            coef *= comb.ncr(spaces, cnt);
        }

        if (side[i] && !prev){ // left -> right
            for (int j = l; j <= r; j++){
                int placed = 0;
                if (last != -1)
                    placed = last - a[last]; // how many right i have placed by last

                int need = a[i] - (j + placed); // j + placed is the next one i need to place after last
                score[j] *= comb.ncr(spaces, need);
            }
        }

        if (!side[i] && prev){ // right -> left
            for (int j = l; j <= r; j++){
                int big = i - a[i] + j - 1; // last right to be placed by i
                
                int need = big - a[last];
                score[j] *= comb.ncr(spaces, need);
            }
        }

        last = i;
    }

    for (int j = l; j <= r; j++){
        if (!side[last]){
            score[j] *= comb.ncr(n - last - 1, j - a[last] - 1);
        }
        else{
            score[j] *= comb.ncr(n - last - 1, n - 1 - a[last]);
        }
    }

    mint ans = 0;
    for (int i = 0; i < n; i++)
        ans += score[i];
    ans *= coef;
    cout << ans << "\n";
}

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

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 $$$1$$$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) \lt 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. I think the easiest way to calculate this range is to use DSU, iterate in order of $$$p_i$$$ and merge with everything it can reach in one move, storing leftmost and rightmost element currently in the component to be fast enough.

It is important to note that these ranges we are calculating have some form of tree structure, because of how we calculated them every pair of ranges will either not intersect or one will contain the other. This means that if we iterate in order of size and "fix" a position in each range we will calculate the answer.

There is actually no need to build the tree, and instead we can multiply by the size of each DSU component as we are merging, after each merge decreasing 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://mirror.codeforces.com/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();
}

For an arbitrary array $$$b$$$ first notice that $$$\min(b_1,\ldots,b_i)$$$ and $$$\max(b_{i + 1},\ldots,n)$$$ is both non-increasing as we increase $$$i$$$. This means that if an array $$$b$$$ is epic then there exists a unique pair of integers $$$x, y$$$ such that $$$x + y = k$$$ and there exists $$$i, (1 \le i \lt |b|)$$$ such that $$$\min(b_1,\ldots,b_i) = x$$$ and $$$\max(b_{i + 1},\ldots,n) = y$$$.

Lets call an array $$$b$$$ $$$x$$$-epic if it is epic due to the pair $$$x, k - x$$$. Because the pair $$$x, y$$$ is unique, the answer will be equivalent to the sum of all $$$x$$$-epic subarrays of $$$a$$$. So lets try to find this sum.

Lets say we are trying to find the sum of all $$$x$$$ epic subarrays for a given $$$x$$$ and let $$$y = k - x$$$. Firstly the subarray must obviously contain both $$$x$$$ and $$$y$$$, so lets try to find for each $$$i$$$ the number of subarrays that are epic where $$$a_i$$$ is the first instance of $$$x$$$ in the subarray. Notice that it must be true that the first element smaller than $$$x$$$ must come after the last element bigger than $$$y$$$. Notice also that there cannot be an element bigger than $$$y$$$ after the last instance of $$$y$$$.

So we should store for each index $$$j$$$ such that $$$p_j = y$$$ the length of the longest consecutive sequence of elements strictly less than $$$y$$$, which contains $$$j$$$ as its leftmost element. Then for each $$$i$$$ where $$$p_i = x$$$ we should binary search for the last time where first element smaller than $$$x$$$ after the last element bigger than $$$y$$$. Once we can use prefix sums to find the number of possible right positions of the subarray. To find the number of possible left positions of the subarray it is just the length of the longest consecutive interval which only contains element strictly larger than $$$x$$$ and contain $$$i$$$ as its right most element. Now we know the number of possible left endpoints of the subarray and right endpoints, so we can just add their product to the answer.

After doing this across all $$$i$$$ we will have the answer.

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

template <class T> struct SegTree{
    vector<T> seg;
    int n;
    const T ID = {INT_MAX, -INT_MAX};
    
    T cmb(T a, T b){
        array<int, 2> res;
        res[0] = min(a[0], b[0]);
        res[1] = max(a[1], b[1]);
        return res;
    }
    
    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);
    }
};

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

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

    vector<vector<int>> p(n + 1);
    for (int i = 0; i < n; i++)
        p[a[i]].push_back(i);
    
    vector<array<int, 2>> stk;
    vector<int> small_l(n, -1), small_r(n, n), big_l(n, -1), big_r(n, n);

    for (int i = 0; i < n; i++){
        while (stk.size() && a[i] <= stk.back()[0])
            stk.pop_back();

        if (stk.size())
            small_l[i] = stk.back()[1];
        stk.push_back({a[i], i});
    }

    stk.clear();
    for (int i = n - 1; i >= 0; i--){
        while (stk.size() && a[i] >= stk.back()[0])
            stk.pop_back();

        if (stk.size())
            big_r[i] = stk.back()[1];
        stk.push_back({a[i], i});
    }

    ll ans = 0;
    SegTree<array<int, 2>> seg_small(n), seg_big(n);

    for (int x = 1; x <= n; x++){
        int y = k - x;
        if (y > n){
            for (int pos : p[x])
                seg_small.upd(pos, {pos, pos});
            continue;
        }

        vector<int> pre(p[y].size());
        for (int i = 0; i < p[y].size(); i++){
            if (i > 0)
                pre[i] += pre[i - 1];

            int r = big_r[p[y][i]] - 1;
            if (i < p[y].size() - 1)
                r = min(r, p[y][i + 1] - 1);
            pre[i] += r - p[y][i] + 1;
        }

        vector<int> first(p[x].size()), last(p[y].size());
        for (int i = 0; i < p[x].size(); i++)
            first[i] = seg_small.query(p[x][i], n - 1)[0];

        for (int i = 0; i < p[y].size(); i++)
            last[i] = seg_big.query(0, p[y][i])[1];

        int prev = -1;
        for (int i = 0; i < p[x].size(); i++){
            int l = p[x][i];
            int l_min = small_l[l] + 1;
            l_min = max(l_min, prev + 1);
            prev = l;

            int nxt = upper_bound(p[y].begin(), p[y].end(), l) - p[y].begin();
            if (nxt == p[y].size())
                continue;
       
            int lo = nxt, hi = p[y].size();
            while (lo < hi){
                int mid = (lo + hi) / 2;

                int pos = p[y][mid];
                if (first[i] <= last[mid])
                    hi = mid;
                else
                    lo = mid + 1;
            }

            lo--;
            if (lo < nxt)
                continue;

            int res = pre[lo];
            if (nxt > 0)
                res -= pre[nxt - 1];

            ans += 1LL * (l - l_min + 1) * res;
        }

        for (int pos : p[x])
            seg_small.upd(pos, {pos, pos});
        for (int pos : p[y])
            seg_big.upd(pos, {pos, pos});
    }

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

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