我死也找不出为啥runtime error,有没有dalao指点迷津
查看原帖
我死也找不出为啥runtime error,有没有dalao指点迷津
307731
白手楼主2020/10/1 21:45
#include <bits/stdc++.h>
using namespace std;
const int Max=1e5+5;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return x*f;
}
struct st
{
    long long l,r,k;
}q[Max];
int a[Max];
long long ans1[Max],ans2[Max],num[Max],pos[Max];
long long top=0;
bool cmp(st a,st b)
{
    return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
}
void add(int pos)
{
    num[a[pos]]++;
    if(num[a[pos]]>1) top+=((num[a[pos]])*(num[a[pos]]-1)/2-(num[a[pos]]-1)*(num[a[pos]]-2)/2);
}
void del(int pos)
{
    num[a[pos]]--;
    if(num[a[pos]]>0) top-=((num[a[pos]]+1)*(num[a[pos]])/2-(num[a[pos]]-1)*(num[a[pos]])/2);
}
long long gcd(long long x,long long y )
{
    if(x<y) swap(x,y);
    int r;
    while(y>0)
    {
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}
int main()
{
 int n=read();
 int m=read();
 int Size=sqrt(n);
 for(int i=1;i<=n;i++)
 {
     a[i]=read();
     pos[i]=(i-1)/Size+1;
 }
 for(int i=1;i<=m;i++)
 {
     q[i].l=read(),q[i].r=read();
     q[i].k=i;
 }
 sort(q+1,q+1+m,cmp);
 int L=1,R=0;
 for(int i=1;i<=m;i++)
 {
     while(q[i].l<L) add(--L);
     while(q[i].r>R) add(++R);
     while(q[i].l>L) del(L++);
     while(q[i].r<R) del(R--);
     ans1[q[i].k]=top;
     ans2[q[i].k]=(q[i].r-q[i].l+1)*(q[i].r-q[i].l)/2;
 }
 int Gcd;
 for(int i=1;i<=m;i++)
 {
    Gcd=gcd(ans1[i],ans2[i]);
     cout<<ans1[i]/Gcd<<'/'<<ans2[i]/Gcd<<endl;//}
 }
 return 0;
}

2020/10/1 21:45
加载中...