Đề bài

Một dãy được gọi là cân bằng nếu thỏa mãn định nghĩa đệ quy sau:

• Mọi dãy có độ dài \(1\) đều cân bằng.
• Dãy có độ dài \(2k+1\), \(S=[S_0,\ldots,S_{2k}]\), là cân bằng nếu:
• \([S_0,\ldots,S_{k-1}]\) cân bằng;
• \([S_{k+1},\ldots,S_{2k}]\) cân bằng;
• \(S_k\) là giá trị lớn nhất duy nhất trong toàn bộ \(S\).

Cho dãy \(A\) gồm \(N\) số nguyên. Ký hiệu \(A[i\ldots j]\) là dãy con liên tiếp từ phần tử \(i\) đến phần tử \(j\).

Có \(Q\) thao tác, mỗi thao tác thay đổi một phần tử của \(A\) và các thay đổi được giữ lại. Ở trạng thái ban đầu và sau mỗi thao tác, hãy tính số cặp \((i,j)\) thỏa mãn

và \(A[i\ldots j]\) là một dãy cân bằng.

Yêu cầu cài đặt

Bạn cần cài đặt hai hàm:

long long initialize(int N, vector<int> A);
long long update_sequence(int p, int v);

• initialize được gọi đúng một lần. Hàm phải trả về số dãy con cân bằng của dãy ban đầu.
• Mỗi lời gọi update_sequence(p, v) gán \(A[p]=v\) và phải trả về số dãy con cân bằng sau thay đổi. Hàm này được gọi tổng cộng \(Q\) lần sau initialize.
• Chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(1\le N\le 10^5\).
• \(0\le Q\le 10^5\).
• \(1\le A[i]\le 10^9\).
• Với mỗi lần cập nhật: \(0\le p\le N-1\) và \(1\le v\le 10^9\).

Phân nhóm

Grader mẫu

Grader mẫu đọc \(N,Q\), dãy \(A\), rồi \(Q\) dòng p v. Grader in kết quả của initialize, sau đó in kết quả của từng lần cập nhật, mỗi kết quả trên một dòng.

4 0
1 1 1 1

4

12 0
8 9 7 9 2 3 2 8 4 6 2 6

18

7 2
1 3 4 4 2 1 6
3 1
3 2

7
9
8

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 1, giấy phép CC BY-NC-SA 4.0.