[每日一题] [NC19798] 区间权值

题目大意：一个长度为N(<=3E5)的数组，考虑每一个长度为L的区间，给予权重w_L。计算没个区间的总和乘以权重的和。

https://ac.nowcoder.com/acm/problem/19798

反过来考虑没个权重w_L的系数，为所有长度为L的区间的总和之和。
长度为1的区间和为a1+...+aN
长度为2的区间和为a1+2a2+...+2aN-1+aN
等等，
可以发现每两个相邻长度之间，要么是加了一个区间总和，要么是减了一个区间总和，并且不难看出通项，那么维护每个长度的这一总和即可。

int n;
int a[MAXN];
int w[MAXN];
void doit() {
  VL cumsum(n, 0LL);
  REP(i, n) {
    if (i) {
      cumsum[i] = cumsum[i - 1] + a[i];
    } else {
      cumsum[i] = a[i];
    }
  }
  ll ans = 0;
  ll cursum = 0;
  REP(i,n) {
    // Updates for i.
    if (i <= n - i - 1) {
      cursum += (cumsum[n - 1 - i] - (i ? cumsum[i - 1] : 0));
    } else {
      if (i - 1 >= n - i) {
      cursum -= (cumsum[i-1] - (n - i ? cumsum[n - 1 - i] : 0));
      }
    }
    ans += cursum * w[i];
    ans %= MOD;
  }
  printf("%lld\n", ans);
}
int main(int argc, char* argv[]) {
  read(n);
  read(a,n);
  read(w,n);
  doit();
  return 0;
}