## Bài 1. Dãy con có độ dài bị chặn

### Subtask 1
Duyệt $\mathcal{O}(Q)$ truy vấn, với mỗi truy vấn:
- Duyệt $\mathcal{O}(N^2)$ đoạn con, tính tổng trong $\mathcal{O}(N)$ và cập nhật đáp án.

**Độ phức tạp:** $\mathcal{O}(QN^3)$

### Subtask 2
Duyệt $\mathcal{O}(Q)$ truy vấn, với mỗi truy vấn:
- Duyệt $\mathcal{O}(N^2)$ đoạn con, tính tổng trong $\mathcal{O}(1)$ và cập nhật đáp án.

**Độ phức tạp:** $\mathcal{O}(QN^2)$

### Subtask 3
Duyệt $N$ độ dài $1\to N$, với mỗi độ dài $\ell$, duyệt $\mathcal{O}(N)$ và lưu lại tổng lớn nhất của một đoạn con độ dài $\ell$ trong dãy vào mảng `best[l]`.

Duyệt $Q$ truy vấn, với truy vấn thứ $i$, ta đi tìm $\max_{L_i \le x \le H_i}\{best[x]\}$ trong $\mathcal{O}(N)$.

Độ phức tạp $\mathcal{O}(N^2 + QN)$

### Subtask 4
Xét mảng tổng tiền tố $S$, với $S[i] = \sum\limits_{x = 1}^{i} a[x]$. Ta có thể dựng mảng trong $O(N)$ bằng công thức truy hồi sau:
$$
S[i] = S[i-1] + a[i]
$$

Xét $Q$ truy vấn, với mỗi truy vấn $(L_{i}, H_{i})$:
- **Nhận xét:** Ta tiến hành duyệt đầu phải $y$ của đoạn con trong $O(N)$, với mỗi $y (1 \le y \le N)$. Ta cần tìm $x$ sao cho:
$$
\begin{cases}
0 \le x < y \\
L_{i} \le y-x \le H_i \\
\max\{S[y]-S[x]\}
\end{cases}
$$
Do $y$ và $S[y]$ cố định, điều kiện trở thành:
$$
\begin{cases}
0 \le x < y \\
y-L_{i} \ge x \ge y-H_{i} \\
\min\{S[x]\}
\end{cases}
$$

Từ đây, thuật toán là với mỗi truy vấn, ta duyệt $y$ trong $O(N)$, sau đó tìm $\min\{S[x]\}$ với $x \in [y-H_{i}, y-L_{i}]$ trong $\mathcal{O}(1)$ bằng [[sparse_table|Sparse Table]].

**Độ phức tạp:** $\mathcal{O}(QN)$

## Bài 2. Mạng thông suốt

### Subtask 1
Duyệt $\mathcal{O}(n^2)$ cặp đỉnh $(u, v)$ trong đồ thị, nếu chưa tồn tại cung $u \to v$, thì thêm cung vào và kiểm tra tính liên thông mạnh của đồ thị này trong $O(n \cdot m)$ bằng cách xét từng đỉnh rồi [[dfs_bfs|DFS]] xem đỉnh có thể thăm được toàn bộ các đỉnh còn lại không.
**Độ phức tạp:** $\mathcal{O}(n^{3}\cdot m)$

### Subtask 2
**Nhận xét:** Đáp án của bài toán là `YES` khi và chỉ khi:
- Đồ thị liên thông mạnh. Trong trường hợp này ta có thể thêm cạnh bất kì.
- Đồ thị gồm nhiều thành phần liên thông mạnh nối liên tiếp nhau theo dạng: $C_1 \to C_2 \to C_3 \to \dots \to C_k$. Trong trường hợp này, ta thêm một cung $u\to v$ với $u$ là một đỉnh bất kì thuộc $C_k$ và $v$ là một đỉnh bất kì thuộc $C_1$

Để xác định các thành phần liên thông, ta có thể dùng $n$ lần [[dfs_bfs|DFS]] từ mỗi đỉnh, đánh dấu $c[i][j] = 1$ nếu tồn tại đường đi từ $i$ đến $j$. Nếu $c[i][j] = c[j][i] = 1$ cho một cặp $(i, j)$ bất kì, ta sẽ dùng [[DSU]] để unite hai đỉnh này lại.

Độ phức tạp: $\mathcal{O}(n \cdot m)$

### Subtask 3
Ta dùng thuật toán [[strongly_connected_component|Tarjan]] để xác định các thành phần liên thông trong $\mathcal{O}(m)$.

## Bài 3. Đếm dãy

### Subtask 1
Duyệt $O(2^n)$ cách chọn, với mỗi cách chọn kiểm tra điều kiện đề bài trong hoặc $O(n)$
**Độ phức tạp:** $O(2^{n}\cdot n)$

#### Đệ quy

void try(int i, int open, int close) {
	if (i == n) {
		if (open == close) ++ans;
		return;
	}
	try(i+1, open, close);
	if (s[i] == '(' && close == 0) try(i+1, open+1, close);
	if (s[i] == ')') try(i+1, open, close+1);
}

#### Khử đệ quy

int ans = 0;
for(int mask = 0; mask < (1ll<<n); ++mask) {
	int open = 0, close = 0;
	bool ok = true;
	for(int i = 0; i < n; ++i) if ((mask>>i)&1) {
		if (s[i] == '(') {
			if (close > 0) ok = false;
			open++;
		} else close++;
	}
	if (open != close) ok = false;
	if (ok) ++ans;
}
cout << ans;

### Subtask 2
Gọi $\text{dp}[L][R][open][close]$ là số cách chọn dãy ngoặc trong đoạn $[L, R]$, đã chọn được $open$ ngoặc mở và $close$ ngoặc đóng.
$$
\begin{align*}\\
&\text{dp}[i][i][1][0] = 1 \text{ nếu } s[i] = '('\\
&\text{dp}[i][i][0][1] = 1 \text{ nếu } s[i] = ')' \\
&\text{dp}[L-1][R][open][close] += \text{dp}[L][R][open][close] \\
&\text{dp}[L-1][R][open+1][close] += \text{dp}[L][R][open][close] \text{ nếu } S[L-1] = '(' \\
&\text{dp}[L][R+1][open][close] += \text{dp}[L][R][open][close] \\
&\text{dp}[L-1][R][open][close+1] += \text{dp}[L][R][open][close] \text{ nếu } S[R+1] = ')' \\
\end{align*}
$$

**Độ phức tạp:** $\mathcal{O}(n^4)$

### Subtask 3
Gọi $\text{dp}[i][open][close]$ là số cách chọn dãy ngoặc khi xét đến $i$, có $open$ ngoặc mở và $close$ ngoặc đóng. Công thức quy hoạch động:
$$
\begin{align*}
&\text{dp}[0][0][0] = 1\\
&\text{dp}[i+1][open][close] += \text{dp}[i][open][close]\\
&\text{Nếu } s[i] = '(', \text{dp}[i+1][open+1][0] += dp[i][open][0]\\
&\text{Nếu } s[i] = ')', \text{dp}[i+1][open][close+1] += dp[i][open][close]
\end{align*}
$$
Đáp án là
$$
\sum\limits_{i=1}^{n} \text{dp}[n][i][i]
$$

**Độ phức tạp:** $\mathcal{O}(n^3)$

### Subtask 4
Tính $L[i][open]$ là số cách chọn $open$ ngoặc mở nằm bên trái $i$. $R[i][close]$ là số cách chọn $close$ ngoặc đóng nằm bên phải $i$.

Duyệt $i$ từ $0$ đến $n-1$, chọn $i$ là điểm trung gian và $i$ là **ngoặc mở**, duyệt $k$ là số lượng ngoặc mở và số lượng ngoặc đóng, đếm số cách chọn $k$ ngoặc mở ở bên trái $i$ và $k$ ngoặc đóng ở bên phải $i$. Số lượng dãy ngoặc đẹp trong trường hợp này sẽ là $L[i][k] \times R[i][k]$

const int N = 9005;
const int MOD = 1e9+19972207;
int L[N][N], R[N][N];

void add(int &a, int b) {
	a += b;
	if (a >= MOD) a-= MOD;
}

...
memset(L, 0, sizeof L);
memset(R, 0, sizeof R);

for(int i = 0; i < n; ++i)
	for(int open = 0; open <= n; ++open) if (dp[i][open]) {
		add(dp[i+1][open], dp[i][open]);
		if (s[i] == '(') add(dp[i+1][open+1], dp[i][open]);
	}
	
// Tinh R
...

int ans = 0;
for(int i = 0; i < n; ++i)
	for(int cnt = 1; cnt <= n; ++cnt) 
		if (s[i] == '(') add(ans, 1ll*L[i][cnt]*R[i][cnt]%MOD);
cout << ans;

**Độ phức tạp:** $\mathcal{O}(n^2)$

### Subtask 5
Duyệt $i$ từ $0$ đến $n-1$, chọn $i$ là điểm trung gian và $i$ là **ngoặc mở**, duyệt $k$ là số lượng ngoặc mở và số lượng ngoặc đóng, đếm số cách chọn $k$ ngoặc mở ở bên trái $i$ và $k$ ngoặc đóng ở bên phải $i$. Số lượng dãy ngoặc đẹp trong trường hợp này sẽ là $C_{x}^{k} \times C_{y}^{k}$ với $x$ là số ngoặc mở bên trái $i$, $y$ là số ngoặc đóng bên phải $i$.

Như vậy, với mỗi vị trí $i \in [0, n-1]$, ta có tổng số ngoặc đẹp là
$$
\sum\limits_{k = 1}^{\min\{x, y\}}C_{x}^{k} \times C_{y}^{k}
= \sum\limits_{k = 1}^{\min\{x, y\}}C_{x}^{x-k} \times C_{y}^{k}
= C_{x+y}^{x} - 1
$$

Ta duy trì $x$ và $y$, trong quá trình duyệt $i$. Sau đó tính $C_{x+y}^n$ trong $O(1)$ hoặc $O(\log n)$.

**Độ phức tạp:** $\mathcal{O}(n \log n)$ hoặc $O(n)$

==0==1==0==11==0==0==1==0==111==
i
k = 2
00==0== 1==1==1==1==