1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 1e9 using namespace std; typedef long long ll; struct { ll l,r,sqi,id; }; bool cmp(Q u,Q v){ if(u.sqi==v.sqi)return u.r<v.r; return u.sqi<v.sqi; } Q query[50005]; ll a[50005],ans[50005][2],n,m,size; ll cnt[50005]={0},tot=0; ll sqr(ll t){return t*t;} void update(ll o,ll id){ tot-=sqr(cnt[a[id]]), cnt[a[id]]+=o, tot+=sqr(cnt[a[id]]); } ll gcd(ll a,ll b){ return (!b)?a:gcd(b,a%b); } void init(){ ll i,j; scanf("%lld%lld",&n,&m); for(size=1;size*size<n;size++); for(i=1;i<=n;i++) scanf("%lld",&a[i]); for(i=1;i<=m;i++) scanf("%lld%lld",&query[i].l,&query[i].r), query[i].sqi=(query[i].l-1)/size, query[i].id=i; sort(query+1,query+m+1,cmp); } void solve(){ ll L=1,R=0,_l,_r,_id,fz,fm,p; for(int i=1;i<=m;i++){ _l=query[i].l,_r=query[i].r; _id=query[i].id; for(;R<_r;R++) update(1,R+1); for(;R>_r;R--) update(-1,R); for(;L<_l;L++) update(-1,L); for(;L>_l;L--) update(1,L-1); if(_l==_r){ ans[_id][0]=0,ans[_id][1]=1; continue; } fz=tot-(_r-_l+1),fm=(_r-_l+1)*(_r-_l); p=gcd(fm,fz); fz/=p,fm/=p; ans[_id][0]=fz,ans[_id][1]=fm; } for(int i=1;i<=m;i++) printf("%lld/%lldn",ans[i][0],ans[i][1]); } int main(){ init(); solve(); return 0; }
|
近期评论