Số Không Thứ K · canuc80k2807 · Thuật toán Canuc80k

Description

Một mảng nhị phân ẩn có độ dài $n$ . Bạn được cho một số $k$ và cần tìm vị trí của số $0$ thứ $k$ khi duyệt từ trái sang phải.

Truy vấn ? l r trả tổng các bit trong đoạn $[l, r]$ , tức số lượng bit $1$ của đoạn. Đây là bản easy: $t = 1$ , nên chỉ có một giá trị $k$ và việc số $0$ vừa tìm được đổi thành $1$ sau đáp án không ảnh hưởng đến phiên.

Trạng thái ẩn được bộ tương tác chọn trước khi phiên bắt đầu và không thay đổi trong suốt phiên. Chương trình không được đọc trực tiếp trạng thái này; mọi thông tin chỉ đến từ các phản hồi hợp lệ theo giao thức bên dưới.

Interaction

Đầu phiên đọc $n$ và $t = 1$ , sau đó đọc $k$ . Truy vấn có dạng ? l r với $1 \leq l \leq r \leq n$ . Đáp án có dạng ! x, là vị trí số $0$ thứ $k$ . Phải flush sau mỗi dòng.

Mỗi truy vấn hợp lệ nhận tổng các bit $a_{l}$ +...+ $a_{r}$ . Có tối đa $20$ truy vấn; đáp án không tính vào ngân sách.

Đáp án đúng nhận AC; đáp án sai nhận WA. Truy vấn sai hoặc vượt ngân sách trả $- 1$ /lỗi giao thức và lời giải phải dừng ngay. Khi nhận $- 1$ hoặc khi luồng vào kết thúc bất thường, chương trình phải dừng ngay. Sau mỗi dòng gửi, chương trình phải đẩy dữ liệu khỏi bộ đệm, chẳng hạn bằng endl hoặc cout.flush() trong C++.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}, t = 1$ và $1 \leq k \leq n$ . Mảng ẩn luôn có ít nhất $k$ số $0$ tại thời điểm yêu cầu. Có tối đa $20$ truy vấn.

Scoring

Subtask $1$ ( $50%$ số điểm): mười hidden session đầu dùng kích thước nhỏ, tập trung kiểm tra mô hình giao thức và các trường hợp biên cơ bản.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung; mười hidden session còn lại dùng toàn bộ giới hạn, trong đó các session cuối kiểm tra cận trên của những đại lượng kích thước có hiệu lực.
Mỗi hidden session có giá trị $5$ điểm. Một session chỉ được tính điểm khi toàn bộ cuộc hội thoại kết thúc với verdict AC.

Example interaction

Mẫu E01

Bộ tương tác -> Lời giải: 8 1
Bộ tương tác -> Lời giải: 3
Lời giải -> Bộ tương tác: ? 1 4
Bộ tương tác -> Lời giải: 2
Lời giải -> Bộ tương tác: ? 1 6
Bộ tương tác -> Lời giải: 3
Lời giải -> Bộ tương tác: ? 1 5
Bộ tương tác -> Lời giải: 3
Lời giải -> Bộ tương tác: ! 6
Kết quả: AC

Giải thích: Mảng mẫu có các số 0 ở vị trí 2, 4, 6 và 7. Các truy vấn prefix cho biết prefix dài 4 mới có hai số 0, còn prefix dài 6 có ba số 0; lower_bound vì thế trả vị trí 6.

Ý tưởng: # Lời giải
Ý tưởng: ## Ý tưởng
Ý tưởng: Nhị phân vị trí nhỏ nhất p sao cho prefix [1,p] chứa ít nhất k số 0. Một truy vấn trả số bit 1; số bit 0 trong prefix bằng p trừ phản hồi.
Ý tưởng: ## Các bước
Ý tưởng: 1. Duy trì đoạn [l,r] chứa vị trí số 0 thứ k. 2. Với mid, hỏi tổng bit 1 trên [1,mid] rồi tính zeros=mid-ones. 3. Nếu zeros≥k thì đáp án không vượt mid; ngược lại đáp án lớn hơn mid. 4. Khi l=r, in vị trí đó.
Ý tưởng: ## Chứng minh tính đúng đắn
Ý tưởng: Gọi Z(p) là số bit 0 trong prefix dài p. Z(p) không giảm theo p, và vị trí số 0 thứ k chính là p nhỏ nhất thỏa Z(p)≥k. Mỗi truy vấn tính đúng Z(mid)=mid−sum(1..mid), nên phép cập nhật là lower_bound chuẩn và không loại đáp án. Khi hai biên gặp nhau, ta thu được đúng vị trí cần tìm.
Ý tưởng: ## Giới hạn truy vấn và độ phức tạp
Ý tưởng: Dùng ⌈log2 n⌉ truy vấn, tối đa 18 khi n≤2·10^5, dưới ngân sách 20. Thời gian O(log n), bộ nhớ O(1).