http://acm.hdu.edu.cn/showproblem.php?pid=4455
题目大意就不多说了，官方的解法是dp，没太理解，自己想了一个直接点的方法，O(n)。
既然要计算所有贡献和，对于区间长度为k，假设集合中的元素全都相同，那么这个元素将会贡献给所有长度为k 的子区间。而事实上，所有元素不可能相同，因此就不可能贡献给所有长度为k 的子区间，那么思考，那些子区间是无法贡献的。假设集合中有序列 1......1，如果两个1的间隔为s，那么对于(k<s)的情况，总共有s-k+1个区间是没法贡献的。
而且，只要是任意的k<s，总存在区间是没法贡献的。对于一个k，
s1-k
s2-k
。。。
sum-k*cnt，记录s 的和，记录s>k的个数，就可以求出没法贡献的次数。再用总数减去就行了。有点抽象，能理解的理解理解。
#include<algorithm>
#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>b;i--)
#define MST(a,num) memset(a,num,sizeof(a))
#define MCP(d,s) memcpy(d,s,sizeof(s))
#define WH(n) while(scanf("%d", &n) != EOF)
#define WHZ(n) while(scanf("%d", &n) != EOF && n != 0)
#define SCF(a) scanf("%d",&a)
#define PRF(a) printf("%d",a)
#define PRS(a) printf("%s",a)
#define PRFF(a) printf("%d
",a)
#define PRSF(a) printf("%s
",a)
#define PRFFU(a) printf("%I64d
",a)
#define PI acos(-1)
#define max3(a,b,c) max(max(a,b),c)
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define FORE(e,x) for(__typeof(x.begin()) e=x.begin(); e!=x.end(); e++) //foreach(it, ans ) cout<<*it<<" ";
#define all(a) (a).begin(),(a).end() //sort(all(v));
#define len(a) ((int)(a).size())
#define pb push_back
#define mk make_pair
#define V(etype) vector<etype>
typedef __int64 Uint;
typedef vector<int> Vint;
typedef pair<int,int>mypair;
#define INF 0x3f3f3f3f
#define eps 1e-9
#define N 1000000+10
int q[N];
int head[N];
int rt[N];
int cnt[N];
int num[N];
Uint sum[N];
int main()
{
int n,a,m;
// freopen("data.in","r",stdin);
// freopen("data2.out","w",stdout);
while((cin>>n)&&n){
MST(cnt,0);
MST(sum,0);
MST(rt,-1);
MST(head,-1);
q[0]=0;
FOR(i,0,n){
SCF(num[i]);
if(head[num[i]]==-1)q[++q[0]]=num[i];
rt[i]=head[num[i]];
head[num[i]]=i;
}
FOR(i,1,q[0]+1){
rt[n]=head[q[i]];
for(int j=n;j!=-1;j=rt[j]){
cnt[j-rt[j]]--;
sum[j-rt[j]]-=j-rt[j];
cnt[0]++;
sum[0]+=j-rt[j];
}
}
FOR(i,1,n){
sum[i]+=sum[i-1],cnt[i]+=cnt[i-1];
//ret[i]=(n-i+1)*q[0]-(sum[i]-num[i]*cnt[i]);
}
Uint s1,s2;
SCF(m);
while(m--){
SCF(a);
if(!a)PRSF("0
");
else{
s1=(n-a+1);
s1*=q[0];
s2=a;
s2*=cnt[a];
s2=sum[a]-s2;
PRFFU(s1-s2);
}
}
}
return 0;
}
/*
7
1 1 2 3 4 4 5
3
1 2 3
7
1 1 2 3 4 4 5
4
1 2 3 0
*/