暑假集训Day14 I (莫队)

本文主要是介绍暑假集训Day14 I (莫队)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接在这里：Problem - I - Codeforces

应该是一个比较经典的莫队题，一开始想的是这个数据范围肯定是要搞一个前缀和，后来发现如果弄前缀和的话区间还是不好操作，但是如果一位一位的算的话还是可以的，所以想到了莫队。

莫队要分块！！！不分块会T！

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef __int64 LL;
 4 const int MAX=2e6+6;
 5 LL n,t,a[MAX];
 6 LL L,R,ans[MAX],cnt[MAX];
 7 LL c[MAX];
 8 struct Node{
 9     LL l,r,no;
10 }stu[MAX];
11 bool cmp(Node x,Node y){
12     if (c[x.l]!=c[y.l]) return x.l<y.l;
13     return x.r<y.r;
14 }
15 int main(){
16     freopen ("i.in","r",stdin);
17     freopen ("i.out","w",stdout);
18     LL i,j,an;
19     scanf("%I64d%I64d",&n,&t);
20     for (i=1;i<=n;i++) scanf("%I64d",a+i);
21     for (i=1,j=(LL)sqrt(n);i<=n;i++) c[i]=i/j;
22     for (i=1;i<=t;i++){
23         scanf("%I64d%I64d",&stu[i].l,&stu[i].r);
24         stu[i].no=i;
25     }
26     sort(stu+1,stu+t+1,cmp);
27     L=1,R=an=0;
28     memset(cnt,0,sizeof(cnt));
29     for (i=1;i<=t;i++){
30         //cout<<stu[i].l<<' '<<stu[i].r<<endl;
31         while (R<stu[i].r){
32             R++;an+=(cnt[a[R]]*2+1)*a[R];
33             cnt[a[R]]++;
34         }//cout<<an<<" fuck"<<endl;
35         while (L>stu[i].l){
36             L--;an+=(cnt[a[L]]*2+1)*a[L];
37             cnt[a[L]]++;
38         }
39         while (R>stu[i].r){
40             an-=((cnt[a[R]]-1)*2+1)*a[R];
41             cnt[a[R]]--;
42             R--;
43         }
44         while (L<stu[i].l){
45             an-=((cnt[a[L]]-1)*2+1)*a[L];
46             cnt[a[L]]--;
47             L++;
48         }
49         ans[stu[i].no]=an;
50     }
51     for (i=1;i<=t;i++) printf("%I64d\n",ans[i]);
52     return 0;
53 }

这篇关于暑假集训Day14 I (莫队)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！