AD VPBRACKET - tacongnam/DylanHarris GitHub Wiki

• Problem: AD - VPBRACKET
• Tag: Graph - Segment Tree
• Note: Tương tự CF 380C
• Introduction:
  Input: VPBRACKET.inp
  Output: VPBRACKET.out
  

Table of Contents Content: Dữ liệu Kết quả Ví dụ Solution Code Cách 1 Cách 2

Một dãy ngoặc đúng được định nghĩa như sau:
Xâu rỗng là 1 dãy ngoặc đúng.
Nếu A là 1 dãy ngoặc đúng thì (A) là 1 dãy ngoặc đúng.
Nếu A và B là dãy ngoặc đúng thì AB là 1 dãy ngoặc đúng.
Cho dãy ngoặc S độ dài N và Q truy vấn biểu diễn bởi 2 số nguyên l và r (1 ≤ l ≤ r ≤ N): Kiểm tra dãy ngoặc con S[l..r] có là dãy ngoặc đúng hay không ?

Dòng đầu tiên chứa 2 số nguyên dương N và Q (1 ≤ N, Q ≤ 10^5).
Dòng thứ hai chứa dãy ngoặc S.
Trong Q dòng tiếp theo, mỗi dòng chứa một truy vấn

Với mỗi truy vấn, in trên một dòng "YES" nếu đúng, ngược lại in "NO".

Input:

    7 3
    ((())()
    3 4
    1 5
    2 7

Output:

    YES
    NO
    YES

• Cách 1: (Solution bài 380C - CF)
  

We will support the segments tree. At each vertex will be stored:
a[v] — the maximum length of the bracket subsequence
b[v] — how many there it open brackets that sequence doesn't contain
c[v] — how many there it closed brackets that sequence doesn't contain
If we want to combine two vertices with parameters (a1, b1, c1) and (a2, b2, c2), we can use the following rules:
t = min(b1, c2)
a = a1 + a2 + t
b = b1 + b2 - t
c = c1 + c2 - t

• Cách 2:

Tạo một mảng s[] cộng dồn các vị trí. Nếu ở vị trí đó là dấu '(' thì s[i] = s[i-1] + 1, nếu là ')' thì s[i] = s[i-1] - 1.
Điều kiện để dãy ngoặc từ l đến r là dãy ngoặc đúng là:
1. s[l-1] == s[r] (nghĩa là tổng cộng dồn trên đoạn l -> r bằng 0) 2. Vị trí l phải là ngoặc mở, vị trí r phải là ngoặc đóng 3. Tổng cộng dồn trên đoạn l -> r đạt giá trị nhỏ nhất tại r

VPBRACKET_1.cpp

VPBRACKET_2.cpp