Căn Bậc Hai Theo Đoạn · canuc80k6600

Cho một dãy số nguyên không âm. Bạn cần xử lý hai loại thao tác trên các đoạn đóng của dãy.

Thao tác $0$ $X$ $Y$ : với mọi chỉ số từ $min (X, Y)$ đến $max (X, Y)$ , thay $a_{i}$ bằng số nguyên lớn nhất $z$ thỏa $z^{2} \leq a_{i}$ .
Thao tác $1$ $X$ $Y$ : tính tổng các phần tử trên chính đoạn đó.

Input có thể chứa nhiều bộ dữ liệu nối tiếp nhau và kết thúc ở EOF. Các bộ được đánh số từ $1$ .

Input

Mỗi bộ dữ liệu có dạng:
Dòng đầu chứa số nguyên $N$ .
Dòng tiếp theo chứa $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ .
Dòng tiếp theo chứa số nguyên $M$ .
$M$ dòng sau, mỗi dòng chứa ba số nguyên $t X Y$ mô tả một thao tác.
Không có số lượng bộ dữ liệu ở đầu input; hãy đọc đến hết tệp.

Output

Với bộ dữ liệu thứ $k$ , in dòng Case #k:. Sau đó, với mỗi thao tác loại $1$ , in tổng cần tìm trên một dòng. In thêm một dòng trống sau mỗi bộ dữ liệu.

Constraints

$1 \leq N, M \leq 1 0^{5}$ cho mỗi bộ dữ liệu.
$0 \leq a_{i} \leq 1 0^{18}$ và tổng của dãy luôn nằm trong kiểu số nguyên $64$ bit có dấu.
$1 \leq X, Y \leq N$ ; nếu $X > Y$ thì vẫn xét đoạn từ $Y$ đến $X$ .

Scoring

Subtask $1$ ( $50%$ số điểm): Trong mỗi bộ dữ liệu, $N, M \leq 2000$ và $a_{i} \leq 1 0^{6}$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Case #1:
42
10
5
2

Giải thích: Ban đầu tổng là $42$ . Sau khi lấy căn trên các đoạn tương ứng, dãy lần lượt trở thành $[0, 1, 4, 5]$ rồi $[0, 1, 2, 2]$ , nên ba tổng còn lại là $10, 5$ và $2$ .

Mô hình: Duy trì một dãy số nguyên không âm qua các phép lấy căn bậc hai nguyên trên đoạn và truy vấn tổng đoạn.
Thuật toán: Mỗi nút lưu tổng và cực đại. Khi cực đại không vượt 1, cả đoạn đã là điểm cố định của phép căn nên cập nhật dừng; nếu không, chỉ đi xuống những nhánh còn có thể đổi.
Thuật toán: Các truy vấn đọc kết quả từ các thống kê đã được duy trì. Mọi thao tác lazy đều được đẩy xuống trước khi tách nút, rồi nút cha được ghép lại từ hai con.
Tính đúng đắn: Ta chứng minh bằng quy nạp theo cây. Ở lá, giá trị lưu chính là giá trị hiện tại của phần tử. Ở một nút trong, điều kiện áp dụng nhanh chỉ được dùng khi thống kê của nút chứng minh rằng mọi phần tử chịu cùng một biến đổi; vì vậy cập nhật các trường tổng hợp là chính xác. Nếu điều kiện đó không đúng, thuật toán đẩy tag, xử lý hai con và ghép lại, nên giả thiết quy nạp cho kết quả đúng. Các nhánh bị bỏ qua đều nằm ngoài đoạn hoặc đã được chứng minh là bất biến. Do đó mọi cập nhật và truy vấn đều đúng theo contract.
Độ phức tạp: O((N+M) log N log log V) theo amortized; bộ nhớ O(N).