题意：就问问你统计[L,R]中x1,x2,,xi出现次数a1,a2,,ai的ai*ai*xi和。
题解：分块暴力。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<set>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef __int64 LL;const int INF = 0x3f3f3f3f;const int maxn=200000+100;LL up[maxn];int col[maxn],sum[maxn*10],n,m,k;LL ans;struct node{int l,r;int id;}q[maxn];int cmp(node l1,node l2){if(l1.l/k==l2.l/k)return l1.r<l2.r;return l1.l<l2.l;}void update(int x,int val){ans-=(LL)col[x]*sum[col[x]]*sum[col[x]];sum[col[x]]+=val;ans+=(LL)col[x]*sum[col[x]]*sum[col[x]];}int main(){while(~scanf("%d%d",&n,&m)){CLEAR(sum,0);k=sqrt(n*1.0+0.5);REPF(i,1,n)scanf("%d",&col[i]);REP(i,m){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}sort(q,q+m,cmp);int L=0,R=0;ans=0;for(int i=0;i<m;i++){int id=q[i].id;int l=q[i].l;int r=q[i].r;while(L < l){update(L,-1);L++;}while(R > r){update(R,-1);R–;}while(L > l){L–;update(L,1);}while(R < r){R++;update(R,1);}up[id]=ans;}for(int i=0;i<m;i++)printf("%I64d\n",up[i]);}return 0;}
，为什么？答：点线杆上贴着”“此处不许小便！”
