{"problem":{"name":"[NOI2022] 二次整数规划问题","description":{"content":"本题中，你需要解决一个著名的 NP 问题——二次整数规划问题。 二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的**整数**序列 $(x_1, x_2, \\ldots, x_n)$，满足下文中的所有条件。 二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束： 1. 一类约束是单个变量取值的约束：给出正整数 $k$（$3 \\leq k \\leq 5$）和 $n$ 个区间 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8501"},"statements":[{"statement_type":"Markdown","content":"本题中，你需要解决一个著名的 NP 问题——二次整数规划问题。\n\n二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的**整数**序列 $(x_1, x_2, \\ldots, x_n)$，满足下文中的所有条件。\n\n二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束：\n\n1. 一类约束是单个变量取值的约束：给出正整数 $k$（$3 \\leq k \\leq 5$）和 $n$ 个区间 $[l_i, r_i]$（$1 \\leq i \\leq n$），其中 $1 \\leq l_i \\leq r_i \\leq k$，你给出的序列需要满足 $\\forall 1 \\leq i \\leq n$，$l_i \\leq x_i \\leq r_i$；\n2. 另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i, q_i, b_i)$，你给出的序列需要满足 $\\forall 1 \\leq j \\leq m$，$\\lvert x_{p_j} - x_{q_j} \\rvert \\leq b_j$。\n\n二次整数规划问题要有目标函数：在给出 $k-2$ 个目标参数 $v_2,v_3,\\dots,v_{k-1}$（**注意下标范围为 $\\boldsymbol{2}$ 至 $\\boldsymbol{k-1}$**）的前提下，对于一个值域为 $[1,k]$ 的整数数列 $\\{p_1,p_2,\\dots,p_n\\}$，设 $c_i$ 为该序列中取值为 $i$ 的元素个数，$G$ 为满足 $1 \\leq i,j \\leq n$ 且 $|p_i-p_j|\\leq 1$ 的整数二元组 $(i, j)$ 个数，**注意当 $\\boldsymbol{i \\neq j}$ 时，$\\boldsymbol{(i, j)}$ 与 $\\boldsymbol{(j, i)}$ 是不同的二元组**。定义该序列的**权值**为\n\n$$ W(p_1, p_2, \\ldots, p_n) = 10^6 G+\\sum_{i=2}^{k-1} c_i v_i \\text{。} $$\n\n你的序列需要在满足以上两类约束的情况下，最大化其权值。在给出的约束下，保证存在满足约束的序列。\n\n二次整数规划问题不一定要有多组询问，但是我们会给出 $q$ 次询问，每次询问给出不同的权值参数 $v_2, v_3, \\ldots, v_{k-1}$，对于每组询问你需要找到满足约束的最大化权值的序列。为了减少输出量，你只需要输出这个序列的权值。\n\n## Input\n\n**本题有多组测试数据。** 第一行一个非负整数和一个正整数 $C, T$，分别表示测试点编号和测试数据数量。$C = 0$ 表示该组数据为样例。\n\n对于每组测试数据，第一行四个整数 $k, n, m, q$，描述序列值域、序列长度、变量之间约束的个数和询问次数。\n\n接下来 $n$ 行每行两个整数 $l_i, r_i$，描述序列中每个元素对应的取值区间。\n\n接下来 $m$ 行每行三个整数 $p_j, q_j, b_j$，描述一个变量之间的约束。\n\n接下来 $q$ 行每行 $k - 2$ 个非负整数 $v_2, v_3, \\ldots, v_{k - 1}$ 描述一组询问的权值参数。\n\n## Output\n\n对于每组数据的每组询问输出一行一个整数，表示序列权值的最大值。\n\n[samples]\n\n## Note\n\n**【样例 \\#1】**\n\n见附件中的 `qip/qip1.in` 与 `qip/qip1.ans`。\n\n该样例满足数据范围中测试点 $1$ 的性质。\n\n----\n\n**【样例解释 \\#1】**\n\n第一个测试数据中两组询问对应的最优序列均为 $(1, 2, 2, 1, 3)$，有 $c_2 = 2, G = 21$。\n\n----\n\n**【样例 \\#2】**\n\n见附件中的 `qip/qip2.in` 与 `qip/qip2.ans`。\n\n该样例满足数据范围中测试点 $3$ 的性质。\n\n----\n\n**【样例解释 \\#2】**\n\n第一个测试数据中两组询问对应的最优序列分别为 $(4,4,3,3)$ 和 $(4,3,2,2)$。\n\n----\n\n**【样例 \\#3】**\n\n见附件中的 `qip/qip3.in` 与 `qip/qip3.ans`。\n\n该样例满足数据范围中测试点 $5$ 的性质。\n\n----\n\n**【样例解释 \\#3】**\n\n第一个测试数据中三组询问对应的一个最优序列分别为 $(3, 3, 3, 3, 3)$、$(2, 2, 3, 3, 2)$ 和 $(3, 2, 4, 4, 2)$。\n\n----\n\n**【样例 \\#4】**\n\n见附件中的 `qip/qip4.in` 与 `qip/qip4.ans`。\n\n该样例满足数据范围中测试点 $2$ 的性质。\n\n----\n\n**【样例 \\#5】**\n\n见附件中的 `qip/qip5.in` 与 `qip/qip5.ans`。\n\n该样例满足数据范围中测试点 $4$ 的性质。\n\n----\n\n**【样例 \\#6】**\n\n见附件中的 `qip/qip6.in` 与 `qip/qip6.ans`。\n\n该样例满足数据范围中测试点 $8$ 的性质。\n\n----\n\n**【样例 \\#7】**\n\n见附件中的 `qip/qip7.in` 与 `qip/qip7.ans`。\n\n该样例满足数据范围中测试点 $14$ 的性质。\n\n----\n\n**【样例 \\#8】**\n\n见附件中的 `qip/qip8.in` 与 `qip/qip8.ans`。\n\n该样例满足数据范围中测试点 $17$ 的性质。\n\n----\n\n**【数据范围】**\n\n设 $\\sum q$ 为单个测试点中所有测试数据的 $q$ 的和。对于所有测试点，\n\n- $1 \\leq T \\leq 600$，\n- 第 $i$（$1 \\le i \\le T$）个测试数据中，$1 \\leq n \\leq \\max(\\frac{T}{i},2 \\log_2 T)$，\n- $3 \\leq k \\leq 5$，$0 \\leq m \\leq 3n$，$1 \\leq q,\\sum q \\leq 3 \\times 10^5$，\n- $1 \\leq l_i \\leq r_i \\leq k$，\n- $1 \\leq p_j,q_j \\leq n$，$0 \\leq b_j<k$，\n- $0 \\leq v_2,\\dots,v_{k-1} \\leq 10^{12}$。\n\n| 测试点编号 | $T \\leq$ | $k=$ | $\\sum q \\leq$   | 特殊性质         | 测试点分数 |\n|:-----:|:--------:|:----:|:---------------:|:------------:|:-----:|\n| $1$   | $10$     | $3$  | $200$           | 无            | $4$   |\n| $2$   | $600$    | $3$  | $3 \\times 10^5$ | 无            | $6$   |\n| $3$   | $10$     | $4$  | $200$           | 无            | $4$   |\n| $4$   | $600$    | $4$  | $3 \\times 10^5$ | 无            | $6$   |\n| $5$   | $10$     | $5$  | $300$           | 无            | $5$   |\n| $6$   | $15$     | $5$  | $500$           | 无            | $4$   |\n| $7$   | $25$     | $5$  | $750$           | 无            | $4$   |\n| $8$   | $50$     | $5$  | $1000$          | 无            | $6$   |\n| $9$   | $80$     | $5$  | $1500$          | 无            | $6$   |\n| $10$  | $120$    | $5$  | $2000$          | 无            | $5$   |\n| $11$  | $200$    | $5$  | $8000$          | A | $3$   |\n| $12$  | $400$    | $5$  | $3 \\times 10^4$ | A | $4$   |\n| $13$  | $600$    | $5$  | $2 \\times 10^5$ | A | $5$   |\n| $14$  | $200$    | $5$  | $8000$          | B | $3$   |\n| $15$  | $400$    | $5$  | $3 \\times 10^4$ | B | $4$   |\n| $16$  | $600$    | $5$  | $2 \\times 10^5$ | B | $4$   |\n| $17$  | $120$    | $5$  | $10^5$          | C | $4$   |\n| $18$  | $150$    | $5$  | $2 \\times 10^5$ | C | $5$   |\n| $19$  | $180$    | $5$  | $3 \\times 10^5$ | C | $5$   |\n| $20$  | $300$    | $5$  | $5 \\times 10^4$ | 无            | $5$   |\n| $21$  | $450$    | $5$  | $10^5$          | 无            | $4$   |\n| $22$  | $600$    | $5$  | $3 \\times 10^5$ | 无            | $4$   |\n\n特殊性质 A：$m=0$。\n\n特殊性质 B：$m \\leq 10$，单个测试点中所有测试数据的 $m$ 的和不超过 $200$。\n\n特殊性质 C：数据随机生成。具体地，生成测试点中每组测试数据时，给出参数 $k,n,m,q$ 以及 $k$ 个非负常数 $p_0,p_1,p_2,\\dots,p_{k-1}$，保证 $p_{k-1} \\neq 0$，则按照如下规则生成该组数据：\n\n- 对于 $1 \\leq i \\leq n$，独立均匀生成 $x,y \\in [1,k]$，则 $l_i=\\min(x,y),r_i=\\max(x,y)$；\n- 不断按照如下方式生成三元组直至有 $m$ 个三元组：\n  1. 独立均匀随机生成 $u,v \\in [1,n]$；\n  2. 以 $p$ 为权值随机生成 $w$（对于 $0 \\leq i \\leq k-1$，$w=i$ 的概率为 $\\frac{p_i}{p_0+p_1+\\dots+p_{k-1}}$）；\n  3. 若在原有三元组集合中加入 $(u,v,w)$ 后不存在序列 $(x_1,x_2,\\dots,x_n)$ 满足所有限制，则舍弃当前三元组，否则加入当前三元组。\n- 每组询问的 $v_2, \\ldots, v_{k-1}$ 在 $[0,10^{12}]$ 内独立均匀随机生成。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8501","tags":["2022","NOI","网络流","O2优化","分治","凸包","整数规划"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}