查询区间每个数出现的个数,离线算法,O(nsqrt(n))
一、普通莫队
题目链接
https://www.luogu.com.cn/problem/P2709
题目大意
题目代码
#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
const int N = 5e4 + 5;
using namespace std;
int n,m,k,block;
struct node{
int l,r,id;
}q[N];
ll a[N],cnt[N],ans[N],sum;
bool cmp(const node& a,const node& b){
if(a.l / block != b.l / block) return a.l < b.l;
return a.r < b.r;
}
void add(int x){
sum -= cnt[x] * cnt[x];
++cnt[x];
sum += cnt[x] * cnt[x];
}
void del(int x){
sum -= cnt[x] * cnt[x];
--cnt[x];
sum += cnt[x] * cnt[x];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
block = sqrt(n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
for(int i = 1;i <= m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id = i;
sort(q + 1,q + m + 1,cmp);
for(int i = 1,l = 1,r = 0;i <= m;++i){
while(l > q[i].l) add(a[--l]);
while(r < q[i].r) add(a[++r]);
while(l < q[i].l) del(a[l++]);
while(r > q[i].r) del(a[r--]);
ans[q[i].id] = sum;
}
for(int i = 1;i <= m;++i){
printf("%lld\n",ans[i]);
}
return 0;
}
标签:cnt,int,sum,add,include,莫队,block
From: https://www.cnblogs.com/gebeng/p/18137048