Vị Trí Lớn Nhất · canuc80k2806 · Thuật toán Canuc80k

Description

Có một mảng ẩn gồm $n$ số đôi một khác nhau. Với truy vấn trên đoạn $[l, r]$ có ít nhất hai phần tử, bộ tương tác trả về chỉ số trong toàn mảng của phần tử lớn thứ hai trong đoạn đó.

Hãy tìm chỉ số của phần tử lớn nhất toàn mảng bằng không quá $40$ truy vấn. Giá trị cụ thể của các phần tử không được tiết lộ và không thay đổi trong 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$ . Truy vấn có dạng ? l r với $1 \leq l < r \leq n$ . Đáp án có dạng ! p, trong đó $p$ là chỉ số phần tử lớn nhất. Phải flush sau mỗi dòng.

Mỗi truy vấn hợp lệ nhận chỉ số toàn cục của phần tử lớn thứ hai trong $a_{l}, \dots, a_{r}$ . Mảng ẩn không thay đổi theo truy vấn; có tối đa $40$ truy vấn.

Đáp án đúng nhận AC, đáp án sai nhận WA. Sai cú pháp, đoạn không hợp lệ hoặc vượt ngân sách là lỗi giao thức. 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

$2 \leq n \leq 1 0^{5}$ . Các phần tử ẩn đôi một khác nhau. Mỗi truy vấn phải có $1 \leq l < r \leq n$ và có tối đa $40$ 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: 7
Lời giải -> Bộ tương tác: ? 1 7
Bộ tương tác -> Lời giải: 6
Lời giải -> Bộ tương tác: ? 1 6
Bộ tương tác -> Lời giải: 6
Lời giải -> Bộ tương tác: ? 3 6
Bộ tương tác -> Lời giải: 4
Lời giải -> Bộ tương tác: ? 2 6
Bộ tương tác -> Lời giải: 6
Lời giải -> Bộ tương tác: ! 2
Kết quả: AC

Giải thích: Truy vấn toàn mảng trả vị trí 6, là phần tử lớn thứ hai. Truy vấn $[1, 6]$ vẫn trả 6 nên cực đại ở bên trái; hai truy vấn nhị phân tiếp theo giữ lại duy nhất vị trí 2.

Ý tưởng: # Lời giải
Ý tưởng: ## Ý tưởng
Ý tưởng: Hỏi toàn mảng để biết vị trí s của phần tử lớn thứ hai toàn cục. Một truy vấn chứa s cho kết quả s đúng khi đoạn đó đồng thời chứa phần tử lớn nhất; dùng tính chất này để xác định phía rồi nhị phân vị trí cực đại.
Ý tưởng: ## Các bước
Ý tưởng: 1. Hỏi [1,n], nhận vị trí s của phần tử lớn thứ hai toàn cục. 2. Nếu s>1, hỏi [1,s]. Kết quả bằng s khi và chỉ khi cực đại nằm bên trái s; nếu không thì cực đại nằm bên phải. Khi s=1, cực đại bắt buộc ở bên phải. 3. Ở phía đã chọn, nhị phân bằng các đoạn luôn chứa s. Kết quả bằng s chính là dấu hiệu đoạn đang hỏi còn chứa cực đại. 4. In vị trí duy nhất còn lại.
Ý tưởng: ## Chứng minh tính đúng đắn
Ý tưởng: Ngoài phần tử lớn nhất toàn cục, không phần tử nào lớn hơn phần tử tại s. Do đó, trong mọi đoạn chứa s, s là phần tử lớn thứ hai của đoạn nếu và chỉ nếu đoạn cũng chứa cực đại toàn cục. Các đoạn được dùng trong nhị phân lồng nhau theo một phía của s, nên mệnh đề “đoạn chứa cực đại” là đơn điệu. Mỗi bước giữ đúng nửa chứa cực đại; khi còn một vị trí, đó chính là đáp án.
Ý tưởng: ## Giới hạn truy vấn và độ phức tạp
Ý tưởng: Dùng không quá 2+⌈log2 n⌉ truy vấn, nhỏ hơn 40 với n≤10^5. Thời gian và bộ nhớ phía lời giải là O(log n) và O(1), ngoài chi phí giao tiếp.