#P6767. [2019备战noi]djq和mz
[2019备战noi]djq和mz
djq 和 MZ
题目描述
有 个 MZ 排成一排,类型编号为 到 。第 个 MZ 的类型为 ,魅力值为 。
有 次询问,每次给出 。对于类型范围 中的每一种类型,计算它在位置区间 内的魅力值总和,输出这些总和的最大值,即
$$\max_{v_l\le c\le v_r} \left( \sum_{\substack{l\le j\le r\\a_j=c}}b_j \right).$$若某种类型在该位置区间中没有出现,则对应总和为 。
输入格式
第一行三个整数 。
第二行 个整数 。
第三行 个整数 。
接下来 行,每行四个整数 ,表示一次询问。
输出格式
对每次询问,输出一行一个整数,表示答案。
样例输入
5 3 3
1 2 3 3 2
1 1 2 1 2
1 4 1 3
1 4 1 2
2 3 1 1
样例输出
3
1
0
样例解释
第一次询问中,类型 的魅力值总和为 ,最大;第二次询问只考虑类型 ,它们的总和都为 ;第三次询问中没有类型 ,答案为 。
数据范围
所有数据满足
$$1\le n,m,q\le10^5,\qquad 1\le a_i\le m,\qquad 1\le l\le r\le n,\qquad 1\le v_l\le v_r\le m.$$魅力值 按完整十进制整数读取,可以为负数。没有出现的类型的总和仍为0;若查询范围内的每种类型均出现且总和均为负数,答案也可以为负数。该定义直接按题面给定的求和与最大值计算,不额外猜填数值上界。
- 的数据满足 。
- 的数据满足 。
- 的数据满足 。
- 的数据满足 。
- 另外 的数据满足 。
- 另外 的数据满足 。
- 另外 的数据满足 ,且 数组随机构造。
本地编译标程
随题提供 exact_integer.h,与标程放在同一目录,可用C++17编译。