题目：点击此处
思路：求出每个区间中从每种颜色中选两个 的种类数的和
如果和为零输出0/1
否则输出 和/ ( (r-l+1)*(r-l)/2 ) 最简形式
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <algorithm> #define ll long long using namespace std; const int maxn=1e6+5; struct node { ll l,r,i; }pos[maxn]; ll n,block,q,l,r,ans=0; ll mp[maxn],c[maxn],a[maxn]; struct an{ ll zi,mu; }answer[maxn]; bool cmp(node a,node b) { if(a.l/block!=b.l/block) return a.l/block<b.l/block; return a.r<b.r; } void add(ll x) { ans+=mp[a[x]]; mp[a[x]]++; } void remov1e(ll x) { mp[a[x]]--; ans-=mp[a[x]]; } int main() { scanf("%lld%lld",&n,&q);block=sqrt(1.0*n); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]); for(ll i=1;i<=q;i++) { scanf("%lld%lld",&pos[i].l,&pos[i].r); pos[i].i=i; } sort(pos+1,pos+1+q,cmp); ll cl=pos[1].l,cr=cl-1; for(ll i=1;i<=q;i++) { l=pos[i].l,r=pos[i].r; while(cl<l) { remov1e(cl); cl++; } while(cl>l) { add(cl-1); cl--; } while(cr<r) { add(cr+1); cr++; } while(cr>r) { remov1e(cr); cr--; } ll zi=ans; if(zi==0) { answer[pos[i].i].zi=0; answer[pos[i].i].mu=1; } else { ll mu=(r-l+1)*(r-l)/2; ll g=__gcd(zi,mu); zi/=g;mu/=g; answer[pos[i].i].zi=zi; answer[pos[i].i].mu=mu; } } for(ll i=1;i<=q;i++) cout<<answer[i].zi<<"/"<<answer[i].mu<<endl; return 0; }
