[求助]萌新刚学会莫队,全T了
查看原帖
[求助]萌新刚学会莫队,全T了
209808
银河AI楼主2021/1/8 22:18

莫队全T,求助哪里错了谢谢

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,len;
ll a[50001],ans[50001],s[50001],sum;
struct query{
	ll l,r,num;
}q[50001];
inline bool cmp(query x,query y){
	return (x.r/len)==(y.r/len)?x.l<y.l:x.r<y.r;
}
inline void del(ll x){
	sum-=2*s[a[x]]-1;
	s[a[x]]--;
}
inline void add(ll x){
	sum+=2*s[a[x]]+1;
	s[a[x]]++;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	len=sqrt(n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].num=i;
	}
	ll l=1,r=0;
	for(int i=1;i<=m;i++){
		ll ql=q[i].l,qr=q[i].r;
		while(l<ql) del(l),l++;
		while(l>ql) l--,add(l);
		while(r>qr) del(r),r--;
		while(r<qr) r++,add(r);
		ans[q[i].num]=sum;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}	
2021/1/8 22:18
加载中...