累積和＋2分探索_ABC 371 D - 1D Countryを理解し忘れないようにする。

ABC 371 D - 1D Country

https://atcoder.jp/contests/abc371/tasks/abc371_d

問題概要

数直線上に N 個の村がある。i 番目の村は座標 Xiにあり、Pi人の村人がいます。
Q 個のクエリに答えてください。
i 番目のクエリは以下の形式です。
整数 Li,R iが与えられる。座標が Li以上 Ri以下の村に住んでいる村人の人数の総数を求めよ。

基本設計

まとめると以下の数式で答えを求められる。
$座標がR以下の場所に住んでいる人の合計 - 座標がL未満の場所に住んでいる人の合計$

座標ごとの合計人数は累積和を使って求める。
あとは値と値の境界線を求められる2分探索を用いて、上記の累積和から「R以下の場所に住んでいる人の合計」と「座標がL未満の場所に住んでいる人の合計」を求められる。

計算量は$O(QlogN)$

提出コード

https://atcoder.jp/contests/abc371/submissions/58600828

int main()
{
  int n;
  cin >> n;
  vector<int> x(n),p(n);
  rep(i,n) cin >> x[i];
  rep(i,n) cin >> p[i];
  int q;
  cin >> q;
  vector<int> l(q),r(q);
  rep(i,q) cin >> l[i] >> r[i];
  vector<ll> sum(n+1);
  rep(i,n) sum[i+1] = sum[i] + p[i];
  rep(i,q) {
    int j1 = upper_bound(all(x),l[i]-1) - x.begin();
    int j2 = upper_bound(all(x),r[i]) - x.begin();
    ll ans = sum[j2]- sum[j1];
    cout << ans << endl;
  }
  return 0;
}