Code:
#include#include #include #include #include #include # define REP(i,a,n) for(int i=a;i<=n;++i) # define CLR(d,a)memset(d,a,sizeof(d));using namespace std;void SetIO(string a){ string in=a+".in"; freopen(in.c_str(),"r",stdin);}const int maxn=60000+5;int n,m,col[maxn];struct Asks{ int l,r; Asks(int l=0,int r=0):l(l),r(r){}}asks[maxn];void Read(){ scanf("%d%d",&n,&m); REP(i,1,n) scanf("%d",&col[i]); REP(i,1,m){ int a,b; scanf("%d%d",&a,&b); asks[i]=Asks(a,b); }}int block;int belong[maxn], ranking[maxn];int get_belong(int i){ return (i-1)/block+1;}bool cmp(int i,int j){ if(belong[asks[i].l]==belong[asks[j].l]) return asks[i].r r2;--i) update(col[i],-1); if(l>l2) for(int i=l-1;i>=l2;--i)update(col[i],1); else REP(i,l,l2-1)update(col[i],-1); l = l2; r = r2; }}long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);}long long up[maxn], down[maxn];void Print(){ REP(i,1,m){ int l=asks[i].l; int r=asks[i].r; if(l==r){ up[i]=0; down[i]=1; } else{ int length=r-l+1; up[i]=ans[i]-length; down[i]=(long long)length*(length-1); if(up[i]==0){ up[i]=0; down[i]=1; continue; } long long k=gcd(up[i],down[i]); up[i]/=k; down[i]/=k; } } REP(i,1,m) printf("%lld/%lld\n",up[i],down[i]);}int main(){ SetIO("input"); Read(); Build(); Work(); Print(); return 0;}