题解
莫队算法是局限性非常大的优化,离线+无修改,它通过邻近区间修改复杂度为 \(O(1)\) 的特性让区间排序,然后再做修改,排序的规则是按块排序,然后左端点 \(l\) 在一个块里的按右端点排序
code
#include<bits/stdc++.h>
using namespace std;
int a[50005];
struct node
{
int l,r,id,kuai;
}q[50004];
int ans[50004];
int num[50004]={0};
bool cmp(node b,node c)
{
if(b.kuai!=c.kuai) return b.kuai<c.kuai;
else if(b.kuai&1) return b.r<c.r;
else return b.r>c.r;
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
int sizes=sqrt(n);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
cin>>q[i].l>>q[i].r;
q[i].id=i;
q[i].kuai=(q[i].l-1)/sizes+1;
}
sort(q+1,q+m+1,cmp);
int sum=0;
for(int i=q[1].l;i<=q[1].r;i++) num[a[i]]++;// 预处理第一个区间
for(int i=1;i<=k;i++) sum+=num[i]*num[i];
ans[q[1].id]=sum;
int l=q[1].l,r=q[1].r;
for(int i=2;i<=m;i++)
{
while(r<q[i].r){r++;sum+=2*num[a[r]]+1;num[a[r]]++;}//挪步
while(l>q[i].l){l--;sum+=2*num[a[l]]+1;num[a[l]]++;}
while(l<q[i].l){sum-=2*num[a[l]]-1;num[a[l]]--;l++;}
while(r>q[i].r){sum-=2*num[a[r]]-1;num[a[r]]--;r--;}
ans[q[i].id]=sum;
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
标签:int,询问,id,num,P2709,kuai,排序,sum
From: https://www.cnblogs.com/pure4knowledge/p/18138206