注册登录

莫队算法----区间求和

连接   https://ac.nowcoder.com/acm/contest/1085/G

链接：https://ac.nowcoder.com/acm/contest/1085/G
来源：牛客网

题目描述

小sun最近突然对区间来了兴趣，现在他有这样一个问题想问问你：
给你n个数，每个数为aia_iai​，现在有m个询问，每个询问l,r，需要求出：
∑i=lrai∗num(ai)\sum_{i=l}^r a_i*num(a_i)∑i=lr​ai​∗num(ai​)

num(ai)num(a_i)num(ai​)代表aia_iai​在这个区间中出现的次数。
你能帮帮他吗？

输入描述:

第一行，两个整数n,m

第二行，总共n个数，代表这个数列

接下来m行，每行两个整数l,r，代表一个询问
知识兔

输出描述:

输出总共m行，对于每个询问，输出这个询问对应的答案
知识兔
示例1

输入

复制
10 5
1 3 2 4 5 6 4 5 6 7
1 5
2 5
3 4
1 10
3 7
知识兔

输出

复制
15
14
6
73
29
题目大意：在制定的一段区间内求arr[i]*cnt[arr[i]]之和，即一段区间内某一个数乘以该数字出现的次数。
莫队算法   一篇讲的很好的博客  https://www.cnblogs.com/WAMonster/p/10118934.html
知识兔
#include<bits/stdc++.h>using namespace std;typedef long long ll;ll ans=0;const int N=1E5+7;ll arr[N],cnt[N];ll base;ll a[N];struct stu{    ll l,r,k,id;    bool friend operator < (const stu &x,const stu &y){        if(x.k!=y.k) return x.l<y.l;        return x.r<y.r;     }}node[N];void add(int x){    ans+=(2*cnt[arr[x]]+1) *arr[x];    cnt[arr[x]]++;}void del(int  x){    ans-=(2*cnt[arr[x]]-1) *arr[x];    cnt[arr[x]]--;}int main(){    int n,m;    cin>>n>>m;    base=sqrt(n);    for(int i=1;i<=n;i++) scanf("%lld",&arr[i]);    for(int i=1;i<=m;i++){        ll l,r;        scanf("%lld%lld",&l,&r);        node[i].id=i;        node[i].l=l;        node[i].r=r;        node[i].k=l/base;     }    ll l=1,r=0;    sort(node+1,node+1+m);    for(int i=1;i<=m;i++){        int ql=node[i].l,qr=node[i].r;        while(l<ql) del(l++);        while(l>ql) add(--l);        while(r>qr) del(r--);        while(r<qr) add(++r);        a[node[i].id]=ans;    }    for(int i=1;i<=m;i++) printf("%lld\n",a[i]);    return 0;} 
疑问1：为什么加数的时候是++r和--l而删除的时候却是l++或者r--？
　　　　因为我们规定，区间边界也会记录在内，因此当del的时候是先删除当前值，在自增或者自减，而add的时候我们是对下一个数的操作，因此要先自增或者自减再操作，这样才能保证增加的时候把最后边界加上，减少的时候不把边界减去；
疑问2：为什么ans+/-=（2*cnt[arr[x]]+/-1）*arr[x];？
　　　　cnt[arr[x]]是数arr[x]当前的数量，arr[x]*cnt[arr[x]]是对之前的cnt[arr[x]]个arr[x]每一个在加上个arr[x]， 又新增的一个arr[x]，因此要再加上arr[x]*(cnt[arr[x]]+1)，最终结果就是（2*cnt[arr[x]]+/-1）*arr[x]
　　　　减少的时候应该是减去arr[x]*(cnt[arr[x]]-1)+arr[x]*cnt[arr[x]];

 


计算机