Educational Codeforces Round 171

定义四个前缀和：

$s_i=a_1+a_2+\cdots +a_i$

$u_i=s_1+s_2+\cdots +s_i$

$t_i=s(i,i)+s(i,i+1)+\cdots +s(i,n)$

$t{s}_i=t_1+t_2+\cdots +t_i$

$s_i$为$a_i$的前缀和，$u_i$为$s_i$的前缀和，$t_i$为分块之后第$i$块的和，$t{s}_i$为$t_i$的前缀和，也是分块之后的前缀和

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

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

此时和$sum=t{s}_y-t{s}_{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)+\cdots +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}$

代码如下：

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;}
}