牛客小白月赛17 G 区间求和

ゝ一世哀愁。 2023-10-11 09:36 20阅读 0赞

[传送门][Link 1]

题意：

![1633695-20190914120458984-426750226.png][]

题解：

原本想着使用暴力方法：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 using namespace std;
     7 typedef long long ll;
     8 const int maxn=1e5+5;
     9 const int mod=26;
    10 int v[maxn],w[maxn];
    11 int main()
    12 {
    13     int n,m;
    14     scanf("%d%d",&n,&m);
    15     for(int i=1;i<=n;++i)
    16     {
    17         scanf("%d",&v[i]);
    18         //sum[i]=sum[i-1]+v[i];
    19     }
    20     while(m--)
    21     {
    22         int l,r,ans=0;
    23         memset(w,0,sizeof(w));
    24         scanf("%d%d",&l,&r);
    25         for(int i=l;i<=r;++i)
    26         {
    27             ans=ans+w[v[i]]*v[i];
    28             w[v[i]]++;
    29             ans=ans+w[v[i]]*v[i];
    30         }
    31         printf("%d\n",ans);
    32     }
    33     return 0;
    34 }

但是对每一次的询问都对应一次区间\[l,r\]的遍历，最大复杂度就是1e5\*1e5（还以为数据会水过）

这个时候就要使用莫队算法(优雅的暴力)来解决了

莫队算法就是先分块，再所有询问的区间按某种方式进行排序，一个一个区间的找结果。具体看代码

以多少分一块看具体情况，这个不固定

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<map>
     6 using namespace std;
     7 typedef long long ll;
     8 const int maxn=1e5+5;
     9 const int mod=26;
    10 const int block=300;
    11 ll w[maxn],ans,v[maxn],sum[maxn];
    12 struct shudui
    13 {
    14     ll l,r,id;
    15     bool operator<(const shudui x)const //<号代表从大到小排序
    16     {
    17         if(l/block==x.l/block)
    18             return r<x.r;
    19         else return l/block<x.l/block;
    20     }
    21 }m[maxn];
    22 ll n,k;
    23 void add(ll i)
    24 {
    25     ans=ans+w[v[i]]*v[i];   //w存这个数字出现的次数
    26     w[v[i]]++;
    27     ans=ans+w[v[i]]*v[i];  //如果一个数字出先2次，那么可以第一次遇见它只加上它
    28 }               //再一次遇见再加一次。比如3出现2次
    29 void del(ll i)                        //第一次ans=3
    30 {
    31     ans=ans-w[v[i]]*v[i];      //第二次ans+3+w[3]*3 ==3*2+3*2(最后的结果)
    32     w[v[i]]--;
    33     ans=ans-(w[v[i]]*v[i]);
    34 }
    35 int main()
    36 {
    37     scanf("%lld%lld",&n,&k);
    38     for(ll i=1;i<=n;++i)
    39     {
    40         scanf("%lld",&v[i]);
    41     }
    42     for(ll i=1;i<=k;++i)
    43     {
    44         scanf("%lld%lld",&m[i].l,&m[i].r);
    45         m[i].id=i;
    46     }
    47     sort(m+1,m+1+k);
    48     ll l=0,r=0;
    49     ans=0;
    50     for(ll i=1;i<=k;++i)
    51     {
    52         while(l<m[i].l)
    53             del(l),l++;
    54         while(l>m[i].l)
    55             add(--l);
    56         while(r>m[i].r)
    57             del(r),r--;
    58         while(r<m[i].r)
    59             add(++r);
    60         sum[m[i].id]=ans;
    61     }
    62     for(ll i=1;i<=k;++i)
    63     {
    64         printf("%lld\n",sum[i]);
    65     }
    66     return 0;
    67 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11518846.html

[Link 1]: https://ac.nowcoder.com/acm/contest/1085/G
[1633695-20190914120458984-426750226.png]: https://img2018.cnblogs.com/blog/1633695/201909/1633695-20190914120458984-426750226.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif