#P6985. [2019年余姚中学集训]Radio Ga Ga

    ID: 6816 传统题 3000ms 888MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>动态规划数据结构计算几何扫描线贪心CF2300平衡树排序构造

[2019年余姚中学集训]Radio Ga Ga

Radio Ga Ga

题目描述

Roger是个长得有点帅的鼓手,"Radio Ga Ga"就是他为Queen所作的词曲作品。

Roger想起来了儿时躺在家中听着收音机的日子,为了记下那些日子,作为一个高智商的(牙医)鼓手,他决定用自己喜欢的架子鼓来做点有意思的事情。

Roger一共有 nn 个架子鼓(如果要问他为什么能弹 10910^9 个鼓,那可能是因为他比较帅吧),排成一排,编号 1,…,n1,\ldots,n。

他先选择第 ss 个鼓。此后,假设已经打过的鼓恰为区间 [l,r][l,r],下一次可以选择:

  • 若 l>1l>1,打第 l−1l-1 个鼓;
  • 若 r<nr<n,打第 r+1r+1 个鼓。

直到所有鼓都打过才结束。

有 mm 条特殊情况。第 ii 条为:如果第 kik_i 次打的是第 xix_i 个鼓,获得 wiw_i 点愉悦值。总愉悦值为所有满足情况的 wiw_i 之和。

有 qq 个独立询问,每次指定起始鼓 sis_i,求能够获得的最大总愉悦值。答案对 109+710^9+7 取模后输出。

两种打鼓顺序 a,ba,b 不同,当且仅当存在 i∈[1,n]i\in[1,n] 使得 ai≠bia_i\ne b_i。

输入格式

从标准输入读入。第一行三个整数 n,m,qn,m,q。

接下来 mm 行,每行三个整数 ki,xi,wik_i,x_i,w_i,表示一条特殊情况。

接下来 qq 行,每行一个整数 sis_i。

输出格式

向标准输出写出 qq 行,每行一个整数,表示该次询问的最大总愉悦值对 109+710^9+7 取模的结果。

样例输入1

7 7 7
1 7 3
1 3 80
4 1 9
4 5 83
2 2 28
2 1 26
5 2 92
1
2
3
4
5
6
7

样例输出1

28
83
191
92
92
92
3

数据范围

采用捆绑测试。所有数据满足 1≤n≤1091\le n\le10^9,1≤m,q≤5×1051\le m,q\le5\times10^5,0≤wi≤1090\le w_i\le10^9,1≤ki,xi,si≤n1\le k_i,x_i,s_i\le n。

不存在两条特殊情况满足 ki=kjk_i=k_j 且 xi=xjx_i=x_j。

子任务 分数 特殊限制
1 10 n≤20n\le20
2 20 n,m,q≤1000n,m,q\le1000
3 10 m,q≤1000m,q\le1000
4 20 m,q≤105m,q\le10^5
5 m,q≤3×105m,q\le3\times10^5
6 无额外限制