{"problem":{"name":"E. Eyes Closed","description":{"content":"Vasya and Petya were tired of studying so they decided to play a game. Before the game begins Vasya looks at array _a_ consisting of _n_ integers. As soon as he remembers all elements of _a_ the game ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF895E"},"statements":[{"statement_type":"Markdown","content":"Vasya and Petya were tired of studying so they decided to play a game. Before the game begins Vasya looks at array _a_ consisting of _n_ integers. As soon as he remembers all elements of _a_ the game begins. Vasya closes his eyes and Petya does _q_ actions of one of two types:\n\n1) Petya says 4 integers _l_1, _r_1, _l_2, _r_2 — boundaries of two non-intersecting segments. After that he swaps one random element from the \\[_l_1, _r_1\\] segment with another random element from the \\[_l_2, _r_2\\] segment.\n\n2) Petya asks Vasya the sum of the elements of _a_ in the \\[_l_, _r_\\] segment.\n\nVasya is a mathematician so he answers Petya the mathematical expectation of the sum of the elements in the segment.\n\nYour task is to write a program which will answer the second type questions as Vasya would do it. In other words your program should print the mathematical expectation of the sum of the elements of _a_ in the \\[_l_, _r_\\] segment for every second type query.\n\n## Input\n\nThe first line contains two integers _n_, _q_ (2 ≤ _n_ ≤ 105, 1 ≤ _q_ ≤ 105) — the number of elements in the array and the number of queries you need to handle.\n\nThe second line contains _n_ integers _a__i_ (1 ≤ _a__i_ ≤ 109) — elements of the array.\n\nThe next _q_ lines contain Petya's actions of type 1 or 2.\n\nIf it is a type 1 action then the line contains 5 integers 1, _l_1, _r_1, _l_2, _r_2 (1 ≤ _l_1 ≤ _r_1 ≤ _n_, 1 ≤ _l_2 ≤ _r_2 ≤ _n_).\n\nIf it is a type 2 query then the line contains 3 integers 2, _l_, _r_ (1 ≤ _l_ ≤ _r_ ≤ _n_).\n\nIt is guaranteed that there is at least one type 2 query and segments \\[_l_1, _r_1\\], \\[_l_2, _r_2\\] don't have common elements.\n\n## Output\n\nFor each type 2 query print one real number — the mathematical expectation of the sum of elements in the segment.\n\nYour answer will be considered correct if its absolute or relative error doesn't exceed 10 - 4 — formally, the answer is correct if where _x_ is jury's answer and _y_ is yours.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vasya 和 Petya 玩腻了学习，于是决定玩一个游戏。游戏开始前，Vasya 会查看一个包含 $n$ 个整数的数组 $a$。一旦他记住了数组 $a$ 的所有元素，游戏就开始。Vasya 闭上眼睛，Petya 执行 $q$ 次操作，每次操作属于以下两种类型之一：\n\n1) Petya 说出四个整数 $l1, r1, l2, r2$ —— 两个不相交区间的边界。之后，他从区间 $[l1, r1]$ 中随机选取一个元素，与从区间 $[l2, r2]$ 中随机选取的另一个元素进行交换。\n\n2) Petya 询问 Vasya 区间 $[l, r]$ 中数组 $a$ 元素的和。\n\nVasya 是一位数学家，因此他回答的是该区间元素和的数学期望。\n\n你的任务是编写一个程序，像 Vasya 那样回答第二类查询。换句话说，对于每一个第二类查询，你的程序应输出区间 $[l, r]$ 中元素和的数学期望。\n\n第一行包含两个整数 $n, q$ ($2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5$) —— 数组元素个数和需要处理的查询数量。\n\n第二行包含 $n$ 个整数 $a_i$ ($1 ≤ a_i ≤ 10^9$) —— 数组的元素。\n\n接下来的 $q$ 行包含 Petya 的类型 1 或类型 2 的操作。\n\n如果是类型 $1$ 的操作，该行包含 $5$ 个整数 $1, l1, r1, l2, r2$ ($1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n$)。\n\n如果是类型 $2$ 的查询，该行包含 $3$ 个整数 $2, l, r$ ($1 ≤ l ≤ r ≤ n$)。\n\n保证至少存在一个类型 $2$ 的查询，且区间 $[l1, r1]$ 和 $[l2, r2]$ 没有公共元素。\n\n对于每个类型 $2$ 的查询，输出一个实数 —— 区间内元素和的数学期望。\n\n你的答案若绝对误差或相对误差不超过 $10^{-4}$，则被视为正确 —— 即，当 $x$ 为标准答案，$y$ 为你输出的答案时，若满足 $|x - y| \\leq 10^{-4} \\cdot \\max(1, |x|)$，则答案正确。\n\n## Input\n\n第一行包含两个整数 $n, q$ ($2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5$) —— 数组元素个数和需要处理的查询数量。第二行包含 $n$ 个整数 $a_i$ ($1 ≤ a_i ≤ 10^9$) —— 数组的元素。接下来的 $q$ 行包含 Petya 的类型 1 或类型 2 的操作。如果是类型 $1$ 的操作，该行包含 $5$ 个整数 $1, l1, r1, l2, r2$ ($1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n$)。如果是类型 $2$ 的查询，该行包含 $3$ 个整数 $2, l, r$ ($1 ≤ l ≤ r ≤ n$)。保证至少存在一个类型 $2$ 的查询，且区间 $[l1, r1]$ 和 $[l2, r2]$ 没有公共元素。 \n\n## Output\n\n对于每个类型 $2$ 的查询，输出一个实数 —— 区间内元素和的数学期望。你的答案若绝对误差或相对误差不超过 $10^{-4}$，则被视为正确 —— 即，当 $x$ 为标准答案，$y$ 为你输出的答案时，若满足 $|x - y| \\leq 10^{-4} \\cdot \\max(1, |x|)$，则答案正确。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the array length and number of queries.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial array of integers.  \nLet $ \\mathbb{E}[a_i^{(t)}] $ denote the expected value of the element at position $ i $ after $ t $ operations.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 10^5 $, $ 1 \\le q \\le 10^5 $  \n2. $ 1 \\le a_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. For type-1 queries: $ 1 \\le l_1 \\le r_1 \\le n $, $ 1 \\le l_2 \\le r_2 \\le n $, $ [l_1, r_1] \\cap [l_2, r_2] = \\emptyset $  \n4. For type-2 queries: $ 1 \\le l \\le r \\le n $  \n\n**Objective**  \nProcess $ q $ queries:  \n- **Type 1** ($ 1, l_1, r_1, l_2, r_2 $):  \n  Let $ S_1 = [l_1, r_1] $, $ S_2 = [l_2, r_2] $.  \n  Randomly select $ i \\in S_1 $, $ j \\in S_2 $ uniformly and swap $ a_i \\leftrightarrow a_j $.  \n  Update expectations:  \n  $$\n  \\mathbb{E}[a_i^{(t+1)}] = \\mathbb{E}[a_i^{(t)}] \\cdot \\left(1 - \\frac{1}{|S_1|}\\right) + \\frac{1}{|S_2|} \\sum_{k \\in S_2} \\mathbb{E}[a_k^{(t)}] \\cdot \\frac{1}{|S_1|}, \\quad \\forall i \\in S_1\n  $$  \n  $$\n  \\mathbb{E}[a_j^{(t+1)}] = \\mathbb{E}[a_j^{(t)}] \\cdot \\left(1 - \\frac{1}{|S_2|}\\right) + \\frac{1}{|S_1|} \\sum_{k \\in S_1} \\mathbb{E}[a_k^{(t)}] \\cdot \\frac{1}{|S_2|}, \\quad \\forall j \\in S_2\n  $$  \n\n- **Type 2** ($ 2, l, r $):  \n  Output:  \n  $$\n  \\sum_{i=l}^{r} \\mathbb{E}[a_i]\n  $$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF895E","tags":["data structures","probabilities"],"sample_group":[["4 4\n1 1 2 2\n1 2 2 3 3\n2 1 2\n1 1 2 3 4\n2 1 2","3.0000000\n3.0000000"],["10 5\n1 1 1 1 1 2 2 2 2 2\n1 1 5 6 10\n2 1 5\n1 1 5 6 10\n1 1 5 6 10\n2 6 10","6.0000000\n8.0400000"],["10 10\n1 2 3 4 5 6 7 8 9 10\n1 1 5 6 10\n1 1 5 6 10\n2 1 5\n1 1 3 6 9\n2 1 3\n1 5 7 8 10\n1 1 1 10 10\n2 1 5\n2 7 10\n2 1 10","23.0000000\n14.0000000\n28.0133333\n21.5733333\n55.0000000"]],"created_at":"2026-03-03 11:00:39"}}