莫队RE求助,只有最后一个点AC
查看原帖
莫队RE求助,只有最后一个点AC
279095
gargantuar楼主2021/10/12 19:37
#define ll long long
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
//	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=read
inline ll read(){
	register ll a=0;
	register char k=getchar();
	while(k<48||k>57)k=getchar();
	while(k>=48&&k<=57){
		a=a*10+k-48;
		k=getchar();
	}
	return a;
}
//	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=var
ll lk,rk,n,m,arr[514514],cnt[514514],sq;
ll i,fanss[514514],fansm[514514],ans;
//	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=mo's algorithm
struct qq{
	ll l,r,id;
	bool operator <(const qq&w)const{
		return l/sq==w.l/sq?r<w.r:l<w.l;
	}
}q[514514];
inline void add(ll id){
	ans+=(++cnt[arr[id]])*2-1;;
}
inline void del(ll id){
	ans-=(--cnt[arr[id]])*2+1;
}
//	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=	=main
int main(){
//	freopen("P1494_1.in","r",stdin);
//	freopen("a.txt","w",stdout);
	n=read(),m=read();//,sq=read();
	sq=sqrt(n);
	for(ll i=1;i<=n;++i)arr[i]=read();
	for(ll i=1;i<=m;++i){
		q[i].id=i;
		q[i].l=read();
		q[i].r=read();
	}
	sort(q+1,q+m+1);
	for(ll i=1;i<=m;++i){
		ll L=q[i].l,R=q[i].r;ll S=R-L+1;
		if(L==R)continue;
		while(lk>L)add(--lk);
		while(lk<L)del(lk++);
		while(rk<R)add(++rk);
		while(rk>R)del(rk--);
		fanss[q[i].id]=ans-1-S;
		fansm[q[i].id]=S*(S-1);
	}
	for(ll i=1;i<=m;++i){
		if(fanss[i]==0&&q[i].l==q[i].r){
			printf("0/1\n");
			continue;
		}
		ll g=__gcd(fanss[i],fansm[i]);
		printf("%lld/%lld\n",fanss[i]/g,fansm[i]/g);
	}
}
2021/10/12 19:37
加载中...