#HTR002D. 丑国传说 · 丑国旅游

丑国传说 · 丑国旅游

题目背景

丑国风景优美,是远近有名的旅游胜地(并不)。来丑国旅游的人很多。

题目描述

丑国的一角排列着编号从 11nnnn 个城市。当一个人在第 ii 个城市时,能且仅能走到第 i+1i+1 个城市。

ii 个城市中的人们最讨厌丑值为 aia_i 的人。当一个丑值为 xx 的人从第 ii 个城市走到第 i+1i+1 个城市时,他会获得 xai×xai+1|x-a_i|\times|x-a_{i+1}| 的舒适值。

现在有 mm 个人要来丑国旅游,第 ii 个人的丑值为 xix_i,要从城市 lil_i 走到 rir_i,问他得到的舒适值之和是多少。

由于这个数可能很大,你需要求出对 109+710^9+7 取模后的值。

由于你不能预知到下一次旅游,我们会强制你在线。

简化版题意:

给出 nnnn 个整数 a1,a2,,ana_1,\,a_2,\,\dots,\,a_n

mm 次在线询问,每次询问给出 x,l,rx,\,l,\,r,求 i=lr1xai×xai+1\sum\limits_{i=l}^{r-1}|x-a_i|\times|x-a_{i+1}|

输入

第一行输入两个整数 n,mn,m,分别表示城市数与旅游人数。

第二行输入 nn 个整数,第 ii 个数表示 aia_i,含义如上所述。

接下来 mm 行,每行输入三个整数 X,L,RX,L,R,记上一次的旅游的总舒适值对 109+710^9+7 取模后为 ss(若是第一次询问,则 s=0s=0),则 xi=Xxors,li=Lxors,ri=Rxorsx_i=X\operatorname{xor}s,l_i=L\operatorname{xor}s,r_i=R\operatorname{xor}s,其中 xor\operatorname{xor} 表示异或,而 xi,li,rix_i,l_i,r_i 的含义如上所述。

输出

输出 mm 行,第 ii 行的数表示第 ii 个人的总舒适值对 109+710^9+7 取模后的值。

5 2
1 2 3 4 5
1 1 3
6 1 7
2
0

对于第一次询问,从城 1 走到城 2,获得舒适值为 11×12=0|1-1|\times|1-2|=0;从城 2 走到城 3,获得舒适值为 12×13=2|1-2|\times|1-3|=2,故总舒适值为 22

对于第二次询问,解密后的 x,l,rx,l,r 分别是 4,3,54,3,5。从城 3 走到城 4,获得舒适值为 43×44=0|4-3|\times|4-4|=0;从城 4 走到城 5,舒适值为 44×45=0|4-4|\times|4-5|=0,总舒适值为 00


数据规模与约定

本题采用捆绑测试。

编号 特殊限制 分值 时限
Subtask0 n,m104n,m\le 10^4 20pts 1s
Subtask1 ai,x10a_i,x\le 10 10pts 2s
Subtask2 aia_i 单调递增
Subtask3 无特殊限制 60pts

对于 100%100\% 的数据,1n,m3×1051 \le n,m \le 3 \times 10^51ai,xi1091 \le a_i,x_i \le 10^91li<rin1 \le l_i < r_i \le n