Truy vấn dãy ngoặc - LCOJ: Luyện Code Online Judge

QBRACK - Truy vấn dãy ngoặc

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một xâu độ dài ~N~ chỉ gồm các kí tự ( và ), các kí tự được đánh số từ ~1~ đến ~N~ theo chiều từ trái qua phải.

Một dãy ngoặc đúng được định nghĩa như sau:

Xâu rỗng là một dãy ngoặc đúng;
Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ là một dãy ngoặc đúng;
Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ là một dãy ngoặc đúng;

Cho ~M~ truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

~0\ i:~ thay đổi kí tự dấu ngoặc ở vị trí ~i~ của xâu kí tự thành kí tự dấu ngoặc ngược lại;
~1\ i\ j:~ in ra ~1~ nếu xâu con từ vị trí ~i~ đến vị trí ~j~ là một dãy ngoặc đúng, in ra ~0~ trong trường hợp ngược lại.

Input

Dòng đầu chứa hai số nguyên dương ~N, M~ là độ dài dãy ngoặc và số truy vấn;
Dòng thứ hai chứa xâu ký tự độ dài ~N~ chỉ gồm các ký tự ( và ) ;
~M~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại nêu trên.

Giới hạn:

~1 ≤ N, M ≤ 10^5; 1 ≤ i ≤ j ≤ N~.

Output

Một chuỗi gồm các ký tự ~0~ hoặc ~1~ tướng ứng với câu trả lời mỗi truy vấn loại ~1\ i\ j~.

Sample

Input #1

Output #1

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

debug khủng khiếp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1000001;
string s;
struct node {
    int a; //ngoặc đúng
    int b; // ngoặc mở thừa
    int c; // ngoặc đóng thừa
    node(int x = 0, int y = 0, int z = 0) {
        a = x;
        b = y;
        c = z;
    }
    friend node operator + (const node &l, const node &r) {
        node ans(0, 0, 0);
        int t = min(l.b, r.c);
        ans.a = l.a + r.a + 2 * t;
        ans.b = l.b + r.b - t;
        ans.c = l.c + r.c - t;
        return ans;
    }
} nodes[4 * maxn];

void build(int i, int l, int r) {
    if (l == r) {
        if (s[l] == '(') nodes[i] = node(0, 1, 0);
        else nodes[i] = node(0, 0, 1);
        return;
    }   
    int mid = (r + l) / 2;
    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
    nodes[i] = nodes[2 * i] + nodes[2 * i + 1];
}
void add(int i, int l, int r, int pos) {
    if (l == r) {
        if (s[l] == '(') {
            s[l] = ')';
            nodes[i] = node(0, 0, 1);
        }
        else {
            s[l] = '(';
            nodes[i] = node(0, 1, 0);

        }
        return;
    }
    int mid = (l + r) / 2;

    if (pos <= mid)add(2 * i, l, mid, pos);
    else add(2 * i + 1, mid + 1, r, pos);
    nodes[i] = nodes[2 * i] + nodes[2 * i + 1];
}
node getmax(int i, int l, int r, int u, int v) {
    if (r < u || l > v) return node(0, 0, 0);
    if (u <= l && r <= v) return nodes[i];
    int mid = (l + r) / 2;
    return getmax(i * 2, l, mid, u, v) + getmax(i * 2 + 1, mid + 1, r, u, v);
}   
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, u, v, t; cin >> n >> m;
    cin >> s;
    build(1, 0, n - 1);
    node nodeq(0, 0, 0);

    while (cin >> t) {
        if (t) {
            cin >> u >> v;
            nodeq = getmax(1, 0, n - 1, u - 1, v - 1);
            cout << (!nodeq.b && !nodeq.c);
        } else {
            cin >> u;
            add(1, 0, n - 1, u - 1);
        }
    }
}

1

phucan1402 đã bình luận lúc 11, Tháng 10, 2025, 8:03

Bài này dùng segment tree và 1 struct node lưu 3 giá trị số cặp hợp lệ, số ngoặc mở còn thừa, số ngoặc đóng còn thừa. Bài này khá tương đồng với bài 380C Codeforces. Source code AC: https://ideone.com/bdWsMQ

1

MANHOOH đã bình luận lúc 29, Tháng 8, 2025, 12:34 ← chỉnh sửa →

nút của cây nay đã dữ dội và nhiều thông tin hơn