清橙A1206.小Z的袜子 && CF 86D（莫队两题）

在网上看了一些别人写的关于莫队算法的介绍，我认为，莫队与其说是一种算法，不如说是一种思想，他通过先分块再排序来优化离线查询问题。

应用范围：一般问题是让你回答多个连续区间上的问题，如果你知道了区间【l，r】的答案、你就可以在O（1）或O（logn）时间内知道【l+1，r】、【l，r+1】、【l-1,r】、【l，r-1】区间的答案，那么你就可以应用莫队算法。

实现方法：数组长度为n，查询个数为m。先读入所有查询，然后把查询【l，r】按l/sqrt（m）递增的的顺序排序，如果相同再按r递增的顺序排序，然后维护当前区间的查询值，再按排好的序从前到后暴力跑一遍就OK了。

原理阐述：到这里很多人可能要问一个问题，为什么要分sqrt（m）块？这个问题也困扰了我好久，不过经过一番冥想，我终于找到了答案：假设我们要把查询分成x块，那么每块中 r 的移动量最大为n、总的移动量为n*x，每块中 l 的移动量最大为n/t、总的移动量为m*n/x，整个查询的复杂度为（n*x+n*m/x），根据数学知识我们可以知道，在n*x=n*m/x的时候总的复杂度是最小的，这时x=sqrt（m），复杂度为O（2*n*sqrt（m）），这样莫队按sqrt（m）分块的合理性就得到了证明。

入门题1：青橙A1206.小Z的袜子

http://www.tsinsen.com/A1206

长度为n的数组，有m个询问，每个询问你需要回答：在该区间内任意抽两个数字且两个数字的数值相同的概率是多大，答案需要时最简分数的形式。

思路：对于区间【l，r】，其不同数值的数的个数分别为a、b、.....、c，那么上述的概率就是（a^a+b^b+...+c^c-(r-l+1)）/(r-l)*(r-l+1)。（不要问我是咋推出来的）。

解法：维护当前区间【l，r】中数值为v的数的个数cnt【v】，如果该区间答案为temp，那么对于区间【l，r+1】，你可以在O（1）时间内求出新的temp，那么久可以运用莫队来搞定了。

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <stack>
11 #include <queue>
12 using namespace std;
13 
14 const int maxn=50005;
15 typedef long long LL;
16 int n,m;
17 
18 LL gcd(LL a,LL b){
19     if(b==0)  return a;
20     return gcd(b,a%b);
21 }
22 
23 struct ANS{
24     LL a,b;
25     void simple(){
26         LL kk=gcd(a,b);
27         a/=kk;
28         b/=kk;
29     }
30 }ans[maxn];
31 
32 struct node{
33     int l,r,id;
34 }q[maxn];
35 
36 int cmp(const node& a,const node& b){
37     if(a.l/(int)sqrt(m)!=b.l/(int)sqrt(m)) return a.l/(int)sqrt(m)<b.l/(int)sqrt(m);
38     return a.r<b.r;
39 }
40 
41 int c[maxn];
42 int cnt[maxn];
43 
44 void solve(){
45     cnt[c[1]]++;
46     LL temp=1;
47     int l=1;
48     int r=1;
49     for(int i=1;i<=m;i++){
50         //cout<<l<<"  "<<r<<endl;
51         while(l<q[i].l){
52             temp=temp-cnt[c[l]]*cnt[c[l]];
53             cnt[c[l]]--;
54             temp=temp+cnt[c[l]]*cnt[c[l]];
55             l++;
56         }
57         while(l>q[i].l){
58             l--;
59             temp=temp-cnt[c[l]]*cnt[c[l]];
60             cnt[c[l]]++;
61             temp=temp+cnt[c[l]]*cnt[c[l]];
62         }
63         while(r<q[i].r){
64             r++;
65             temp=temp-cnt[c[r]]*cnt[c[r]];
66             cnt[c[r]]++;
67             temp=temp+cnt[c[r]]*cnt[c[r]];
68         }
69         while(r>q[i].r){
70             temp=temp-cnt[c[r]]*cnt[c[r]];
71             cnt[c[r]]--;
72             temp=temp+cnt[c[r]]*cnt[c[r]];
73             r--;
74         }
75         //cout<<q[i].id<<endl;
76         ans[q[i].id].a=temp-(r-l+1);
77         ans[q[i].id].b=(LL)(r-l+1)*(r-l);
78         ans[q[i].id].simple();
79     }
80 }
81 
82 int main (){
83     while(scanf("%d%d",&n,&m)!=EOF){
84         for(int i=1;i<=n;i++){
85             scanf("%d",&c[i]);
86         }
87         for(int i=1;i<=m;i++){
88             scanf("%d%d",&q[i].l,&q[i].r);
89             q[i].id=i;
90         }
91         sort(q+1,q+m+1,cmp);
92         memset(cnt,0,sizeof(cnt));
93         solve();
94         for(int i=1;i<=m;i++)
95             cout<<ans[i].a<<"/"<<ans[i].b<<endl;
96     }
97     return 0;
98 }

入门题2： CF 86D Powerful array

http://codeforces.com/problemset/problem/86/D

题意：给你一个长度为n的数组，m个询问，每个询问需要你回答对于给出的区间【l，r】，sigma（cnt[v]*cnt[v]*v），其中v是【l，r】内的数字，cnt[v]是【l，r】内v的个数。

解法：区间的范围每移动一次，就可以在O(1)时间内完成更新，故可以使用莫队算法（具体实现详见代码）

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <stack>
11 #include <queue>
12 using namespace std;
13 
14 typedef long long LL;
15 const int maxn=200005;
16 const int maxa=1e6;
17 
18 int n,t;
19 
20 struct node{
21     int l,r,id;
22 }q[maxn];
23 
24 int cmp(const node& a,const node& b){
25     if(a.l/(int)sqrt(t)!=b.l/(int)sqrt(t))  return a.l/(int)sqrt(t)<b.l/(int)sqrt(t);
26     return a.r<b.r;
27 }
28 
29 int cnt[maxa+5];
30 int a[maxn];
31 LL ans[maxn];
32 
33 LL temp;
34 void update(int cur,int change){
35     temp-=(LL)cnt[a[cur]]*cnt[a[cur]]*a[cur];
36     cnt[a[cur]]+=change;
37     temp+=(LL)cnt[a[cur]]*cnt[a[cur]]*a[cur];
38 }
39 
40 void solve(){
41     temp=a[1];
42     cnt[a[1]]++;
43     int l=1;
44     int r=1;
45     for(int i=1;i<=t;i++){
46         while(l<q[i].l){
47             update(l,-1);
48             l++;
49         }
50         while(l>q[i].l){
51             l--;
52             update(l,1);
53         }
54         while(r>q[i].r){
55             update(r,-1);
56             r--;
57         }
58         while(r<q[i].r){
59             r++;
60             update(r,1);
61         }
62         ans[q[i].id]=temp;
63     }
64 }
65 
66 int main (){
67     while(scanf("%d%d",&n,&t)!=EOF){
68         for(int i=1;i<=n;i++)
69             scanf("%d",&a[i]);
70         for(int i=1;i<=t;i++){
71             scanf("%d%d",&q[i].l,&q[i].r);
72             q[i].id=i;
73         }
74         sort(q+1,q+t+1,cmp);
75         memset(cnt,0,sizeof(cnt));
76         solve();
77         for(int i=1;i<=t;i++)
78             cout<<ans[i]<<endl;
79     }
80     return 0;
81 }