Educational Codeforces Round 171

D. Sums of Segments

定义四个前缀和：

\(s_i=a_1+a_2+\dots+a_i\)

\(u_i=s_1+s_2+\dots+s_i\)

\(t_i=s(i,i)+s(i,i+1)+\dots+s(i,n)\)

\(ts_i=t_1+t_2+\dots+t_i\)

\(s_i\)为\(a_i\)的前缀和，\(u_i\)为\(s_i\)的前缀和，\(t_i\)为分块之后第\(i\)块的和，\(ts_i\)为\(t_i\)的前缀和，也是分块之后的前缀和

\(b\)数组中第\(k\)块的个数是\(n-k+1\)，前\(k\)块的总数为\(nk-\frac{k(k-1)}{2}\)

由前\(k\)块的总数可以二分，定位到\(l,r\)的块数，假定分别\(x,y\)

此时和\(sum=ts_{y}-ts_{x-1}\)，还需要减去在\(x,y\)块中多加的

此时需要求位置\(l,r\)在块中的第几个

设第\(l,r\)个元素是\(s(x,z),s(y,w)\)，由于位置\(xn-\frac{x(x-1)}{2}\)上的元素是\(s(x,n)\)，则有

\(n-z=xn-\frac{x(x-1)}{2}-l\)，可得：\(z=n-xn-\frac{x(x-1)}{2}+l\)

同理：\(w=n-yn-\frac{y(y-1)}{2}+r\)

然后删去多出来的部分

对于第\(x\)块，位置\(l\)在\(s(x,z)\)，所以要去掉\(s(x,1)+s(x,2)+\dots+s(x,z-1)\)，即下图中红色部分，就可以用我们前面的前缀和求取，

蓝色梯形部分为：\(u_{z-1}-u_x\)

橙色矩形部分为：\((x-z)s_{x-1}\)

所以减去的红色部分为：\(u_{z-1}-u_x-(x-z)s_{x-1}\)

同理可得对于第\(y\)块，需要减去的部分为：\(u_n-u_{w-1}-(n-w)s_{y-1}\)

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
const double eps = 1e-6;
int n;
int s[N],u[N],t[N],ts[N],a[N];
int x, y, q, l, r ,z ,w;
void solve()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
        s[i] = s[i-1] + a[i];
        u[i] = u[i-1] + s[i]; 
    }
    for(int i = n ; i >= 1 ; i --)
        t[i] = t[i+1] + (n-i+1)*a[i];
    for(int i = 1 ; i <= n ; i ++)
        ts[i] = ts[i-1] + t[i];
    cin >> q;
    while(q--){
        cin >> l >> r;
        int sum = 0;
        int L = 1, R = n;
        while(L != R){
            int mid = (L + R) / 2;
            if(n*mid-mid*(mid-1)/2 < l) L = mid + 1;
            else R = mid;
        }
        x = L;
        L = 1 , R = n;
        while(L != R){
            int mid = (L + R) / 2;
            if(n*mid-mid*(mid-1)/2 < r) L = mid + 1;
            else R = mid;
        }
        y = L;
        // cout << x << " " << y << " ";
        sum = ts[y] - ts[x-1];
        z = n - (x*n -x*(x-1)/2 - l);
        w = n - (y*n -y*(y-1)/2 - r);
        sum -= u[z-1] - u[x-1] - (z-x)*s[x-1];
        sum -= u[n]-u[w] -s[y-1]*(n-w);
        cout << sum << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // cin >> _ ;
    while (_--)
        solve();
    return 0;
}