题意概述
敌军一共有 \(n\) 个阵营，第 \(i\) 个阵营会向 \([i+1, \min(i+r_i, n)]\) 区间内的所有阵营发送一封电报。
拥有一个拦截器，若有一封电报从阵营 \(p\) 发送到阵营 \(q\)，拦截器位于 \(x\)，并且 \(p \leq x \leq q\)，那么该电报就会被拦截，拦截价值为 \(\min(x-p, q-x)\)。
问对于每个阵营 \(i\)，在该位置放置拦截器的拦截价值之和为多少？
思路
先将 \(r_i\) 调整为 \(\min(i+r_i, n) - i\) 。
第 \(i\) 个阵营发送电报，只会对 \([i, i+r_i]\) 区间贡献有影响，根据拦截价值的定义，考虑分类讨论。
令 \(mid = (i+i+r+1)/2\) 。
-
若 \(i \le j \le mid\)，有两端贡献，一段为 \([j,2j-i]\)，每个点 \(x\) 贡献 \(x-j\)，总贡献为 \((2j-i-j+1) \times (2j-i+j) / 2 - j \times (2j-i-j+1)\) ；另一端为 \([2j-i+1,i+r]\)，每个点 \(x\) 贡献 \(j-i\)，总贡献为 \((i+r-(2j-i)) \times (j-i)\) 。发现前一部分有 \(/2\) 不好处理，考虑对所有贡献都 \(\times 2\)。整理出贡献总和为 \(-3j^2+(6i+2r+1)j-3i^2-i-2ri\) 。
-
若 \(mid \lt j \le i+r\)，只有一段贡献 \([j,i+r]\)，每个点 \(x\) 贡献 \(x-j\)，总贡献为 \((i+r-j+1) \times (i+r+j) / 2 - (i+r-j+1) \times j\) 。同样把贡献 \(\times 2\)，整理出贡献总和为 \(j^2+(-2r-2i-1)j+i^2+r^2+2ri+i+r\) 。
因此对于每个位置，差分维护各次的系数即可。
时间复杂度 \(\mathcal{O}(n)\) 。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n;cin >> n;vector<int> R(n+1);for (int i=1;i<=n;i++){cin >> R[i];} vector<array<ll,3>> diff(n+2,{0,0,0});for (int i=1;i<=n;i++){int l = i;int r = min(n,i+R[i]);R[i] = r-l;int mid = (l+r+1)/2;diff[l][0] += -3ll*i*i-i-2ll*R[i]*i;diff[mid+1][0] -= -3ll*i*i-i-2ll*R[i]*i;diff[l][1] += 6ll*i+2ll*R[i]+1;diff[mid+1][1] -= 6ll*i+2ll*R[i]+1;diff[l][2] += -3;diff[mid+1][2] -= -3;diff[mid+1][0] += (ll)i*i+(ll)R[i]*R[i]+2ll*i*R[i]+i+R[i];diff[r+1][0] -= (ll)i*i+(ll)R[i]*R[i]+2ll*i*R[i]+i+R[i];diff[mid+1][1] += -2ll*R[i]-2ll*i-1;diff[r+1][1] -= -2ll*R[i]-2ll*i-1;diff[mid+1][2] += 1;diff[r+1][2] -= 1;}for (int i=1;i<=n;i++){for (int j=0;j<=2;j++){diff[i][j] += diff[i-1][j];}cout << (diff[i][2]*i*i+diff[i][1]*i+diff[i][0])/2 << '\n';}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}