Educational Codeforces Round 171
Educational Codeforces Round 171
D. Sums of Segments
定义四个前缀和:
s i = a 1 + a 2 + ⋯ + a i s_i=a_1+a_2+\dots+a_i si=a1+a2+⋯+ai
u i = s 1 + s 2 + ⋯ + s i u_i=s_1+s_2+\dots+s_i ui=s1+s2+⋯+si
t i = s ( i , i ) + s ( i , i + 1 ) + ⋯ + s ( i , n ) t_i=s(i,i)+s(i,i+1)+\dots+s(i,n) ti=s(i,i)+s(i,i+1)+⋯+s(i,n)
t s i = t 1 + t 2 + ⋯ + t i ts_i=t_1+t_2+\dots+t_i tsi=t1+t2+⋯+ti
s i s_i si为 a i a_i ai的前缀和, u i u_i ui为 s i s_i si的前缀和, t i t_i ti为分块之后第 i i i块的和, t s i ts_i tsi为 t i t_i ti的前缀和,也是分块之后的前缀和
b b b数组中第 k k k块的个数是 n − k + 1 n-k+1 n−k+1,前 k k k块的总数为 n k − k ( k − 1 ) 2 nk-\frac{k(k-1)}{2} nk−2k(k−1)
由前 k k k块的总数可以二分,定位到 l , r l,r l,r的块数,假定分别 x , y x,y x,y
此时和 s u m = t s y − t s x − 1 sum=ts_{y}-ts_{x-1} sum=tsy−tsx−1,还需要减去在 x , y x,y x,y块中多加的
此时需要求位置 l , r l,r l,r在块中的第几个
设第 l , r l,r l,r个元素是 s ( x , z ) , s ( y , w ) s(x,z),s(y,w) s(x,z),s(y,w),由于位置 x n − x ( x − 1 ) 2 xn-\frac{x(x-1)}{2} xn−2x(x−1)上的元素是 s ( x , n ) s(x,n) s(x,n),则有
n − z = x n − x ( x − 1 ) 2 − l n-z=xn-\frac{x(x-1)}{2}-l n−z=xn−2x(x−1)−l,可得: z = n − x n − x ( x − 1 ) 2 + l z=n-xn-\frac{x(x-1)}{2}+l z=n−xn−2x(x−1)+l
同理: w = n − y n − y ( y − 1 ) 2 + r w=n-yn-\frac{y(y-1)}{2}+r w=n−yn−2y(y−1)+r
然后删去多出来的部分
对于第 x x x块,位置 l l l在 s ( x , z ) s(x,z) s(x,z),所以要去掉 s ( x , 1 ) + s ( x , 2 ) + ⋯ + s ( x , z − 1 ) s(x,1)+s(x,2)+\dots+s(x,z-1) s(x,1)+s(x,2)+⋯+s(x,z−1),即下图中红色部分,就可以用我们前面的前缀和求取,
蓝色梯形部分为: u z − 1 − u x u_{z-1}-u_x uz−1−ux
橙色矩形部分为: ( x − z ) s x − 1 (x-z)s_{x-1} (x−z)sx−1
所以减去的红色部分为: u z − 1 − u x − ( x − z ) s x − 1 u_{z-1}-u_x-(x-z)s_{x-1} uz−1−ux−(x−z)sx−1
同理可得对于第 y y y块,需要减去的部分为: u n − u w − 1 − ( n − w ) s y − 1 u_n-u_{w-1}-(n-w)s_{y-1} un−uw−1−(n−w)sy−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;}
}