首页 > 其他 > 详细

小B的询问

时间:2017-07-11 20:42:48      阅读:299      评论:0      收藏:0      [点我收藏+]

OJ题号:BZOJ3781、洛谷2709

思路:

根据平方和公式,$(a+b)^2=a^2+2ab+b^2$,即当$c_i$增加$1$时,新的答案增加$2C_i+1$,减少时亦同。莫队求解即可。

 1 #include<cstdio>
 2 #include<cctype>
 3 #include<cmath>
 4 #include<algorithm>
 5 inline int getint() {
 6     char ch;
 7     while(!isdigit(ch=getchar()));
 8     int x=ch^0;
 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^0);
10     return x;
11 }
12 int base;
13 struct Que {
14     int l,r,id;
15     bool operator < (const Que &x) const {
16         return (r/base<x.r/base)?true:((r/base==x.r/base)?(l<x.l):false);
17     }
18 };
19 const int K=50001;
20 int cnt[K]={0},Ans=0;
21 inline void inc(const int x) {
22     Ans+=cnt[x]<<1|1;
23     cnt[x]++;
24 }
25 inline void dec(const int x) {
26     cnt[x]--;
27     Ans-=cnt[x]<<1|1;
28 }
29 int main() {
30     int n=getint(),m=getint();getint();
31     base=(int)sqrt(n);
32     int a[n];
33     for(int i=0;i<n;i++) a[i]=getint();
34     Que q[m];
35     for(int i=0;i<m;i++) {
36         q[i].l=getint()-1;
37         q[i].r=getint()-1;
38         q[i].id=i;
39     }
40     std::sort(&q[0],&q[m]);
41     int ans[m];
42     for(int i=0,l=0,r=-1;i<m;i++) {
43         while(r<q[i].r) inc(a[++r]);
44         while(r>q[i].r) dec(a[r--]);
45         while(l<q[i].l) dec(a[l++]);
46         while(l>q[i].l) inc(a[--l]);
47         ans[q[i].id]=Ans;
48     }
49     for(int i=0;i<m;i++) printf("%d\n",ans[i]);
50     return 0;
51 }

 

小B的询问

原文:http://www.cnblogs.com/skylee03/p/7152080.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!