P15729 [JAG 2024 Summer Camp #2] Add Add Add 题解

P15729 [JAG 2024 Summer Camp #2] Add Add AddLink: https://www.luogu.com.cn/problem/P15729题目描述给定两个长度为N NN的正整数序列( A 1 , A 2 , … , A N ) (A_1, A_2, \ldots, A_N)(A1​,A2​,…,AN​)和( B 1 , B 2 , … , B N ) (B_1, B_2, \ldots, B_N)(B1​,B2​,…,BN​)。对于k 2 , 3 , … , 2 N k 2, 3, \ldots, 2Nk2,3,…,2N计算∑ i j ≤ k ( A i B j ) \sum_{ij \leq k} (A_i B_j)∑ij≤k​(Ai​Bj​)的值即对所有满足i j ≤ k i j \leq kij≤k且1 ≤ i , j ≤ N 1 \leq i, j \leq N1≤i,j≤N的下标对( i , j ) (i, j)(i,j)求( A i B j ) (A_i B_j)(Ai​Bj​)的和。输入格式输入以如下格式给出N A 1 A 2 … A N B 1 B 2 … B N \begin{aligned} N \\ A_1 \ A_2 \ \ldots \ A_N \\ B_1 \ B_2 \ \ldots \ B_N \end{aligned}​NA1​A2​…AN​B1​B2​…BN​​1 ≤ N ≤ 200 , 000 1 \leq N \leq 200,0001≤N≤200,0001 ≤ A i , B i ≤ 10 6 1 \leq A_i, B_i \leq 10^61≤Ai​,Bi​≤1061 ≤ i ≤ N 1 \leq i \leq N1≤i≤N所有输入值均为整数。输出格式输出2 N − 1 2N - 12N−1行。在第i ii行1 ≤ i ≤ 2 N − 1 1 \leq i \leq 2N - 11≤i≤2N−1输出当k i 1 k i 1ki1时的答案。输入输出样例 #1输入 #13 1 1 1 1 1 1输出 #12 6 12 16 18输入输出样例 #2输入 #25 3 7 1 8 3 7 10 5 3 4输出 #210 37 70 114 165 206 230 248 255输入输出样例 #3输入 #31 3 5输出 #38Solution1. 题意给定两个长度为n nn的正整数序列{ A n } \{A_n\}{An​}和{ B n } \{B_n\}{Bn​}。对于k 2 , 3 , … , 2 n k 2, 3, \ldots, 2nk2,3,…,2n计算∑ i j ≤ k ( A i B j ) \sum_{ij \leq k} (A_i B_j)∑ij≤k​(Ai​Bj​)的值。2. 分析不妨设函数f ( k ) ∑ i j ≤ k ( A i B j ) f(k) \sum_{ij \leq k} (A_i B_j)f(k)ij≤k∑​(Ai​Bj​)则很容易发现f ( k 1 ) f ( k ) ∑ i j k 1 ( A i B j ) f ( k ) ∑ i 1 k 1 ( A i B k 1 − i ) f ( k ) ∑ i 1 k A i ∑ i 1 k B i \begin{aligned} f(k1) f(k) \sum_{ij k1} (A_i B_j) \\ f(k) \sum_{i1}^{k1}(A_iB_{k1-i}) \\ f(k) \sum_{i1}^{k}A_i \sum_{i1}^{k}B_i \end{aligned}f(k1)​f(k)ijk1∑​(Ai​Bj​)f(k)i1∑k1​(Ai​Bk1−i​)f(k)i1∑k​Ai​i1∑k​Bi​​从上面的和式容易发现f ( k 1 ) f(k1)f(k1)等于f ( k ) f(k)f(k)加上两个数组的前k kk项和而前缀和本身可以通过一边输入一边计算储存。如此一来输入阶段O ( n ) O(n)O(n)复杂度求出两个数组的前缀和常数是2 22然后继续O ( n ) O(n)O(n)复杂度求出f ( 1 ) , f ( 2 ) ⋯ f ( k ) f(1),f(2) \cdots f(k)f(1),f(2)⋯f(k)并输出。总体的时间复杂度还是O ( n ) O(n)O(n)。换句话说f ( k ) f(k)f(k)就是前缀和的前缀和整个求解过程可以理解为“半打表”。3. 代码usingSystem;usingSystem.Collections.Generic;usingSystem.IO;usingSystem.Linq;usingSystem.Text;publicclassP15729{constintmaxn200010;staticlong[]anewlong[maxn];staticlong[]bnewlong[maxn];publicstaticvoidMain(string[]args){ScannercinnewScanner();StreamWritercoutnewStreamWriter(Console.OpenStandardOutput()){AutoFlushfalse};longn;stringnInputcin.Next();if(string.IsNullOrEmpty(nInput))return;nlong.Parse(nInput);for(longi1;in;i){stringvalcin.Next();if(val!null){a[i]long.Parse(val);a[i]a[i-1];}}for(longi1;in;i){stringvalcin.Next();if(val!null){b[i]long.Parse(val);b[i]b[i-1];}}longsum0;for(longk2;k2*n;k){longmMath.Min(k-1,n);suma[m]-a[k-m-1];sumb[m]-b[k-m-1];cout.Write(sum);cout.Write(\n);}cout.Flush();cout.Close();}}publicclassScanner{privateStreamReaderreader;privatestring[]tokens;privateintpointer;publicScanner(){readernewStreamReader(Console.OpenStandardInput());}publicstringNext(){while(tokensnull||pointertokens.Length){stringlinereader.ReadLine();if(linenull)returnnull;tokensline.Split(new[]{ ,\t,\n,\r},StringSplitOptions.RemoveEmptyEntries);pointer0;}returntokens[pointer];}}