コンテンツにスキップ

ABC480 D - Concatenation of Prefixes

サイト
AtCoder
コンテスト
ABC480
問題
D - Concatenation of Prefixes
難易度
864

長さ NN の整数列 AA が与えられます。i=1,2,…,Ni = 1, 2, \dots, N の順に (A1,…,Ai)(A_1, \dots, A_i) を末尾に連結して、長さ N(N+1)2\frac{N(N+1)}{2} の数列 BB を作ります。QQ 個の質問 (L,R)(L, R) について、BL+⋯+BRB_L + \dots + B_R を求める問題です(1≤N,Q≤1051 \le N, Q \le 10^5、−108≤Ai≤108-10^8 \le A_i \le 10^8)。

BB の先頭からの和 f(x)=B1+⋯+Bxf(x) = B_1 + \dots + B_x が求められれば、答えは f(R)−f(L−1)f(R) - f(L - 1) です。

BB は、kk 番目のかたまりが (A1,…,Ak)(A_1, \dots, A_k) であるようなかたまりの連結です。kk 番目のかたまりの長さは kk なので、はじめの ii 個のかたまりの長さの合計は Ti=i(i+1)2T_i = \frac{i(i+1)}{2} です。また、AA の累積和を Pj=A1+⋯+AjP_j = A_1 + \dots + A_j とすると、kk 番目のかたまりの和は PkP_k です。

f(x)f(x) を求めるには、まず Ti≤xT_i \le x となる最大の ii を求めます。B1,…,BxB_1, \dots, B_x は、はじめの ii 個のかたまりと、i+1i + 1 番目のかたまりの先頭 x−Tix - T_i 個からなります。したがって

f(x)=(P1+⋯+Pi)+Px−Tif(x) = (P_1 + \dots + P_i) + P_{x - T_i}

です。PP と、PP の累積和を前計算しておけば、f(x)f(x) は ii を求めるだけで計算できます。TiT_i は増加列なので、ii は二分探索で求められます。

計算量は O(N+Qlog⁡N)O(N + Q \log N) です。∣f(x)∣|f(x)| は最大で N(N+1)2×108≈5×1017\frac{N(N+1)}{2} \times 10^8 \approx 5 \times 10^{17} 程度なので、64 ビット整数に収まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/binary-search.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, Q);
VL(A, N);
vl tmp = {0};
vl s0 = {0}, s1 = {0};
rep(i, N) {
s0.push_back(s0.back() + A[i]);
s1.push_back(s1.back() + s0.back());
tmp.push_back(tmp.back() + i + 1);
}
auto q = [&](ll x) {
ll i = bisect_right(tmp, x) - 1;
return s1[i] + s0[x - tmp[i]];
};
rep(Q) {
LL(L, R);
print(q(R) - q(L - 1));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tmp[i] が TiT_i、s0[j] が PjP_j、s1[i] が P1+⋯+PiP_1 + \dots + P_i です。bisect_right(tmp, x) は tmp の中で x より大きい最初の要素の位置(Python の bisect.bisect_right と同じ)を返すので、そこから 11 を引くと Ti≤xT_i \le x となる最大の ii になります。q(x) が f(x)f(x) です。

使用ライブラリ:cpp_include@9c33ee7