E - Infinite Parenthesis Sequence

基本信息

题目出处	2018 ICPC 亚洲区域赛青岛站网络赛
队伍通过率	0/1550 (0.0%)

题解

考虑计算 $f (k, i)$ 表示 $B^{k}$ 中第 $i$ 个左括号的下标（ $i$ 可以为 $0$ 甚至负数），设 $g (k, p)$ 表示满足 $f (k, i) \leq p$ 的最大的 $i$ ，则区间 $[l, r]$ 里左括号的总数即为 $g (k, r) - g (k, l - 1)$ 。 $g$ 的值通过二分 $i$ 即可算出。

另外，由于我们只关心 $g$ 的差值，因此第 $0$ 个左括号具体对应哪个括号其实可以随便指定。方便起见，把最开始的有限字符串中的第一个左括号选为第 $0$ 个左括号。

接下来考虑 $f (k, i)$ 的转移方程。

如果 $f (k, i)$ 的下一个字符是右括号，因为 () -> )(，有 $f (k + 1, i) = f (k, i) + 1$ 。
如果 $f (k, i)$ 的下一个字符是左括号，因为 (( -> (*，有 $f (k + 1, i) = f (k, i + 1) - 1$ 。

综合起来，转移方程为

f (k + 1, i) = min (f (k, i) + 1, f (k, i + 1) - 1)

假设 $f (k, i)$ 是从 $f (0, j)$ 转移过来的，那么第一维从 $0$ 走到 $k$ 的过程中， $min$ 中的第二项恰选了 $(j - i)$ 次，第一项恰选了 $(k - (j - i))$ 次，因此转移方程还可以写为

f (k, i) = min_{i \leq j \leq i + k} (f (0, j) + k - 2 (j - i))

容易看出决策区间的长度是 $(i + k) - i = k$ 。设最开始的有限字符串中，左括号的数量共有 $m$ 个。首先分析 $k \leq m$ 的时候如何求出最小值。

设 $F (j) = f (0, j) - 2 j$ 。注意到 $f (0, j + m) - f (0, j) = n$ ，有

F (j + t) = F (j mod m + t) + (n - 2 m) \times ⌊ \frac{j}{m} ⌋

其中 $t$ 是任意非负数。因此我们可以用 RMQ 预处理 $F (0)$ 到 $F (2 m - 1)$ ，然后把 $[i, i + k]$ 映射到 $[i mod m, i mod m + k]$ 求最小值即可。

接下来分析 $k$ 比较大时的解法。讨论 $(n - 2 m)$ 的值：

若 $n - 2 m \geq 0$ ，说明 $F (j + m) \geq F (j)$ ，因此最小值只存在于 $i \leq j < i + m$ 这个范围中。
若 $n - 2 m < 0$ ，说明 $F (j + m) < F (j)$ ，因此最小值只存在于 $i + k - m < j \leq i + k$ 这个范围中。

这样我们就把区间长度缩小到了 $m$ ，又可以通过 RMQ 求出最小值了。

上面还有一个细节问题没有解决：二分 $g$ 的时候，上下界是多少？我们来看 $f (k, 0)$ 的取值范围。

取 $j = 0$ 时，有 $f (k, 0) \leq f (0, 0) + k < n + k$ ，因此 $g (k, l)$ 的最小值可能是 $(n + k - l)$ 。
由于 $f (0, j) \geq 0$ ， $- 2 (j - i) \geq - 2 k$ ，因此 $f (0, 0) \geq - k$ ，则 $g (k, r)$ 的最大值可能是 $(r + k)$ 。

所以二分上下界取 $[- 3 \times 10^{9}, 3 \times 10^{9}]$ 即可。

复杂度 $O (n \log n + q \log (n + k - l + r))$ 。

参考代码

#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
#define MAXP 20
using namespace std;

int n, m, q;
char s[MAXN + 10];

int lg[MAXN + 10], rmq[MAXP][MAXN * 2 + 10];

// RMQ 预处理 F(0) 到 F(2m - 1)
void preRmq() {
    m = 0;
    for (int i = 0; i < n; i++) if (s[i] == '(') rmq[0][m++] = i;
    for (int i = m; i < m * 2; i++) rmq[0][i] = rmq[0][i - m] + n;
    for (int i = 0; i < m * 2; i++) rmq[0][i] -= i * 2;

    for (int p = 1; p < MAXP; p++) for (int i = 0, ii = (1 << p) - 1; ii < m * 2; i++, ii++) {
        int j = i + (1 << (p - 1));
        rmq[p][i] = min(rmq[p - 1][i], rmq[p - 1][j]);
    }
}

long long calc(long long K, long long i) {
    long long L, R;
    // 根据 n - 2m 的值，将区间长度缩小到 min(m, k)
    if (m * 2 <= n) {
        L = i;
        R = min(i + K, L + m - 1);
    } else {
        R = i + K;
        L = max(i, R - m + 1);
    }

    // 将区间 [L, R] 映射到 [L mod m, L mod m + R - L]，再用 RMQ 求最小值
    long long div = (L >= 0 ? L / m : (L + 1) / m - 1);
    int mod = (L % m + m) % m;
    long long delta = n * div - 2 * div * m;
    int len = R - L + 1, p = lg[len];
    return min(rmq[p][mod], rmq[p][mod + len - (1 << p)]) + delta + K + 2 * i;
}

// 二分求 g(K, lim) 的值
long long query(long long K, long long lim) {
    long long head = -3e9, tail = 3e9;
    while (head < tail) {
        long long mid = (head + tail + 1) >> 1;
        if (calc(K, mid) <= lim) head = mid;
        else tail = mid - 1;
    }
    return head;
}

void solve() {
    scanf("%s", s); n = strlen(s);
    preRmq();

    scanf("%d", &q);
    while (q--) {
        long long K, l, r; scanf("%lld%lld%lld", &K, &l, &r);
        // 特殊情况：没有左括号
        if (m == 0) printf("0\n");
        else printf("%lld\n", query(K, r) - query(K, l - 1));
    }
}

int main() {
    lg[1] = 0;
    for (int i = 2; i <= MAXN; i++) lg[i] = lg[i >> 1] + 1;

    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}