#P6767. [2019备战noi]djq和mz

    ID: 6587 传统题 1500ms 512MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>数据结构博弈论CF2500莫队分块构造数学

[2019备战noi]djq和mz

djq 和 MZ

题目描述

有 nn 个 MZ 排成一排,类型编号为 11 到 mm。第 ii 个 MZ 的类型为 aia_i,魅力值为 bib_i。

有 qq 次询问,每次给出 l,r,vl,vrl,r,v_l,v_r。对于类型范围 [vl,vr][v_l,v_r] 中的每一种类型,计算它在位置区间 [l,r][l,r] 内的魅力值总和,输出这些总和的最大值,即

$$\max_{v_l\le c\le v_r} \left( \sum_{\substack{l\le j\le r\\a_j=c}}b_j \right).$$

若某种类型在该位置区间中没有出现,则对应总和为 00。

输入格式

第一行三个整数 n,m,qn,m,q。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n。

接下来 qq 行,每行四个整数 l,r,vl,vrl,r,v_l,v_r,表示一次询问。

输出格式

对每次询问,输出一行一个整数,表示答案。

样例输入

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

样例解释

第一次询问中,类型 33 的魅力值总和为 2+1=32+1=3,最大;第二次询问只考虑类型 1,21,2,它们的总和都为 11;第三次询问中没有类型 11,答案为 00。

数据范围

所有数据满足

$$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.$$

魅力值 bib_i 按完整十进制整数读取,可以为负数。没有出现的类型的总和仍为0;若查询范围内的每种类型均出现且总和均为负数,答案也可以为负数。该定义直接按题面给定的求和与最大值计算,不额外猜填数值上界。

  • 5%5\% 的数据满足 m=1m=1。
  • 10%10\% 的数据满足 n,m,q≤100n,m,q\le100。
  • 20%20\% 的数据满足 n,m,q≤1000n,m,q\le1000。
  • 30%30\% 的数据满足 n,m,q≤5000n,m,q\le5000。
  • 另外 10%10\% 的数据满足 r−l≤100r-l\le100。
  • 另外 10%10\% 的数据满足 m≤100m\le100。
  • 另外 20%20\% 的数据满足 n=mn=m,且 aa 数组随机构造。

本地编译标程

随题提供 exact_integer.h,与标程放在同一目录,可用C++17编译。