题目链接:https://www.luogu.org/problemnew/show/P2709
题目大意:中文题目
具体思路:莫队入门题,按照离线的方式打的,对每一个区间进行分块和编号,如果在同一个块里面就按照右端点从小到大排列,如果不在同一个块里面就按照块的下标开始排序,这里的块是按照数列分块里面的方法来进行的,查询每个区间的值就可以了。
对于l,r指针的移动,当l<q[i].l的时候,我们需要将l指针往右移动,所以假设t为当前的颜色,ans为未移动的时候的值,首先去除掉原来的值的影响,ans-=t*t,然后再加上新的值的影响,ans+=(t+1)*(t+1),因为我们是先进行加减操作,所以这种情况下ans=-(t-1)*(t-1)+t*t=2*t-1.其他情况同理。
AC代码:
#include<iostream>
#include<stack>
#include<cstring>
#include<iomanip>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
# define ll long long
const int maxn = 2e5+;
int a[maxn];
struct node{
int l,r,pos,id;
bool friend operator < (node t1,node t2){
if(t1.pos==t2.pos)return t1.r<t2.r;
return t1.pos<t2.pos;
}
}q[maxn];
int ans[maxn],vis[maxn];
int main(){
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
int block=(int)sqrt(n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=;i<=m;i++){
scanf("%d %d",&q[i].l,&q[i].r);
q[i].pos=(q[i].l-)/block+;
q[i].id=i;
}
sort(q+,q+m+);
int tmp=;
int l=,r=;
for(int i=;i<=m;i++){
while(l<q[i].l)vis[a[l]]--,tmp-=(*vis[a[l]]+),l++;
while(l>q[i].l)l--,vis[a[l]]++,tmp+=*vis[a[l]]-;
while(r<q[i].r)r++,vis[a[r]]++,tmp+=*vis[a[r]]-;
while(r>q[i].r)vis[a[r]]--,tmp-=*vis[a[r]]+,r--;
ans[q[i].id]=tmp;
}
for(int i=;i<=m;i++){
printf("%d\n",ans[i]);
}
return ;
}