ABC480D 题解

· · 题解

Solution

序列区间和可以转化成前缀和问题，所以答案为 \operatorname{prefix}(R)-\operatorname{prefix}(L-1)（其中 \operatorname{prefix}(i) 表示 B_1+B_2+\dots+B_i）。

但是 B 的长度是 \dfrac{N(N+1)}{2}，直接计算会 TLE。我们需要想别的办法。

把 B 排成三角形：

A_1 A_1$ $A_2 A_1$ $A_2$ $A_3 \vdots\qquad\quad\quad\ddots A_1$ $A_2$ $A_3$ $\dots$ $A_N

可以发现每一层数的和是 A 的前缀和，由于 B 中第 i 个数所在的层的上面所有层是完整的，所以可以把上面所有数的和算出来（对 A 的前缀和数组再求一次前缀和），这样问题只剩下一层，可以得到也是从第 1 个数开始的，所以用之前得到的 A 的前缀和求出答案即可。两次计算的结果的和即为 \operatorname{prefix}(i)。

至于上面的层数有多少，可以预处理对于每个 j(j=1,2,\dots,N)，1+2+\dots+j 的值，然后二分查找（因为是查找最大的满足 (1+2+\dots+j) \le i 的 j，所以使用 upper_bound，最后下标减 1）。

Code

#include <bits/stdc++.h>
using namespace std;
long long n,q,a[400001],s[400001],ss[400001],p[400001];long long l,r;
/*

1  11    111      1111
1|1 10|1 10 100|1 10 100 1000  

1 3 6 10
*/
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        ss[i]=ss[i-1]+s[i];
        p[i]=1ll*i*(i+1)/2;
    }
    while(q--){
        cin>>l>>r;
        long long ansl=0,ansr=0;
        long long d=upper_bound(p+1,p+n+1,r)-p-1,dd=upper_bound(p+1,p+n+1,l-1)-p-1;
        ansr=ss[d]+s[r-p[d]];
        ansl=ss[dd]+s[(l-1)-p[dd]];
        cout<<ansr-ansl<<'\n';
    }
    return 0;
}

AC Record