推式子
是的，努力推式子即可。
记需要统计答案的区间的头尾值为v，主要思想就是分不同的v来考虑。枚举v的所有区间下的最小间隔的区间，考虑区间内的数在v的所有跨过这个区间的大区间的贡献即可。注意中间端点的答案会被统计两次，需要减掉……(刚开始没注意到这一点然后WA飞啦)
#include<cstdio> #include<cstring> #define N 1000005 #define uint unsigned using namespace std; namespace runzhe2000 { int read() { int r = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()); for(; c >='0' && c <='9'; r = r*10+c-'0', c = getchar()); return r; } int n; uint a[N], b[N], suma[N], sumb[N], suml[N], sumr[N], cntl[N], cntr[N], lastl[N], lastr[N], lastv[N], ans; void main() { n = read(); for(int i = 1; i <= n; i++) { a[i] = read(); b[i] = -2*a[i]*i; suma[i] = suma[i-1] + a[i]; sumb[i] = sumb[i-1] + b[i]; } for(int i = 1; i <= n; i++) { int p = lastv[a[i]]; suml[i] = suml[p] + i; cntl[i] = cntl[p] + 1; lastl[i] = p; lastv[a[i]] = i; } memset(lastv,0,sizeof(lastv)); for(int i = n; i >= 1; i--) { int p = lastv[a[i]]; sumr[i] = sumr[p] + i; cntr[i] = cntr[p] + 1; lastr[i] = p; lastv[a[i]] = i; } for(int i = 1; i <= n; i++) if(lastl[i]) { int j = lastl[i]; ans -= (suma[i] - suma[j-1]) * (suml[j] * cntr[i] + sumr[i] * cntl[j]); ans -= (sumb[i] - sumb[j-1]) * cntl[j] * cntr[i]; if(lastr[i]) { int k = lastr[i]; ans += b[i] * cntl[j] * cntr[k] + a[i] * (suml[j] * cntr[k] + sumr[k] * cntl[j]); } } printf("%u\n",ans); } } int main() { runzhe2000::main(); }