bzoj 2038: [2009国家集训队]小Z的袜子(hose)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define ll long long
 7 #define M 50009
 8 using namespace std;
 9 struct data
10 {
11     ll l,r,a,b,id;
12 }da[M];
13 ll s,n,m,c[M],block,ku,pos[M],su[M];
14 bool cmp(data a1,data a2)
15 {
16     if(pos[a1.l]==pos[a2.l])
17       return a1.r<a2.r;
18     return pos[a1.l]<pos[a2.l];
19 }
20 bool cmp1(data a1,data a2)
21 {
22     return a1.id<a2.id;
23 }
24 ll sqr(ll a1)
25 {
26     return a1*a1;
27 }
28 void up(int a1,int a2)
29 {
30     if(a1) 
31       {
32         s-=sqr(su[c[a1]]);
33         su[c[a1]]+=a2;
34         s+=sqr(su[c[a1]]);
35       }
36     return;
37 }
38 ll gcd(ll a1,ll a2)
39 {
40     ll a3=a1%a2;
41     for(;a3;)
42       {
43         a1=a2;
44         a2=a3;
45         a3=a1%a2;
46       }
47     return a2;
48 }
49 int main()
50 {
51     scanf("%lld%lld",&n,&m);
52     for(int i=1;i<=n;i++)
53       scanf("%lld",&c[i]);
54     for(int i=1;i<=m;i++)
55       {
56         scanf("%lld%lld",&da[i].l,&da[i].r);
57         da[i].id=i;
58       }
59     block=(int)sqrt(n);
60     ku=n/block;
61     if(n%block)
62       ku++;
63     for(int i=1;i<=n;i++)
64       pos[i]=(i-1)/block+1;
65     sort(da+1,da+m+1,cmp);
66     int h=0,t=0;
67     for(int i=1;i<=m;i++)
68       {
69         for(;t<da[i].r;t++)
70           up(t+1,1);
71         for(;t>da[i].r;t--)
72           up(t,-1);
73         for(;h<da[i].l;h++)  
74           up(h,-1);
75         for(;h>da[i].l;h--)
76           up(h-1,1);
77         if(da[i].l==da[i].r)
78           {
79             da[i].a=0;
80             da[i].b=1;
81             continue;
82           }
83         ll len=da[i].r-da[i].l+1;
84         da[i].a=s-len;
85         da[i].b=len*(len-1);
86         ll k=gcd(da[i].a,da[i].b);
87         da[i].a/=k;
88         da[i].b/=k;
89       }
90     sort(da+1,da+m+1,cmp1);
91     for(int i=1;i<=m;i++)
92       printf("%lld/%lld\n",da[i].a,da[i].b);
93     return 0;
94 }