Hướng dẫn bài PQUERY

#include <iostream>
#include <cstdio>
using namespace std;
const int maxN = 1e6 + 1;
int s[maxN];
int n, m;

inline int ReadInt() {
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        ;
    int res = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) res = res * 10 + c - '0';
    return res;
}

void WriteInt(int x) {
    if (x > 9)
        WriteInt(x / 10);
    putchar(x % 10 + '0');
}

inline bool Odd(int x) { return x & 1; }

struct TSegmentTree {
    typedef int TTreeArr[4 * maxN];
    TTreeArr L, H, sumV, minV;
    int leaf[maxN];
    void Build(int x, int low, int high) {
        L[x] = low;
        H[x] = high;
        if (low == high) {
            leaf[low] = x;
            sumV[x] = minV[x] = s[low];
        } else {
            int middle = (low + high) / 2;
            Build(2 * x, low, middle);
            Build(2 * x + 1, middle + 1, high);
            sumV[x] = sumV[2 * x] + sumV[2 * x + 1];
            minV[x] = min(minV[2 * x], sumV[2 * x] + minV[2 * x + 1]);
        }
    }
    inline void Increase(int i, int Delta) {
        int x = leaf[i];
        sumV[x] += Delta;
        minV[x] += Delta;
        for (x /= 2; x > 0; x /= 2) {
            sumV[x] += Delta;
            minV[x] = min(minV[2 * x], sumV[2 * x] + minV[2 * x + 1]);
        }
    }
    inline int GetLastMin(int x)  // Tìm vị trí cuối cùng p: s[L[x]] + s[L[x] + 1] + ... + s[i] = minV[x]
    {
        while (L[x] < H[x]) x = sumV[2 * x] + minV[2 * x + 1] == minV[x] ? 2 * x + 1 : 2 * x;
        return L[x];
    }
    int FindMatch(int i) {
        --i;
        int t = 0;
        int y = -1, z = -1, ty;
        for (int x = leaf[i]; x > 0; x /= 2)
            if (!Odd(x))  // x chẵn => con trái
            {
                if (minV[x + 1] + t < 0) {
                    y = x + 1;
                    ty = t;
                    break;
                } else if (minV[x + 1] + t == 0)
                    z = x + 1;  // có ứng viên trong nhánh gốc z
                t += sumV[x + 1];
            }
        if (y != -1)  // Tìm thêm ứng viên z trong nhánh gốc y
        {
            while (L[y] < H[y])
                if (minV[y * 2] + ty < 0)
                    y *= 2;
                else {
                    if (minV[y * 2] + ty == 0)
                        z = y * 2;
                    ty += sumV[y * 2];
                    y = y * 2 + 1;
                }
        }
        // z = nút chứa điểm match với i
        return z == -1 ? i : GetLastMin(z);
    }
} tree;

void Enter() {
    n = 0;
    s[0] = 0;
    char c;
    for (c = getchar(); c == '(' || c == ')'; c = getchar()) s[++n] = c == '(' ? 1 : -1;
    tree.Build(1, 0, n);
}

inline void PerformFlip(int i) {
    s[i] = -s[i];
    tree.Increase(i, s[i] == 1 ? 2 : -2);
}

inline int PerformQuery(int i) { return tree.FindMatch(i) - i + 1; }

void Solve() {
    m = ReadInt();
    for (; m > 0; --m) {
        char c;
        for (c = getchar(); c != 'C' && c != 'Q'; c = getchar())
            ;
        if (c == 'C')
            PerformFlip(ReadInt());
        else {
            WriteInt(PerformQuery(ReadInt()));
            putchar('\n');
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Enter();
    Solve();
}