ABC480 D - Concatenation of Prefixes
- サイト
- AtCoder
- コンテスト
- ABC480
- 問題
- D - Concatenation of Prefixes
- 難易度
- 864
長さ の整数列 が与えられます。 の順に を末尾に連結して、長さ の数列 を作ります。 個の質問 について、 を求める問題です(、)。
の先頭からの和 が求められれば、答えは です。
は、 番目のかたまりが であるようなかたまりの連結です。 番目のかたまりの長さは なので、はじめの 個のかたまりの長さの合計は です。また、 の累積和を とすると、 番目のかたまりの和は です。
を求めるには、まず となる最大の を求めます。 は、はじめの 個のかたまりと、 番目のかたまりの先頭 個からなります。したがって
です。 と、 の累積和を前計算しておけば、 は を求めるだけで計算できます。 は増加列なので、 は二分探索で求められます。
計算量は です。 は最大で 程度なので、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] が 、s0[j] が 、s1[i] が です。bisect_right(tmp, x) は tmp の中で x より大きい最初の要素の位置(Python の bisect.bisect_right と同じ)を返すので、そこから を引くと となる最大の になります。q(x) が です。
使用ライブラリ:cpp_include@9c33ee7