{"raw_statement":[{"iden":"statement","content":"Cánh đồng hoa ở Amsterdam được chia thành $N$ ô đất, mỗi ô đất được đánh số từ $1$ đến $N$.\n\nHai người làm vườn chăm chỉ low_ và lantrungseo được giao chăm sóc hoa trên những ô đất này. Vì là những người làm vườn yêu bộ môn giải thuật, đồng thời cũng vì có quá nhiều hoa màu, low_ và lantrungseo đã cùng đưa ra bài toán như sau:\n\nBan đầu trên ô đất thứ $i$ có $A_i$ bông hoa. Mỗi ngày, hai người làm vườn sẽ phải thực hiện một trong hai sự kiện sau theo danh sách cho trước:\n\n\"_1_\": Chọn ra hai chỉ số $l, r$ ($1 <= l <= r <= N$). Với mỗi $i$ thuộc đoạn $[ l, r ]$, trồng trên ô đất thứ $i$ số lượng hoa là $i -l + 1$. Ví dụ, nếu $N = 5$ và chọn $l = 2$ và $r = 4$, thì trồng 1 bông trên ô đất 2, 2 bông trên ô đất 3, 3 bông trên ô đất 4.\n\n\"_2_\": Hai người làm vườn chán trồng hoa (nên sẽ không trồng thêm bông nào ngày hôm đó). Thay vì đó, low_ đố lantrungseo tính tổng số bông hoa trên các ô đất thuộc đoạn $[ u, v ]$ ($1 <= u <= v <= N$).\n\nBạn có danh sách các sự kiện diễn ra trong $Q$ ngày. Hãy giúp lantrungseo trả lời các sự kiện \"_2_\".\n\nDòng đầu chứa $T$ ($1 <= T <= 4$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:\n\n- Dòng đầu chứa $N$ ($1 <= N <= 10^5$) - số ô đất trên cánh đồng hoa.\n\n- Dòng thứ hai chứa $N$ số: $A_1, A_2,..., A_N$. ($0 <= A_i <= 10^6$) - số bông hoa trên từng cánh đồng.\n\n- Dòng thứ 3 chứa $Q$ ($1 <= Q <= 10^5$) - số sự kiện diễn ra trên cánh đồng.\n\n- $Q$ dòng tiếp theo, đầu mỗi dòng sẽ là một xâu thể hiện dạng sự kiện:\n\n+ \"_1_\": Sự kiện trồng thêm hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $l, r$ cách nhau bởi một dấu cách ($1 <= l <= r <= N$).\n\n+ \"_2_\": Sự kiện tính số lượng hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $u, v$ cách nhau bởi một dấu cách ($1 <= u <= v <= N$).\n\nVới mỗi sự kiện \"_2_\", in ra một số duy nhất là kết quả của sự kiện.\n\n20% số điểm ứng với $N <= 1000, Q <= 1000$.\n\n40% số điểm ứng với $N <= 10^5, Q <= 10^5$. Trong mỗi bộ test, truy vấn _\"1\"_ cuối cùng sẽ xuất hiện trước truy vấn _\"2\"_ đầu tiên.\n\n40% số điểm còn lại ứng với giới hạn gốc.\n\nBộ test thứ nhất:\n\nBan đầu: $2, 1, 3, 5, 2$\n\nSau ngày đầu tiên: $3, 3, 6, 5, 2$\n\nSau ngày thứ ba: $3, 3, 6, 6, 4$\n\nSau ngày thứ tư: $3, 4, 8, 9, 8$\n\nSau ngày thứ năm: $4, 4, 8, 9, 8$ \n\n"},{"iden":"input","content":"Dòng đầu chứa $T$ ($1 <= T <= 4$) - số bộ test trong file input. Mỗi bộ test sẽ có format như sau:- Dòng đầu chứa $N$ ($1 <= N <= 10^5$) - số ô đất trên cánh đồng hoa.- Dòng thứ hai chứa $N$ số: $A_1, A_2,..., A_N$. ($0 <= A_i <= 10^6$) - số bông hoa trên từng cánh đồng.- Dòng thứ 3 chứa $Q$ ($1 <= Q <= 10^5$) - số sự kiện diễn ra trên cánh đồng.- $Q$ dòng tiếp theo, đầu mỗi dòng sẽ là một xâu thể hiện dạng sự kiện:+ \"_1_\": Sự kiện trồng thêm hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $l, r$ cách nhau bởi một dấu cách ($1 <= l <= r <= N$).+ \"_2_\": Sự kiện tính số lượng hoa. Trên cùng một dòng, sau xâu này sẽ là hai số $u, v$ cách nhau bởi một dấu cách ($1 <= u <= v <= N$)."},{"iden":"output","content":"Với mỗi sự kiện \"_2_\", in ra một số duy nhất là kết quả của sự kiện."},{"iden":"scoring","content":"20% số điểm ứng với $N <= 1000, Q <= 1000$.40% số điểm ứng với $N <= 10^5, Q <= 10^5$. Trong mỗi bộ test, truy vấn _\"1\"_ cuối cùng sẽ xuất hiện trước truy vấn _\"2\"_ đầu tiên.40% số điểm còn lại ứng với giới hạn gốc."},{"iden":"note","content":"Bộ test thứ nhất:Ban đầu: $2, 1, 3, 5, 2$Sau ngày đầu tiên: $3, 3, 6, 5, 2$Sau ngày thứ ba: $3, 3, 6, 6, 4$Sau ngày thứ tư: $3, 4, 8, 9, 8$Sau ngày thứ năm: $4, 4, 8, 9, 8$ "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ (x_0, y_0) \\in \\mathbb{R}^2 $ be Dahlia’s position.  \nLet $ R \\in \\mathbb{Z}^+ $ be the maximum pull distance.  \nLet $ T = \\{ (x_i, y_i) \\in \\mathbb{R}^2 \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of $ N $ target positions, with $ (x_i, y_i) \\neq (x_0, y_0) $ for all $ i $, and all targets distinct.\n\n**Constraints**  \n1. $ |x_0|, |y_0| \\leq 10^9 $  \n2. $ 1 \\leq R \\leq 10^9 $  \n3. $ 1 \\leq N \\leq 5 \\times 10^5 $  \n4. $ (x_i, y_i) \\neq (x_0, y_0) $ for all $ i $, and $ (x_i, y_i) \\neq (x_j, y_j) $ for all $ i \\neq j $\n\n**Objective**  \nCount the number of targets $ (x_i, y_i) \\in T $ such that the Euclidean distance from $ (x_0, y_0) $ to $ (x_i, y_i) $ is at most $ R $:  \n$$\n\\left| \\left| (x_i - x_0, y_i - y_0) \\right| \\right|_2 \\leq R\n$$","simple_statement":"Dahlia is at point (x0, y0) and can pull any target within distance R.  \nCount how many targets are within distance R from her.","has_page_source":false}