CF380C Sereja and Brackets 題解 數列分塊

題目連結：​​https://codeforces.com/contest/380/problem/C​​

題目大意：給定長度為 \(n(\le 10^6)\) 的一個括号序列，有 \(m(\le 10^5)\) 次詢問，每次詢問給定一個區間 \([l,r]\)，你需要回答出區間 \([l,r]\)

解題思路：

首先，無論在哪個區間範圍内，每一個 ')' 所比對的 '(' 都是固定的。

我們可以用 \(f[i]\) 表示下标為 \(i\)

對于每次詢問的 \(l\) 和 \(r\)，問題就變成了詢問區間 \([l,r]\) 範圍記憶體在多少 \(f[i]\) 滿足 \(f[i] \ge l\)。

這個問題用 分塊 是很好解決的，對于完整的分開，隻需要初始時對每個分塊的 \(f[i]\) 排序，然後查詢的時候就可以二分查找 \(\le l\)

時間複雜度是 \(O(m \cdot \sqrt{n} \cdot \log n)\)，但是因為常數比較小（這裡的 \(\log n\) 其實是 \(\log \sqrt{n} = \frac{1}{2} \log n\)，然後不比對的狀态 \(f[i]\)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char s[maxn];
int n, m, l, r, f[maxn];
int blo, bl[maxn];
vector<int> vec[1010];

void init() {
    stack<int> stk;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') stk.push(i);
        else if (!stk.empty()) {
            f[i] = stk.top();
            stk.pop();
        }
    }
    blo = sqrt(n);
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / blo + 1;
        if (f[i]) vec[bl[i]].push_back(f[i]);
    }
    for (int i = 1; i <= bl[n]; i++)
        sort(vec[i].begin(), vec[i].end());
}

int solve(int l, int r) {
    int cnt = 0;
    for (int i = l; i <= min(bl[l]*blo, r); i++) if (f[i] >= l) cnt++;
    if (bl[l] != bl[r]) {
        for (int i = (bl[r]-1)*blo+1; i <= r; i++) if (f[i] >= l) cnt++;
    }
    for (int i = bl[l]+1; i < bl[r]; i++) {
        int num = vec[i].end() - lower_bound(vec[i].begin(), vec[i].end(), l);
        cnt += num;
    }
    return cnt * 2;
}

int main() {
    scanf("%s%d", s+1, &m);
    n = strlen(s+1);
    init();
    while (m--) {
        scanf("%d%d", &l, &r);
        printf("%d\n", solve(l, r));
    }
    return 0;
}