题解：AT_abc480_d [ABC480D] Concatenation of Prefixes
chenyuan3
·
·
题解
令 C_x=\sum_{i=1}^xB_i，则只需求 C_r-C_{l-1}。
[AC](https://atcoder.jp/contests/abc480/submissions/80133649) 代码：
``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
ll n, q, a[maxn], b[maxn], l, r;
ll calc(ll x)
{
ll l = 0, r = x, ans = 1;
while (l <= r)
{
ll mid = l + r >> 1;
ll p = mid * (mid + 1) / 2;
if (mid * (mid + 1) / 2 <= x)
{
l = mid + 1;
ans = mid;
}
else
{
r = mid - 1;
}
}
return b[ans] + a[x - ans * (ans + 1) / 2];
}
void solve()
{
cin >> n >> q;
for (ll i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i - 1];
b[i] = b[i - 1] + a[i];
}
while (q--)
{
cin >> l >> r;
cout << calc(r) - calc(l - 1) << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
```