T1

题目描述

有 \(n\) 个人站成一行，每个人有一个魅力值，相同魅力值的人会形成一个团伙，你出于对于社会和谐发展的考虑，定义一个团伙正常当且仅当团伙人数为 \(2\)，现在你的任务就是回答 \(M\) 个询问，每次询问一个区间 \([L, R]\)，你需要回答这个区间中所有人各自结成团伙后，处于不正常团伙中的人的魅力值之和。

输入格式

第一行两个数 \(n, M\)，分别表示人数与询问数。

接下来一行 \(n\) 个数，分别表示每个人的魅力值。

接下来 \(M\) 行每行两个数 \(L, R\)，表示一个询问。

输出格式

对于每一个询问，输出一行表示答案。

输入样例

5 5
4 3 3 4 1
1 1
1 4
1 2
1 5
2 3

输出样例

4
0
7
1
0

数据规模

对于 \(20\%\) 数据，\(n \leq 500, m \leq 500\)。

对于 \(50\%\) 数据，\(n \leq 10000, m \leq 10000\)。

对于 \(100\%\) 数据，\(n \leq 10^5, m \leq 10^5, a_i \leq 10^5\)。

T2

题目描述

有一个长相惊奇的国家……

可以猜到，这个国家有 \(N\) 个城市，每个城市之间有且仅有一条通路。

可以猜到，这个国家是长在树上的。

可以猜到，首都是 \(1\) 号结点。

可以猜到，每个城市管辖它子树中的所有城市。

可以猜到，每个城市有一个权值 \(A\)，两个城市的通讯难度为两城市路径异或和。

可以猜到，一个城市的繁忙度定义为它所管辖的城市中通讯难度最大的两个城市的通讯难度。

可以猜到，还有一点特别需要注意，如果两个城市 \(x, y\) 都在 \(a\) 的子树中，但是 \(\operatorname{lca}(x, y) \neq a\)，那么这两个城市不参与 \(a\) 的繁忙度统计。

可以猜到，这道题你只需要输出所有城市的繁忙度即可。

可以猜到，这道题是水题……

输入格式

第一行一个数 \(N\)。

第二行 \(N\) 个数，表示点权 \(A_i\)。

接下来 \(N - 1\) 个数，表示树上的一条边，默认 \(1\) 号节点为根。

输出格式

\(1\) 行 \(N\) 个数，表示每个节点的子树中异或和最大的路径异或和。

输入样例

5
1775 6503 8147 2354 8484
1 2
1 3
3 4
1 5

输出样例

16044 6503 8147 2354 8484

数据规模

对于 \(30\%\) 数据，\(n \leq 100\)。

对于 \(100\%\) 数据，\(n \leq 100000\)。

T3

题目描述

我们定义一个不正常序列。

\(F_1 = 1\)

\(F_i = (a \times M_i + b \times i + c) \bmod (10^9 + 7)\)。

在这里，\(M_i\) 是指数列 \(F_1, F_2, \dots, F_{i - 1}\) 的中位数。

一个数列的中位数是当这个数列排好序后数列最中间的那个数，如果数列一共有偶数项，那么定义较小的那个为它的中位数。

对于给定的 \(a, b, c, n\)，求 \(\displaystyle\sum_{i=1}^n F_i\)。

输入格式

仅一行，\(a, b, c, n\)。

输出格式

一行表示数列的和。

输入样例

5 6 7 2

输出样例

25

数据规模

对于 \(30\%\) 数据，\(n \leq 50\)。

对于 \(100\%\) 数据，\(n \leq 10^6, 0 \leq a, b, c \leq 10^9 + 7\)