求助一个(玄学的?)错误原因
查看原帖
求助一个(玄学的?)错误原因
223529
huangjiarui楼主2021/11/14 18:11

求助,这里有一个奇怪的错误,不知道为什么。

原代码是这样(90pt90pt,最后一个点RERE):

#include<algorithm>
#include<cmath>
#include<cstdio>
const int MaxN = 50000;
struct query{
	long long l,r,num;
}q[MaxN+10];
long long gcd(long long x,long long y)
{
	return (y == 0)?x:gcd(y,x%y);
}
struct fs{
	long long fm,fz;
	
	fs(long long z = 0,long long m = 1)
	{
		long long g = gcd(z,m);
		fm = m/g,fz = z/g;
	}
}ans[MaxN+10];
long long block[MaxN+10],col[MaxN+10],t[MaxN+10],l,r,len,n,m,cnt;
bool cmp(query x,query y)
{
	return block[x.l] < block[y.l] || (block[x.l] == block[y.l] && ((x.r > y.r)^(block[x.l]&1)));
}
int main()
{
	scanf("%lld%lld",&n,&m),len = sqrt(n);
	for (int i = 1;i <= n;++i)
		scanf("%lld",&col[i]),block[i] = block[i-1]+(i == block[i-1]*len+1);
	for (int i = 1;i <= m;++i)
		scanf("%lld%lld",&q[i].l,&q[i].r),q[i].num = i;
	std::sort(q+1,q+m+1,cmp);
	l = r = 1,cnt = 0,t[col[l]] = 1;
	for (int i = 1;i <= m;++i)
	{
		while (r < q[i].r)
			cnt += t[col[++r]],++t[col[r]];
		while (r > q[i].r)
			cnt -= t[col[r]]-1,--t[col[r--]];
		while (l > q[i].l)
			cnt += t[col[--l]],++t[col[l]];
		while (l < q[i].l)
			cnt -= t[col[l]]-1,--t[col[l++]];
		if (r-l == 0)
			ans[q[i].num] = fs(0,1);
		else
			ans[q[i].num] = fs(cnt,(r-l+1)*(r-l)/2);
	}
	for (int i = 1;i <= m;++i)
		printf("%lld/%lld\n",ans[i].fz,ans[i].fm);
	return 0;
}

然后把中间cmpcmp函数部分改为:

bool cmp(query x,query y)
{
	return block[x.l] < block[y.l] || (block[x.l] == block[y.l] && ((x.r < y.r)^(block[x.l]&1)^1));
}

ACAC了。

求助原因

RERE记录ACAC记录)

2021/11/14 18:11
加载中...