bzoj - 2038: [2009國家集訓隊]小Z的襪子(hose)

　題目鏈接:http://www.lydsy.com/JudgeOnline/problem.php?id=2038

　莫隊算法可以解決一類不修改、離線查詢問題。而這題可以用莫隊來做。

　*我是看這個論文學會的：（鏈接~）

　其實莫隊就是一種優化的暴力，只是把查詢都離線預先按照規則去排序，然后依次暴力處理這些詢問。

　有兩種做法，目前只會寫分段解決。先把1~n分成sqrt(n) ，?u = sqrt(n) ，?m個查詢先按照第幾個塊排序，再按照 R排序。

　代碼如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 const int MAXN = 5e4 + 5;
 9 typedef long long LL;
10 int a[MAXN] , u , cont[MAXN];
11 struct que {
12     int l , r , id;
13 }q[MAXN];
14 struct data {
15     LL x , y;
16 }ans[MAXN];
17 
18 LL gcd(LL x , LL y) {
19     if(!y)
20         return x;
21     return gcd(y , x % y);
22 }
23 
24 bool cmp(que x , que y) {
25     if(x.l / u == y.l / u) 
26         return x.r < y.r;
27     return x.l / u < y.l / u;
28 }
29 
30 inline LL f(LL x) {
31     return x * x;
32 }
33 
34 int main()
35 {
36     int n , m;
37     while(~scanf("%d %d" , &n , &m)) {
38         for(int i = 1 ; i <= n ; i++) {
39             scanf("%d" , a + i);
40         }
41         for(int i = 1 ; i <= m ; i++) {
42             scanf("%d %d" , &q[i].l , &q[i].r);
43             q[i].id = i;
44         }
45         u = sqrt(n);
46         sort(q + 1 , q + m + 1 , cmp);
47         int L = 1 , R = 0;
48         LL temp = 0;
49         memset(cont , 0 , sizeof(cont));
50         for(int i = 1 ; i <= m ; i++) {
51             while(L < q[i].l) {
52                 temp -= f(cont[a[L]]);
53                 cont[a[L]]--;
54                 temp += f(cont[a[L]]);
55                 L++;
56             }
57             while(L > q[i].l) {  //前面的還沒算
58                 L--;
59                 temp -= f(cont[a[L]]);
60                 cont[a[L]]++;
61                 temp += f(cont[a[L]]);
62             }
63             while(R > q[i].r) {
64                 temp -= f(cont[a[R]]);
65                 cont[a[R]]--;
66                 temp += f(cont[a[R]]);
67                 R--;
68             }
69             while(R < q[i].r) {
70                 R++;
71                 temp -= f(cont[a[R]]);
72                 cont[a[R]]++;
73                 temp += f(cont[a[R]]);
74             }
75             ans[q[i].id].x = temp - (R - L + 1);
76             ans[q[i].id].y = (LL)(R - L + 1) * (R - L);
77         }
78         for(int i = 1 ; i <= m ; i++) {
79             if(!ans[i].x || !ans[i].y) {
80                 printf("0/1\n");
81             }
82             else {
83                 temp = gcd(ans[i].x , ans[i].y);
84                 printf("%lld/%lld\n" , ans[i].x / temp , ans[i].y / temp);
85             }
86         }
87     }
88 }

轉載于:https://www.cnblogs.com/Recoder/p/5208648.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/257674.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/257674.shtml
英文地址，請注明出處：http://en.pswp.cn/news/257674.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！