如题
代码开了long long,其他应该没问题
前6个点能过,后面4个点全wa
7号点数据本地测试没问题,在IDEONE测试时出锅,初步怀疑是编译环境问题
希望dalao指明问题所在,不胜感激
#include<bits/stdc++.h>
using namespace std;
const long long MAXN=50010;
long long n,m,Size,length,l=1,r=0,ans=0;
long long belong[MAXN],num[MAXN],cnt[MAXN],ANS[MAXN],LENGTH[MAXN];
struct kuai{
long long l,r,id,length;
}q[MAXN];
inline long long read(void)
{
long long ans=0;
char a=getchar();
while(!isdigit(a))
a=getchar();
while(isdigit(a))
{
ans=ans*10+a-'0';
a=getchar();
}
return ans;
}
inline bool cmp(const kuai &a,const kuai &b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
}
inline void add(long long x)
{
ans+=cnt[num[x]];
++cnt[num[x]];
}
inline void del(long long x)
{
--cnt[num[x]];
ans-=cnt[num[x]];
}
inline long long calc(long long x)
{
if(x&1)
return (x-1)/2*x;
else
return x*(x-1)/2;
}
long long GCD(long long a,long long b)
{
return b>0?GCD(b,a%b):a;
}
signed main(void)
{
freopen("C:\\Users\\HP\\Desktop\\debug.txt","r",stdin);
freopen("C:\\Users\\HP\\Desktop\\wa.txt","w",stdout);
n=read();m=read();
Size=sqrt(m*2.0/3);
length=ceil(1.0*n/Size);
for(long long i=1;i<=length;++i)
for(long long j=(i-1)*Size+1;j<=i*Size;++j)
belong[j]=i;
for(long long i=1;i<=n;++i)
num[i]=read();
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);
for(long long i=1;i<=m;++i)
{
long long L=q[i].l,R=q[i].r;
while(l<L)
del(l++);
while(L<l)
add(--l);
while(r<R)
add(++r);
while(R<r)
del(r--);
ANS[q[i].id]=ans;
LENGTH[q[i].id]=(q[i].r-q[i].l+1)*(q[i].r-q[i].l)/2;
}
for(long long i=1;i<=m;++i)
{
//printf("cases%d:",i);
if(LENGTH[i]==0||ANS[i]==0)
printf("0/1\n");
else
{
long long TEMP=__gcd(ANS[i],LENGTH[i]);
printf("%lld",ANS[i]/TEMP);
printf("/");
printf("%lld\n",LENGTH[i]/TEMP);
}
}
return 0;
}