{"problem":{"name":"F2. Award from Wuhudsm(Hard Version)","description":{"content":"*This is the hard version of the problem. The changes in this version are highlighted in bold characters*. Yugandhar have an undirected graph containing $n$ nodes numbered $1, 2,...., n$. Initially t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":7000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFF2"},"statements":[{"statement_type":"Markdown","content":"*This is the hard version of the problem. The changes in this version are highlighted in bold characters*.\n\nYugandhar have an undirected graph containing $n$ nodes numbered $1, 2,...., n$. Initially there are $0$ edges i.e., there are total $n$ connected components in the graph. He has a freedom to add exactly $k$ undirected edges in this graph, each edge can be added between $u$ and $v$ if and only if $v$ = $u + 1$. Note that he can add multiple edges between two nodes. \n\nAfter giving this graph to wuhudsm, he will observe the following $m$ requirements and reward him coins :\n\nSo Please tell him the optimal way to select these $k$ edges to get maximum number of coins.\n\nAditionally, help him for $q$ queries.\n\nEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10^4$). The description of the test cases follows.\n\nThe first line of test case contains three integers $n, m, q$ ($2 <= n <= bold(10^4)$, $1 <= m <= bold(10^4)$, $1 <= q <= 10^6$) — the number of nodes in graph, the number of requirements and the number of queries.\n\nNext $m$ lines of each test case contains three space separated integers $x_i, y_i, c_i$ ($1 <= x_i, y_i <= n$, $x_i ≠ y_i$, $1 <= c_i <= 10^9$).\n\nNext $q$ lines of each test case contains a single integer $k_i$ ($1 <= k_i <= 10^9$) — the total number of edges needed to add in graph.\n\nIt is guaranteed that the sum of $n$ and sum of $m$ over all test cases doesn't exceed $bold(10^4)$.\n\nIt is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^6$. \n\nFor each test case print $q$ integers — the maximum number of coins he can get if he choose exactly $k_i$ edges optimally.\n\n## Input\n\nEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10^4$). The description of the test cases follows.The first line of test case contains three integers $n, m, q$ ($2 <= n <= bold(10^4)$, $1 <= m <= bold(10^4)$, $1 <= q <= 10^6$) — the number of nodes in graph, the number of requirements and the number of queries.Next $m$ lines of each test case contains three space separated integers $x_i, y_i, c_i$ ($1 <= x_i, y_i <= n$, $x_i ≠ y_i$, $1 <= c_i <= 10^9$).Next $q$ lines of each test case contains a single integer $k_i$ ($1 <= k_i <= 10^9$) — the total number of edges needed to add in graph.It is guaranteed that the sum of $n$ and sum of $m$ over all test cases doesn't exceed $bold(10^4)$.It is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^6$. \n\n## Output\n\nFor each test case print $q$ integers — the maximum number of coins he can get if he choose exactly $k_i$ edges optimally.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"*这是本题的困难版本，唯一区别是时间和内存限制。*\n\n给你一个大小为 $n$ 的数组 $a$。\n\n你执行以下操作：\n\n记 $s_i = a_{l_i} | a_{l_{i + 1}} | ... | a_{r_i}$。这里 $|$ 表示按位或。\n\n求 $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。\n\n输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^6)$，表示测试用例的数量。\n\n每个测试用例包含多行输入。\n\n每个测试用例的第一行包含一个整数 $n (1 lt.eq n lt.eq 10^6)$。\n\n接下来一行包含 $n$ 个用空格分隔的整数：$a_1$，$a_2$，...，$a_n$ $(0 lt.eq a_i < 2^{30})$。\n\n所有测试用例的 $n$ 之和不超过 $10^6$。\n\n对于每个测试用例，在新行上输出 —— $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。\n\n测试用例 $1$：\n\n选择 $k = 3, [ l_1, r_1 ] = [ 1, 1 ], [ l_2, r_2 ] = [ 2, 2 ], [ l_3, r_3 ] = [ 3, 3 ]$。\n\n我们得到 $s_1 = 2, s_2 = 1, s_3 = 2$。答案是 $s_1 - s_2 + s_3 = 2 - 1 + 2 = 3$。\n\n测试用例 $2$：\n\n选择 $k = 1, [ l_1, r_1 ] = [ 1, 6 ]$。\n\n我们得到 $s_1 = 6$。答案是 $s_1 = 6$。\n\n## Input\n\n输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^6)$，表示测试用例的数量。每个测试用例包含多行输入。每个测试用例的第一行包含一个整数 $n (1 lt.eq n lt.eq 10^6)$。接下来一行包含 $n$ 个用空格分隔的整数：$a_1$，$a_2$，...，$a_n$ $(0 lt.eq a_i < 2^{30})$。所有测试用例的 $n$ 之和不超过 $10^6$。\n\n## Output\n\n对于每个测试用例，在新行上输出 —— $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。\n\n[samples]\n\n## Note\n\n测试用例 $1$：选择 $k = 3, [ l_1, r_1 ] = [ 1, 1 ], [ l_2, r_2 ] = [ 2, 2 ], [ l_3, r_3 ] = [ 3, 3 ]$。我们得到 $s_1 = 2, s_2 = 1, s_3 = 2$。答案是 $s_1 - s_2 + s_3 = 2 - 1 + 2 = 3$。测试用例 $2$：选择 $k = 1, [ l_1, r_1 ] = [ 1, 6 ]$。我们得到 $s_1 = 6$。答案是 $s_1 = 6$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ n \\in \\mathbb{Z} $ be the length of array $ a = (a_1, a_2, \\dots, a_n) $, where $ a_i \\in \\mathbb{Z} $ and $ 0 \\le a_i < 2^{30} $.  \n\nA partition of $ a $ into $ k $ contiguous non-empty subarrays is defined by indices $ 1 = l_1 \\le r_1 < l_2 \\le r_2 < \\dots < l_k \\le r_k = n $.  \nFor each subarray $ [l_i, r_i] $, define $ s_i = \\bigvee_{j=l_i}^{r_i} a_j $ (bitwise OR).  \n\n**Constraints**  \n1. $ 1 \\le t \\le 10^6 $  \n2. $ 1 \\le n \\le 10^6 $ per test case  \n3. $ \\sum_{\\text{all test cases}} n \\le 10^6 $  \n4. $ 0 \\le a_i < 2^{30} $  \n\n**Objective**  \nFor each test case, maximize:  \n$$\n\\sum_{i=1}^k (-1)^{i+1} s_i\n$$  \nover all possible partitions $ k \\ge 1 $ and corresponding contiguous subarrays.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFF2","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}