【BZOJ 2038】[2009国家集训队]小Z的袜子(hose)

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #define ll long long
 5 using namespace std;
 6 const int N=50010;
 7 struct node{int l,r,id;
 8             ll a,b;}a[N];
 9 int n,m;
10 ll ans,sum[N];
11 int c[N],bel[N];
12 bool cmp(node a,node b){
13     if (bel[a.l]==bel[b.l]) return (a.r<b.r);
14     return a.l<b.l;
15 }
16  
17 bool cmp1(node a,node b){return a.id<b.id;}
18 ll sqr(ll x){return x*x;}
19 void init(){
20     scanf("%d%d",&n,&m);
21     for (int i=1;i<=n;i++) scanf("%d",&c[i]);
22     int block=int(sqrt(n));
23     for (int i=1;i<=n;i++) bel[i]=(i/block)+1;
24     for (int i=1;i<=m;i++){
25         scanf("%d%d",&a[i].l,&a[i].r);
26         a[i].id=i;
27     }
28 }
29  
30 void updata(int wz,int ch){
31     ans-=sqr(sum[c[wz]]);
32     sum[c[wz]]+=ch;
33     ans+=sqr(sum[c[wz]]);
34 }
35  
36 ll gcd(ll a,ll b){
37     if (a%b==0) return b;
38     return gcd(b,a%b);
39 }
40  
41 int main(){
42     init();
43     sort(a+1,a+m+1,cmp);
44     int l=1,r=0;
45     for (int i=1;i<=m;i++){
46         for (;r<a[i].r;r++) updata(r+1,1);
47         for (;r>a[i].r;r--) updata(r,-1);
48         for (;l<a[i].l;l++) updata(l,-1);
49         for (;l>a[i].l;l--) updata(l-1,1);
50         if (a[i].l==a[i].r) {a[i].a=0,a[i].b=1;continue;}
51         a[i].a=ans-(a[i].r-a[i].l+1);
52         a[i].b=(ll)(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
53         ll tmp=gcd(a[i].a,a[i].b);
54         a[i].a/=tmp;a[i].b/=tmp;
55     }
56     sort(a+1,a+m+1,cmp1);
57     for (int i=1;i<=m;i++) printf("%lld/%lld\n",a[i].a,a[i].b);
58 }