P15729 [JAG 2024 Summer Camp #2] Add Add Add
Link: 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, 2Nk=2,3,…,2N，计算∑ i + j ≤ k ( A i + B j ) \sum_{i+j \leq k} (A_i + B_j)∑i+j≤k(Ai+Bj)的值，即对所有满足i + j ≤ k i + j \leq ki+j≤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}NA1A2…ANB1B2…BN
- 1 ≤ N ≤ 200 , 000 1 \leq N \leq 200,0001≤N≤200,000
- 1 ≤ A i , B i ≤ 10 6 1 \leq A_i, B_i \leq 10^61≤Ai,Bi≤106（1 ≤ 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 + 1k=i+1时的答案。
输入输出样例 #1
输入 #1
3 1 1 1 1 1 1输出 #1
2 6 12 16 18输入输出样例 #2
输入 #2
5 3 7 1 8 3 7 10 5 3 4输出 #2
10 37 70 114 165 206 230 248 255输入输出样例 #3
输入 #3
1 3 5输出 #3
8Solution
1. 题意
给定两个长度为n nn的正整数序列{ A n } \{A_n\}{An}和{ B n } \{B_n\}{Bn}。对于k = 2 , 3 , … , 2 n k = 2, 3, \ldots, 2nk=2,3,…,2n，计算∑ i + j ≤ k ( A i + B j ) \sum_{i+j \leq k} (A_i + B_j)∑i+j≤k(Ai+Bj)的值。
2. 分析
不妨设函数
f ( k ) = ∑ i + j ≤ k ( A i + B j ) f(k) = \sum_{i+j \leq k} (A_i + B_j)f(k)=i+j≤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(k+1) &= f(k) + \sum_{i+j = k+1} (A_i + B_j) \\&= f(k) + \sum_{i=1}^{k+1}(A_i+B_{k+1-i}) \\&= f(k) + \sum_{i=1}^{k}A_i + \sum_{i=1}^{k}B_i \end{aligned}f(k+1)=f(k)+i+j=k+1∑(Ai+Bj)=f(k)+i=1∑k+1(Ai+Bk+1−i)=f(k)+i=1∑kAi+i=1∑kBi
从上面的和式容易发现，f ( k + 1 ) f(k+1)f(k+1)等于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{constintmaxn=200010;staticlong[]a=newlong[maxn];staticlong[]b=newlong[maxn];publicstaticvoidMain(string[]args){Scannercin=newScanner();StreamWritercout=newStreamWriter(Console.OpenStandardOutput()){AutoFlush=false};longn;stringnInput=cin.Next();if(string.IsNullOrEmpty(nInput))return;n=long.Parse(nInput);for(longi=1;i<=n;i++){stringval=cin.Next();if(val!=null){a[i]=long.Parse(val);a[i]+=a[i-1];}}for(longi=1;i<=n;i++){stringval=cin.Next();if(val!=null){b[i]=long.Parse(val);b[i]+=b[i-1];}}longsum=0;for(longk=2;k<=2*n;k++){longm=Math.Min(k-1,n);sum+=a[m]-a[k-m-1];sum+=b[m]-b[k-m-1];cout.Write(sum);cout.Write("\n");}cout.Flush();cout.Close();}}publicclassScanner{privateStreamReaderreader;privatestring[]tokens;privateintpointer;publicScanner(){reader=newStreamReader(Console.OpenStandardInput());}publicstringNext(){while(tokens==null||pointer>=tokens.Length){stringline=reader.ReadLine();if(line==null)returnnull;tokens=line.Split(new[]{' ','\t','\n','\r'},StringSplitOptions.RemoveEmptyEntries);pointer=0;}returntokens[pointer++];}}
