codeforces 86 D. Powerful array （莫队算法）
http://codeforces.com/problemset/problem/86/D
题意：Ks为区间内s的数目，求区间[L,R]之间所有KsKss的和
思路：莫队算法，和小z的袜子差不多。不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。
再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多==
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月13日 星期六 23时17分58秒
4File Name :code/cf/problem/86D.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E5+7;
34int t,n;
35int a[N];
36int pos[N];
37LL sum;
38LL ans[N];
39struct node
40{
41 int l,r;
42 int id;
43
44 bool operator <(node b)const
45 {
46 if (pos[l]==pos[b.l]) return r<b.r;
47 return pos[l]<pos[b.l];
48 }
49
50}q[N];
51
52int cnt[N*5];
53
54
55void update(int x,int d)
56{
57 sum -= 1LL*cnt[a[x]]*cnt[a[x]]*a[x];
58 cnt[a[x]]+=d;
59 sum += 1LL*cnt[a[x]]*cnt[a[x]]*a[x];
60}
61int main()
62{
63 #ifndef ONLINE_JUDGE
64 freopen("code/in.txt","r",stdin); //TLE #54....WHY?
65 #endif
66
67 cin>>n>>t;
68 int bk = 470;
69 for ( int i = 1 ; i <= n ; i++)
70 {
71 scanf("%d",&a[i]);
72 pos[i]=(i-1)/bk;
73 }
74
75 for ( int i = 1 ; i <= t ; i++) scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i ;
76 sort(q+1,q+t+1);
77
78 int pl = 1;
79 int pr = 0;
80 int id;
81 int l;
82 int r;
83 ms(cnt,0);
84 sum = 0;
85 for ( int i = 1 ; i <= t ; i++)
86 {
87 // cout<<"sum:"<<sum<<endl;
88 id = q[i].id;
89 l = q[i].l;
90 r = q[i].r;
91
92 if (pr<r)
93 {
94 for ( int j = pr+1 ; j <= r ; j++)
95 update(j,1);
96 }
97 else
98 {
99 for ( int j = r+1 ; j <= pr ; j++)
100 update(j,-1);
101 }
102 pr = r;
103
104 if (pl<l)
105 {
106 for ( int j = pl ; j <=l-1 ; j++)
107 update(j,-1);
108 }
109 else
110 {
111 for ( int j = l ; j <= pl-1 ; j++)
112 update(j,1);
113 }
114
115 pl = l;
116
117 ans[id] = sum;
118 }
119
120 for ( int i = 1 ;i <= t ; i++) printf("%lld\n",ans[i]);
121
122 #ifndef ONLINE_JUDGE
123 fclose(stdin);
124 #endif
125 return 0;
126}