60分代码,后面全WA,蒟蒻求调
查看原帖
60分代码,后面全WA,蒟蒻求调
327295
GalwayGirl楼主2022/7/2 15:34
#include<bits/stdc++.h>
using namespace std;
struct xzh
{
	int l,r,id;
}q[51000];
long long fz,n,m,cnt[51000],a[51000],t,ans1[51000],ans2[51000];
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
bool cmp(xzh x,xzh y)
{
	int r1=ceil(x.l*1.0/t),r2=ceil(y.l*1.0/t);
	if(r1==r2)return x.r<y.r;
	return x.l<y.l;
}
long long calc(int x)
{
	return x*(1+x)/2;
}
long long gcd(int a,int b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
int main()
{
	n=read();
	m=read();
	for(long long i=1;i<=n;i++)a[i]=read();
	t=sqrt(n);
	for(long long i=1;i<=m;i++)
	{
		q[i].l=read();
		q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	long long l=1,r=0;
	for(long long i=1;i<=m;i++)
	{
		if(q[i].l==q[i].r)continue;
		while(r<q[i].r)
		{
			r++;
			fz-=calc(cnt[a[r]]-1);
			cnt[a[r]]++;
			fz+=calc(cnt[a[r]]-1);
		}
		while(r>q[i].r)
		{
			fz-=calc(cnt[a[r]]-1);
			cnt[a[r]]--;
			fz+=calc(cnt[a[r]]-1);
			r--;
		}
		while(l<q[i].l)
		{
			fz-=calc(cnt[a[l]]-1);
			cnt[a[l]]--;
			fz+=calc(cnt[a[l]]-1);
			l++;
		}
		while(l>q[i].l)
		{
			l--;
			fz-=calc(cnt[a[l]]-1);
			cnt[a[l]]++;
			fz+=calc(cnt[a[l]]-1);
		}
		ans1[q[i].id]=fz;
		ans2[q[i].id]=calc(q[i].r-q[i].l);
	}
	for(long long i=1;i<=m;i++)
	{
		if(ans1[i]==0)cout<<"0/1"<<endl;
		else
		{
			long long yue=gcd(ans1[i],ans2[i]);
			printf("%lld/%lld\n",ans1[i]/yue,ans2[i]/yue);
		}
	}
	return 0;
}
2022/7/2 15:34
加载中...