Hai trạng thái của cùng dữ liệu

Bối cảnh

Một tập dữ liệu cần được phân tích theo hai cách. Nhóm A quan tâm đến thứ tự thời gian gốc và hỏi tổng trên đoạn index [L,R] của input. Nhóm B coi dữ liệu như một phân phối giá trị, sort tăng dần rồi hỏi tổng trên đoạn rank [L,R] của state đã sort. Hai loại truy vấn có cùng công thức prefix nhưng khác state.

Bài Medium cố ý tạo nguy cơ state mismatch: nếu chỉ giữ một prefix rồi sort dữ liệu, một trong hai nhóm query sẽ nhận kết quả sai. Hãy duy trì hai prefix độc lập: preOriginal build trước sort và preSorted build sau sort. Đây chính là bài học quan trọng của B18: mỗi derived structure phải ghi rõ nó mô tả state nào.

Điểm đánh lừa là cả hai nhóm query đều dùng hai số L,R và đều hỏi "tổng đoạn", nên code rất dễ gọi nhầm prefix. Một cách thiết kế chắc chắn là đặt tên state rõ ràng (original, sorted) và không tái sử dụng cùng vector cho hai ý nghĩa. Khi đọc đề contest dài, thói quen gắn mỗi derived array với một state cụ thể giúp giảm rất nhiều lỗi logic.

Yêu cầu

1. Đọc n và dãy.
2. Build prefix cho thứ tự gốc.
3. Tạo bản sao, sort tăng và build prefix cho state sorted.
4. Query ORIG L R dùng index 0-based.
5. Query SORTED L R dùng rank 1-based.

Input

Dòng 1 n; dòng 2 n số; dòng q; q lệnh.

Output

Mỗi query một dòng tổng.

Ràng buộc

1≤n,q≤5000, chỉ số/rank hợp lệ.

Ví dụ 1

Input

5
5 1 4 2 3
6
ORIG 0 1
SORTED 1 2
ORIG 1 3
SORTED 3 5
ORIG 0 4
SORTED 1 5

Output

6
3
7
12
15
15

Giải thích

Original là 5 1 4 2 3, còn sorted là 1 2 3 4 5. ORIG 0 1 tính 5+1=6; SORTED 1 2 tính hai rank nhỏ nhất 1+2=3. ORIG 1 3 là 1+4+2=7, trong khi SORTED 3 5 là 3+4+5=12. Tổng toàn bộ ở cả hai state đều 15, nên hai query cuối cùng cùng cho 15.

Ví dụ 2

Input

1
7
2
ORIG 0 0
SORTED 1 1

Output

7
7

Giải thích

Chỉ có một phần tử 7 nên state original và sorted giống nhau. ORIG 0 0 dùng prefix original và SORTED 1 1 dùng prefix sorted, nhưng cả hai đều lấy đúng một phần tử 7, nên hai dòng output đều là 7.

Thông tin học tập

• Module: M05
• Buổi: B18
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: prefix sum, original state, sorted state, state consistency, query dispatch
• Giới hạn kiến thức: B01-B18
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100