莫队入门1 P1494 [国家集训队] 小 Z 的袜子

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=5e4+5;
 5 ll a[N],blg[N],cnt[N];
 6 string ans[N];
 7 inline ll gcd(ll a,ll b){
 8     return !b?a:gcd(b,a%b);
 9 }
10 struct event
11 {
12     int l,r,pos;
13 }e[N]; 
14 void build(int n)
15 {
16     int cnt=sqrt(n);
17     int tot=n/cnt;
18     if(n%cnt)tot++;
19     for(int i=1;i<=n;i++)
20     blg[i]=(i-1)/cnt+1;    
21     blg[n]=tot;
22 }
23 static bool cmp(event &a,event &b){
24     return (blg[a.l] ^ blg[b.l]) ? blg[a.l] < blg[b.l] : ((blg[a.l] & 1) ? a.r < b.r : a.r > b.r);
25 }
26 int main()
27 {
28     //freopen("P1494_1.in","r",stdin);
29     int n,m;
30     scanf("%d%d",&n,&m);
31     for(int i=1;i<=n;i++)
32     scanf("%d",&a[i]);
33     for(int i=1;i<=m;i++)
34     {
35         scanf("%d%d",&e[i].l,&e[i].r);
36         e[i].pos=i;
37     }
38     build(n);
39     sort(e+1,e+m+1,cmp);
40     ll l=1,r=0,up=0;
41     for(int i=1;i<=m;i++)
42     {
43         ll ql=e[i].l,qr=e[i].r;
44         ll down=1ll*(qr-ql+1)*(qr-ql)/2;
45         while(l<ql)
46         {
47             up+=1-cnt[a[l]];
48             --cnt[a[l]];
49             l++;
50             
51         }
52         while(l>ql)
53         {
54             up+=cnt[a[--l]];
55             cnt[a[l]]++;
56             
57         }
58         while(r<qr)
59         {
60             up+=cnt[a[++r]];
61             cnt[a[r]]++;
62             
63         }
64         while(r>qr)
65         {
66             up+=1-cnt[a[r]];
67             --cnt[a[r]];
68             r--;
69                 
70         }
71         if(ql==qr){
72         ans[e[i].pos]="0/1";
73         continue;
74         }
75         ll gd=gcd(up,down);
76         ans[e[i].pos]=to_string(up/gd)+"/"+to_string(down/gd);
77     }
78     for(int i=1;i<=m;i++)cout<endl;
79     return 0;    
80 }