51nod1712 区间求和

http://www.51nod.com/Challenge/Problem.html#problemId=1712
先考虑题面中的简化问题。
对于(iin [1,n])，(a_i)的贡献为(a_i*(i-1)-a_i*(n-i))
那么对于(iin [l,r](a_l=a_r))，贡献为(a_i*(i-l)-a_i*(r-i)=2i*a_i-a_i(l+r))
这个式子只需要统计4个东西就可以(O(n))计算了。

• (i)左侧(a_l)的个数(A)
• (i)右侧(a_r)的个数(B)
• (i)左侧(a_l)的(l)之和(C)
• (i)右侧(a_r)的(r)之和(D)

那么对答案的贡献就是(2*i*a_i*A*B-a_i*(BC+AD))
统计一下(A,B,C,D)即可。

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

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
	return x * f;
}

typedef unsigned int uint;
const int N = 1000010;

int n, lim, a[N];
uint num[N], sum[N], numl[N], numr[N], suml[N], sumr[N];
uint Sum, Num;

int main() {
	n = read();
	for(int i = 1; i <= n; ++i) {
		a[i] = read();
		numr[a[i]]++; sumr[a[i]] += i; 
	}
	uint ans = 0;
	for(int i = 1; i <= n; ++i) {
		numl[a[i]]++; suml[a[i]] += i;
		Num -= num[a[i]];
		num[a[i]] = numl[a[i]] * numr[a[i]];
		Num += num[a[i]];
		Sum -= sum[a[i]];
		sum[a[i]] = suml[a[i]] * numr[a[i]] + sumr[a[i]] * numl[a[i]];
		Sum += sum[a[i]];
		
		ans += 2 * i * a[i] * Num - a[i] * Sum;
		
		numr[a[i]]--; sumr[a[i]] -= i;
		Num -= num[a[i]];
		num[a[i]] = numl[a[i]] * numr[a[i]];
		Num += num[a[i]];
		Sum -= sum[a[i]];
		sum[a[i]] = suml[a[i]] * numr[a[i]] + sumr[a[i]] * numl[a[i]];
		Sum += sum[a[i]];
	}
	printf("%u
", ans);
}