It's optimal to make adjacent characters different.

If two adjacent characters are same, then they only add the total time by $$$1$$$ seconds. If we insert a different character between them, the $$$1$$$ will turn into two $$$2$$$ s, which add the total time by $$$2$$$ seconds. Since you can only insert $$$1$$$ character in it, it's the optimal insertion method.

If that same adjacent pair doesn't exist, we can still add a different character between an arbitrary pair, then it will add the total time by $$$2$$$ seconds.

Time complexity: $$$O(n)$$$.

# include <iostream>
# include <string>
using namespace std;
const int N = 1e5 + 10;
string s;
int n, tp;
void run()
{
    cin >> s;
    n = s.size();
    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            tp = 0;
            while (s[i] == tp + 'a' or s[i + 1] == tp + 'a')
                tp++;
            s.insert(s.begin() + i + 1, tp + 'a');
            break;
        }
    }
    if (n == s.size())
    {
        if (s.back() == 'z')
            s.push_back('a');
        else
            s.push_back('z');
    }
    cout << s << '\n';
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

The given grid contains at most $$$1$$$ connected region.

There are only $$$2$$$ rows in this grid.

Imagine a trap.

Since there are only $$$2$$$ rows in the grid, so all the cell unblocked will have at most $$$3$$$ adjacent unblocked cells.

In order to make $$$3$$$ connected components, we should seperate these $$$3$$$ adjacent unblocked cells into different connected components. So how to do that?

Imagine a "trap" like this:

...
x.x

We can see that if we block the middle cell on the upper row, it will separate into $$$3$$$ connected components like this:

.x.
x.x

It's the only way to separate legally.

Time complexity: $$$O(n)$$$.

# include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, res;
char ch[2][N];
void run()
{
    cin >> n;
    cin >> ch[0];
    cin >> ch[1];
    res = 0;
    for (int j = 0; j < 2; j++)
    {
        for (int i = 1; i < n - 1; i++)
        {
            if (ch[j][i] == '.')
            {
                res += (ch[j ^ 1][i - 1] == 'x' and
                        ch[j ^ 1][i + 1] == 'x' and
                        ch[j ^ 1][i] == '.' and
                        ch[j][i - 1] == '.' and
                        ch[j][i + 1] == '.');
            }
        }
    }
    printf("%d\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

It's OK to construct it greedily.

For a RBS $$$s$$$, we define its layer value $$$l$$$ as this:

"Layer" stands for "the layer number of brackets pair".

And its prefix value $$$p$$$ is this:

Then, it's required to satisfy $$$p_n=0$$$ and $$$\min(p)=0$$$.

If $$$\min(p)<0$$$, it'll no longer be a RBS.

Then, we define the require value $$$r$$$ as this:

Note that this $$$s$$$ may contains "_".

A legal construction of $$$s$$$ satisfies $$$p_i\ge r_i$$$.

Then, for each position $$$i$$$, if inserting an ")" may make $$$p_i<r_i$$$, then insert an "(" instead.

It can be proved that this is the optimal construction method.

Time complexity: $$$O(n)$$$.

Fun fact: I got $$$2$$$ runtime errors during the contest because I set the array size to $$$10^5$$$ while the problem requires $$$2\times 10^5$$$.

# include <iostream>
# include <string>
# include <stack>
using namespace std;
const int N = 2e5 + 10;
string s;
int n, ts[N];
stack<int> stk;
using ll = long long;
ll res;
void run()
{
    cin >> n >> s;
    ts[n] = res = 0;
    for (int i = n - 1; ~i; i--)
    {
        if (s[i] != ')')
        {
            ts[i] = max(0, ts[i + 1] - 1);
        }
        else
        {
            ts[i] = ts[i + 1] + 1;
        }
    }
    for (int i = 0, tmp = 0; i < n; i++)
    {
        // printf("%d%c", ts[i], " \n"[i == n - 1]);
        if (s[i] == '(')
        {
            tmp++;
            stk.push(i);
            continue;
        }
        if (s[i] == ')')
        {
            tmp--;
            res += i - stk.top();
            stk.pop();
            continue;
        }
        if (tmp - 1 < ts[i + 1] or !stk.size())
        {
            tmp++;
            s[i] = '(';
            stk.push(i);
            continue;
        }
        s[i] = ')';
        tmp--;
        res += i - stk.top();
        stk.pop();
    }
    // cout << s << '\n';
    printf("%lld\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

After each operation, the values on all vertices should be non-negative.

Maximize the minimum.

With the formula in hint $$$3$$$, we can quickly realize that we should make $$$\min_{i=2}^n a_i$$$ as big as possible. So how to do that?

Well, the operation that the problem provides is able to add a vertex by subtracting the rest of its subtree. So, in order to maximize the minimum, we can simply make them closer.

If the value of a vertex is already higher than the minimum value of its subtree, we can't get them closer.

Apply a depth-first search to do that.

Time complexity: $$$O(n)$$$.

# include <iostream>
# include <vector>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], cont[N];
vector<int> road[N];
void dfs(int x, int f)
{
    cont[x] = 0x3f3f3f3f;
    for (auto &i : road[x])
    {
        if (i == f)
            continue;
        dfs(i, x);
        cont[x] = min(cont[x], cont[i]);
    }
    if (x == 1)
        return;
    // printf("%d %d %d\n", x, cont[x], a[x]);
    if (cont[x] == 0x3f3f3f3f)
        cont[x] = a[x];
    else if (cont[x] > a[x])
    {
        // printf("c %d %d\n", cont[x], a[x]);
        cont[x] = (cont[x] + a[x]) / 2;
        // printf("c %d %d\n", cont[x], a[x]);
    }
}
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        road[i].clear();
    }
    for (int i = 2, x; i <= n; i++)
    {
        scanf("%d", &x);
        road[x].push_back(i);
    }
    dfs(1, 0);
    // for (int i = 1; i <= n; i++)
    // {
    //     printf("%d%c", cont[i], " \n"[i == n]);
    // }
    printf("%d\n", a[1] + cont[1]);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

What will happen when we increase $$$k$$$?

The number of the monsters fleeing won't be higher. Why?

Because, a higher $$$k$$$ means the lower expectation level.

Binary search.

With the conclusion in hint $$$2$$$, we can calculate the Firmness requirement $$$f$$$ which satisfies when $$$k\ge f_i$$$, the $$$i$$$-th monster always fights with Monocarp.

If $$$i$$$-th monster fight with Monocarp with a parameter of $$$k$$$, then it must satisfy that

Because when Monocarp already fought $$$a_ik$$$ or more monsters before, then his level will be higher than $$$a_i$$$, and the $$$i$$$-th monster will flee.

The formula above is easy to calculate with a BIT.

After calculating the sequence $$$f$$$, we can answer all the queries in a time complexity of $$$O(1)$$$.

Time complexity: $$$O(n\log^2 (2\times 10^5)+q)$$$.

Fun fact: I applied an unnecessary sort on the queries. However, it still has a good speed.

# include <iostream>
# include <vector>
# include <tuple>
# include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid;
vector<int> dst[N];
inline void update(int x, int v)
{
    while (x < N)
    {
        tr[x] += v;
        x += (x & -x);
    }
}
inline int query(int x)
{
    int res = 0;
    while (x)
        res += tr[x], x -= (x & -x);
    return res;
}
inline bool check(int x, int v) // xth monster will fl, x=v
{
    return 1ll * a[x] * v <= query(v);
}
using t3i = tuple<int, int, int>;
t3i qry[N];
bool res[N];
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= q; i++)
    {
        auto &[x, k, id] = qry[i];
        scanf("%d%d", &x, &k);
        id = i;
    }
    sort(qry + 1, qry + q + 1);
    for (int i = 1; i <= q; i++)
    {
        auto &[x, k, id] = qry[i];
        while (idx < x)
        {
            l = 1, r = n;
            while (l < r)
            {
                mid = (l + r) >> 1;
                if (check(idx, mid))
                    l = mid + 1;
                else
                    r = mid;
            }
            update(l, 1);
            idx++;
        }
        res[id] = !check(x, k);
    }
    for (int i = 1; i <= q; i++)
    {
        puts(res[i] ? "YES" : "NO");
    }
}