#P15045. [2026省选联测]厨师

    ID: 14261 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400排序堆线段树贪心组合数学栈数据结构

[2026省选联测]厨师

题目描述

欧阳南德和上官琐艾经营着一家餐厅,这里有 nn 位厨师,编号从 11 到 nn。厨师 ii (1≤i≤n1 \le i \le n) 可以制作美味度为 aia_i 的锡尔潘乔和美味度为 bib_i 的皮克马乔。

然而,这些厨师都有很强的个性,因此有 mm 对厨师彼此不和。第 jj 对 (1≤j≤m1 \le j \le m) 不和的厨师是厨师 uju_j 和厨师 vjv_j。

来到这家餐厅的顾客会按以下方式用餐:

  • 选择满足 1≤p<q≤n1 \le p < q \le n 的整数 p,qp, q,并委托厨师 pp 和厨师 qq 这两人制作料理。但是,不能委托不和的两人组制作料理。
  • 锡尔潘乔和皮克马乔这两道菜都由厨师 pp 和厨师 qq 中能够做出更高美味度料理的那位厨师制作。如果对于某道菜,两人都能做出相同美味度的料理,则由其中一人制作。注意,一位厨师可以制作两道菜。
  • 顾客的满意度是锡尔潘乔的美味度和皮克马乔的美味度之和。

这家餐厅来了 qq 位顾客,编号从 11 到 qq。

顾客 kk (1≤k≤q1 \le k \le q) 会委托在所有可以委托的两人组中,满意度第 xkx_k 高的两人组制作料理。具体来说,如果满意度为 ss,则选择使得 s×n2+p×n+qs \times n^2 + p \times n + q 的值是第 xkx_k 高的厨师 pp 和厨师 qq (1≤p<q≤n1 \le p < q \le n) 两人组来制作料理。

欧阳南德和上官琐艾想请你帮忙计算每位顾客的满意度。

输入格式

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

第二行给出 nn 个整数 aia_i。

第三行给出 nn 个整数 bib_i。

接下来的 mm 行,每行给出两个整数 uiu_i 和 viv_i。

最后一行给出 qq 个整数 xix_i。

输出格式

输出 qq 行,第 kk 行输出第 kk 个顾客的满意度。

样例 #1

输入 #1

4 2 4
2 7 3 5
4 3 4 8
1 3
2 4
1 2 3 4

输出 #1

13
13
11
11

样例 #2

输入 #2

4 3 1
3 6 5 4
1 1 1 1
1 2
2 3
2 4
1

输出 #2

6

样例 1 解释

可以委托制作料理的厨师二人组有 44 种,每种组合的顾客满意度如下:

  • 选择厨师 11 和厨师 22 时,锡尔潘乔由厨师 22 制作,皮克马乔由厨师 11 制作。因此,锡尔潘乔的美味度为 77,皮克马乔的美味度为 44。所以,顾客的满意度为 7+4=117 + 4 = 11。
  • 选择厨师 11 和厨师 44 时,锡尔潘乔由厨师 44 制作,皮克马乔由厨师 44 制作。因此,锡尔潘乔的美味度为 55,皮克马乔的美味度为 88。所以,顾客的满意度为 5+8=135 + 8 = 13。
  • 选择厨师 22 和厨师 33 时,锡尔潘乔由厨师 22 制作,皮克马乔由厨师 33 制作。因此,锡尔潘乔的美味度为 77,皮克马乔的美味度为 44。所以,顾客的满意度为 7+4=117 + 4 = 11。
  • 选择厨师 33 和厨师 44 时,锡尔潘乔由厨师 44 制作,皮克马乔由厨师 44 制作。因此,锡尔潘乔的美味度为 55,皮克马乔的美味度为 88。所以,顾客的满意度为 5+8=135 + 8 = 13。

因此,对于每位顾客,可以得到以下信息:

  • 顾客 11 选择厨师 33 和厨师 44 的二人组。因此,顾客 11 的满意度为 1313。
  • 顾客 22 选择厨师 11 和厨师 44 的二人组。因此,顾客 22 的满意度为 1313。
  • 顾客 33 选择厨师 22 和厨师 33 的二人组。因此,顾客 33 的满意度为 1111。
  • 顾客 44 选择厨师 11 和厨师 22 的二人组。因此,顾客 44 的满意度为 1111。

样例 2 解释

可以委托制作料理的厨师二人组有 33 种,每种组合的顾客满意度如下:

  • 选择厨师 11 和厨师 33 时,锡尔潘乔由厨师 33 制作,皮克马乔由厨师 11 或厨师 33 制作。因此,锡尔潘乔的美味度为 55,皮克马乔的美味度为 11。所以,顾客的满意度为 5+1=65 + 1 = 6。
  • 选择厨师 11 和厨师 4 4 时,锡尔潘乔由厨师 44 制作,皮克马乔由厨师 11 或厨师 44 制作。因此,锡尔潘乔的美味度为 44,皮克马乔的美味度为 11。所以,顾客的满意度为 4+1=54 + 1 = 5。
  • 选择厨师 33 和厨师 4 4 时,锡尔潘乔由厨师 33 制作,皮克马乔由厨师 33 或厨师 44 制作。因此,锡尔潘乔的美味度为 5 5,皮克马乔的美味度为 11。所以,顾客的满意度为 5+1=65 + 1 = 6。

因此,对于顾客 11,可以得到以下信息:

  • 顾客 11 选择厨师 33 和厨师 44 的二人组。因此,顾客 11 的满意度为 66。

数据范围

  • 2≤n≤400 0002 \le n \le 400\,000,0≤m≤400 0000 \le m \le 400\,000,1≤q≤400 0001 \le q \le 400\,000;
  • 1≤ai,bi≤1091 \le a_i,b_i \le 10^9;
  • m<n(n−1)2m < \frac{n(n - 1)}{2},1≤uj<vj≤n1 \le u_j < v_j \le n。对于 i≠ji\neq j,(ui,vi)≠(uj,vj)(u_i, v_i) \neq (u_j, v_j);
  • 1≤xk≤400 0001 \le x_k \le 400\,000,xk≤n(n−1)2−mx_k \le \frac{n(n - 1)}{2} - m;
测试点编号 max⁡{n,m,q}≤\max\left\{n,m,q\right\}\le 特殊性质
11 5050 G
2∼32\sim 3 10510^5 ABC
4∼54\sim 5 AC
66 A
7∼147\sim 14 CD
15∼1715\sim 17 CE
18∼2218\sim 22 F
23∼2523\sim 25 4×1054\times 10^5 无
  • 特殊性质 A:保证 ∀i∈[1,n],bi=1\forall i\in [1,n],b_i=1;
  • 特殊性质 B:保证 m=0m=0;
  • 特殊性质 C:保证 q=1q=1;
  • 特殊性质 D:保证 x1=1x_1=1;
  • 特殊性质 E:保证 x1≤105x_1\le 10^5;
  • 特殊性质 F:保证 ∀i∈[1,n],xi≤105\forall i\in [1,n],x_i\le 10^5。
  • 特殊性质 G:保证 ∀i∈[1,n],xi≤50\forall i\in [1,n],x_i\le 50。