nbut 1457 Sona
https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。 思路：由于一共才1E5,而数字1E9,所以先离散化，再莫队，类似小z的袜子。 注意 ：%lld会WA,要用%I64d
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月17日 星期三 16时11分00秒
4File Name :code/nbut/1457.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=1E5+7;
34int a[N],b[N];
35LL cnt[N];
36int pos[N];
37LL ans[N];
38LL sum;
39int n,m;
40
41struct node
42{
43 int l,r;
44 int id;
45
46 bool operator < (node b)const
47 {
48 if (pos[l]==pos[b.l]) return r<b.r;
49 return pos[l]<pos[b.l];
50 }
51}q[N];
52
53
54
55void update(int x,int d)
56{
57
58 sum-=cnt[a[x]]*cnt[a[x]]*cnt[a[x]];
59 cnt[a[x]]+=d;
60 sum +=cnt[a[x]]*cnt[a[x]]*cnt[a[x]];
61
62}
63int main()
64{
65 #ifndef ONLINE_JUDGE
66 freopen("code/in.txt","r",stdin);
67 #endif
68
69 while (scanf("%d",&n)!=EOF)
70 {
71 ms(cnt,0);
72 ms(ans,0);
73 sum = 0LL;
74
75 int siz = 330;//sqrt(100000);
76 for ( int i = 1 ; i <= n ; i++)
77 {
78 scanf("%d",&b[i]);
79 pos[i] = (i-1)/siz;
80 a[i] = b[i];
81 }
82
83 sort(b+1,b+n+1); //离散化
84 int t = unique(b+1,b+n+1)-b-1;
85 for ( int i = 1 ; i <= n ; i++) a[i]=lower_bound(b+1,b+t+1,a[i])-b;
86
87 scanf("%d",&m);
88 for ( int i = 1 ; i <= m ; i++)
89 {
90 scanf("%d %d",&q[i].l,&q[i].r);
91 q[i].id = i ;
92 }
93 sort(q+1,q+m+1);
94
95 int pl=1,pr=0;
96 int id,l,r;
97 for ( int i = 1 ; i <= m ; i++)
98 {
99 id = q[i].id;
100 r = q[i].r;
101 l = q[i].l;
102
103 if (pr<r)
104 {
105 for ( int j = pr +1 ; j <= r ; j++) update(j,1);
106 }
107 else
108 {
109 for (int j = r+1 ; j <= pr ; j++) update(j,-1);
110 }
111 pr = r;
112
113 if (l<pl)
114 {
115 for ( int j = l ; j <= pl-1 ; j++) update(j,1);
116 }
117 else
118 {
119 for (int j = pl ; j <= l-1 ; j++) update(j,-1);
120 }
121 pl = l;
122
123 ans[id] = sum;
124 }
125
126 for ( int i = 1 ; i <= m ; i++) printf("%I64d\n",ans[i]); //用%lld会WA...也不给个警告
127 }
128
129 #ifndef ONLINE_JUDGE
130 fclose(stdin);
131 #endif
132 return 0;
133}