| Time Limit | $2$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $5$ | 正确数量 | $3$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。
每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。
奈文摩尔有 nnn 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 111 到 nnn。第 iii 个灵魂的战斗力为 kik_iki，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对 i,j(i
影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间 [a,b][a,b][a,b]，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑所有满足 a≤i
顺带一提，灵魂的战斗力组成一个 111 到 nnn 的排列：k1,k1,⋯,knk_1, k_1, \cdots, k_nk1,k1,⋯,kn。
第一行四个整数 n,m,p1,p2n,m,p_1,p_2n,m,p1,p2；
第二行 nnn 个整数数：k1,k2,⋯,knk_1, k_2,\cdots, k_nk1,k2,⋯,kn；
接下来 mmm 行,每行两个数 a,ba,ba,b，表示询问区间 [a,b][a,b][a,b] 中的灵魂对会为影魔提供多少攻击力。
共输出 mmm 行，每行一个答案，依次对应 mmm 个询问。
10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
30
39
4
13
16
对于 30%30\%30% 的数据，1≤n,m≤5001\le n, m\le 5001≤n,m≤500；
另有 30%30\%30% 的数据，p1=2p2p_1 = 2p_2p1=2p2；
对于 100%100\%100% 的数据，1≤n,m≤200000,1≤p1,p2≤10001\le n,m\le 200000, 1\le p_1, p_2\le 10001≤n,m≤200000,1≤p1,p2≤1000。
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$1092 $ms] | 范晋豪@信息与计算科学142 | 108902 | 2017-07-02 23:21:10 |
| 内存最少[$27128 $KB] | sqrjy | 607432 | 2020-07-16 09:49:33 |
| 第一AC | 范晋豪@信息与计算科学142 | 108902 | 2017-07-02 23:21:10 |
| 第一挑战 | 范晋豪@信息与计算科学142 | 108902 | 2017-07-02 23:21:10 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|