Submission #69371186

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  /////////////////// 前入力 ///////////////////
  
  int n, q;
  cin >> n >> q;

  vector<long long> a(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i);
  }

  /////////////////// 前処理 ///////////////////

  // 普通の累積和
  vector<long long> b0(n+1);
  partial_sum(a.begin(),a.end(),b0.begin()+1);

  // i倍の累積和
  for (int i=0; i<n; i++) {
    a.at(i) *= i;
  }
  vector<long long> b1(n+1);
  partial_sum(a.begin(),a.end(),b1.begin()+1);

  // i^2倍の累積和
  for (int i=0; i<n; i++) {
    a.at(i) *= i;
  }
  vector<long long> b2(n+1);
  partial_sum(a.begin(),a.end(),b2.begin()+1);

  /////////////////// ループ ///////////////////

  for (int loop=0; loop<q; loop++) {
    
    //////////////////// 入力 ////////////////////

    int l, r;
    cin >> l >> r;
    l--;

    //////////////// 出力変数定義 ////////////////

    long long result = 0;

    //////////////////// 処理 ////////////////////

    // Σ a[i]*(r-i)*{i-(l-1)} = Σ a[i]*{(-1)*i^2+(l+r-1)*i-r*(l-1)} を求める

    // 2次の部分
    result -= b2.at(r)-b2.at(l);

    // 1次の部分
    result += (b1.at(r)-b1.at(l))*(l+r-1);

    // 0次の部分
    result -= (b0.at(r)-b0.at(l))*r*(l-1);

    //////////////////// 出力 ////////////////////

    cout << result << endl;
    
  }

  /////////////////// 後処理 ///////////////////



  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result