CF86D-Powerful Array

简要题面

设一个序列的分值为每个数出现次数的平方乘这个数,给定一个长度为n序列,有m组询问[l,r][l,r],求从第l个数到第r个数这个子序列的分值。

不需简要题解(其实就是直接放代码)

莫队裸题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
/*
Author: CNYALI_LK
LANG: C++
PROG: CF86D.cpp
*/
#include<bits/stdc++.h>
#define up(a,b,c) for (ll a(b),a##end(c);a<=a##end;++a)
#define down(a,c,b) for (ll a(b),a##end(c);a>=a##end;--a)
#define uup(a,c,b) for (ll a(b),a##end(c);a<=a##end;++a)
#define udown(a,b,c) for (ll a(b),a##end(c);a>=a##end;--a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
struct inout{
static const ll ibufl=1<<25;
static const ll obufl=1<<25;
char in_buf[ibufl],out_buf[obufl],*inf,*ouf;
ll no;
operator bool(){
return !no;
}
inout(){
inf=in_buf;ouf=out_buf;
no=0;
}
void init(){
fread(in_buf,1,ibufl,stdin);
}
inout& operator >>(ll &a){
ll fh=1;
while(!(isdigit(*inf)||*inf=='-'||*inf=='\0'))++inf;
if(*inf=='\0'){
no=1;
a=0;
return *this;
}
if(*inf=='-')fh=-1,++inf;
a=0;
while(isdigit(*inf)){a=a*10+*inf-'0';++inf;}
a*=fh;
return *this;
}
inout& operator >>(char &a){
while(*inf==' '||*inf=='\n')++inf;
if(*inf=='\0'){
no=1;
a=0;
return *this;
}

a=*inf;
++inf;
return *this;
}
inout& operator >>(char *a){
while(*inf==' '||*inf=='\n')++inf;
if(*inf=0){
a='\0';
no=1;
return *this;
}
while(!(*inf==' '||*inf=='\n'||*inf=='\0')){*a=*inf;++inf;++a;}
*a='\0';
return *this;
}

inout& operator >>(double &a){
ll fh=1;
double s;
while(!(isdigit(*inf)||*inf=='-'||*inf=='.'||*inf=='\0'))++inf;
if(*inf=='\0'){
a=0;
no=1;
return *this;
}
if(*inf=='-')fh=-1,++inf;
a=0;
while(isdigit(*inf)){a=a*10+*inf-'0';++inf;}
if(*inf=='.'){
s=0.1;
++inf;
while(isdigit(*inf)){
a+=s*(*inf-'0');
++inf;
s*=0.1;
}
}
if(*inf=='E'||*inf=='e'){
ll ss;
++inf;
*this>>ss;
if(ss>0){
while(ss){
--ss;
a*=10;
}
}
if(ss<0){
while(ss){
++ss;
a/=10;
}
}

}
a*=fh;
return *this;
}
void writell(ll x){
if(x/10)writell(x/10);
*ouf=x%10+'0';
++ouf;
}
inout& operator <<(ll a){

if(a<0){*ouf='-';++ouf;a=-a;}
writell(a);
return *this;
}
static const ll sz=7;
inout& operator <<(char a){
*ouf=a;++ouf;
return *this;
}
inout& operator <<(char *a){
while(*a){
*ouf=*a;
++ouf;
++a;
}
return *this;
}
inout& operator <<(double a){
if(a<-eps){*ouf='-';++ouf;a=-a;}
writell((ll)a);
a-=(ll)a;
*ouf='.';
++ouf;
up(i,1,sz){
a=a*10;
*ouf=(ll)a+'0';
++ouf;
a-=(ll)a;
}
return *this;
}
void out(){
fwrite(out_buf,1,ouf-out_buf,stdout);
ouf=out_buf;
}
};
inout io;
struct ques{
ll l,r,t;
};
ques ask[201010];
ll askl(ques a,ques b){return a.l<b.l||a.l==b.l&&a.r<b.r;}
ll askr(ques a,ques b){return a.r<b.r||a.r==b.r&&a.l<b.l;}
ll a[201010],sum[1001010],tot,ans[201010];
void add(ll x){tot+=x*(sum[x]*2+1);++sum[x];}
void rm(ll x){tot-=x*(sum[x]*2-1);--sum[x];}
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
io.init();
ll n,s,l,r,m;
io>>n>>m;
up(i,1,n)io>>a[i];
up(i,1,m){
io>>ask[i].l>>ask[i].r;
ask[i].t=i;
}
sort(ask+1,ask+m+1,askl);
l=1,r=1000;
ll mid;
while(l<=r){
mid=(l+r)>>1;
if(sqr(mid)<=m)l=mid+1;
else r=mid-1;
}
s=l-1;
for(ll i=1,j=s;i<=m;i+=s,j=mmin(j+s,m)){sort(ask+i,ask+j+1,askr);}
l=ask[1].l;
r=ask[1].r;
up(i,l,r){
add(a[i]);
}
ans[ask[1].t]=tot;
up(i,2,m){
while(l>ask[i].l){--l;add(a[l]);}
while(r<ask[i].r){++r;add(a[r]);}
while(l<ask[i].l){rm(a[l]);++l;}
while(r>ask[i].r){rm(a[r]);--r;}
ans[ask[i].t]=tot;
}
up(i,1,m)io<<ans[i]<<endl;

io.out();
return 0;
}
文章目录
  1. 1. 简要题面
  2. 2. 不需简要题解(其实就是直接放代码)
|

博客使用Disqus作为评论系统