【莫队】HH的项链 && 小Z的袜子

昨天早上别人莫队都65+，只有我20分。【好歹水了20分

话说当时莫队还是我讲的来着。QAQ

于是我就来颓博客了【其实是改不出来题了

背景

　　莫队！优美的暴力！

　　据说这是2010年国家集训队的莫涛在作业里提到了这个方法。

　　由于莫涛经常打比赛做队长，大家都叫他莫队，该算法也被称为莫队算法。

前置知识

　　1.简单分块。

　　2.熟练离散化

　　3.倍增 / 树剖求LCA

　　4.STL中有关sort的部分

例题1. P1972 [SDOI2009]HH的项链

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

第一行：一个整数N，表示项链的长度。

第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。

第三行：一个整数M，表示HH 询问的个数。

接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出格式

M 行，每行一个整数，依次表示询问对应的答案。

输入输出样例

输入 #1

6
1 2 3 4 3 5
3
1 2
3 5
2 6

输出 #1

2
2
4

说明/提示

数据范围：

对于100%的数据，N <= 500000，M <= 500000。

思路分析

　　一眼线段树。【线段树可做，主席树也可做QAQ但是我不会

增加出现次数时判断一下 $c n t_{n u m}$

$c n t_{n u m}$

$那么究竟问题出现在了哪里？$

$仔细想想，当一个询问出现在序列的很前段，下一个在最后段，再下一个又在最前端/..........................$

$冗余的地方显而易见了。$

$这个时候就大概可以想到了，将询问排序，尽量减少指针移动的损失。$

$基本上接近了莫队的精髓。$

$莫队的本质$

$莫队算法的核心是分块和排序。$

$将大小为 n$

inline bool cmp(Node x,Node y) {
    return pos[x.l]==pos[y.l]?x.r<y.r:x.l<y.l;
}

　　听说还有个玄学优化：奇偶性排序

　　这个和莫队的主算法有异曲同工之妙……看起来卵用都没有，实际上可以帮你每个点平均优化200ms（可怕）

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　------WAMonster

　　顺便再引用一下DALAO的代码。

int cmp(query a, query b) {
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

也就是说，对于左端点在同一奇数块的区间，右端点按升序排列，反之降序。这个东西也是看着没用，但实际效果显著。

它的主要原理便是右指针跳完奇数块往回跳时在同一个方向能顺路把偶数块跳完，然后跳完这个偶数块又能顺带把下一个奇数块跳完。

理论上主算法运行时间减半，实际情况有所偏差。（不过能优化的很爽就对了）

时间复杂度

　　排序 O（n logn）+ 左指针 O（n √n）+ 右指针 O（n √n）

　　总复杂度 O（n √n）

　　强死啦

提供一个分块思路：

　　　　定义 a[ i ] 表示 i 这个位置的贝壳种类。

　　　　pre[ i ] 表示从 i 往前，第一个种类为 a[ i ] 的位置。

　　我们要求一段区间

$因为区间内$

$复杂度OK。$

代码放送（莫队）

 1 // luogu-judger-enable-o2
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 const int MA=500005;
10 int n,m,s,tot;
11 int a[MA],c[MA*2],ans[MA*2];
12 struct Node{
13     int l,r,id;
14     bool operator < (const Node x) const {
15         return l/s==x.l/s?(((l/s)&1)?r<x.r:r>x.r):l<x.l;
16     }
17 }q[MA];
18 
19 inline int read() {
20     char ch=getchar();int num=0;
21     while(ch<'0'||ch>'9') ch=getchar();
22     while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+ch-'0';ch=getchar();}
23     return num;
24 }
25 
26 void add(int x) {
27     tot+=(++c[a[x]]==1);
28     return;
29 }
30 
31 void dec(int x) {
32     tot-=(--c[a[x]]==0);
33     return;
34 }
35 
36 int main()
37 {
38     n=read();
39     s=sqrt(n);
40     for(int i=1;i<=n;++i)
41         a[i]=read();
42     m=read();
43     for(int i=1;i<=m;++i){
44        q[i].l=read();
45        q[i].r=read();
46        q[i].id=i;
47     }
48     sort(q+1,q+m+1);
49     int L=1,R=0;
50     for(int i=1;i<=m;++i){
51         while(q[i].l>L)
52             dec(L++);
53         while(q[i].l<L)    
54             add(--L);
55         while(q[i].r<R)
56             dec(R--);
57         while(q[i].r>R)
58             add(++R);
59         ans[q[i].id]=tot;
60     }
61     for(int i=1;i<=m;++i)
62        printf("%d
",ans[i]);
63     return 0;
64 }

HH的项链

例题2 .P1494 [国家集训队]小Z的袜子

题目描述

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

然而数据中有L=R的情况，请特判这种情况，输出0/1。

输入格式

输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。

输出格式

包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）

输入输出样例

输入 #1

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

输出 #1

2/5
0/1
1/1
4/15

说明/提示

30%的数据中 N,M ≤ 5000；

60%的数据中 N,M ≤ 25000；

100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

思路分析

代码放送

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define MA 51000
 7 using namespace std;
 8 
 9 inline long long read(){
10     register long long x=0,t=1;
11     register char ch=getchar();
12     while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
13     if(ch=='-'){t=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
15     return x*t;
16 }
17 
18 long long n,m,c[MA];
19 long long color[MA];
20 long long ac;
21 struct ss{
22     long long l,r,id;
23     long long t;
24 }q[MA];
25 
26 struct node{
27     long long a,b;
28 }ans[MA];
29 
30 inline bool cmp(ss a,ss b) {
31     if(a.t==b.t)
32         return a.r<b.r;
33     else
34         return a.t<b.t;
35 }
36 
37 inline void count(long long x,long long k) {
38     ac-=color[c[x]]*color[c[x]];
39     color[c[x]]+=k;
40     ac+=color[c[x]]*color[c[x]];
41 }
42 
43 int main()
44 {
45     n=read();
46     m=read();
47     long long Len=sqrt(n);
48     for(int i=1;i<=n;i++)
49         c[i]=read();
50     for(int i=1;i<=m;i++) {
51         q[i].l=read();
52         q[i].r=read();
53         q[i].id=i;
54         q[i].t=(q[i].l-1)/Len+1;
55     }
56     sort(q+1,q+m+1,cmp);
57     long long l=1,r=0;
58     for(int i=1;i<=m;i++) {
59         while(l>q[i].l) {
60             count(l-1,1);
61             l--;
62         }
63         while(l<q[i].l) {
64             count(l,-1);
65             l++;
66         }
67         while(r>q[i].r) {
68             count(r,-1);
69             r--;
70         }
71         while(r<q[i].r) {
72             count(r+1,1);
73             r++;
74         }
75         if(q[i].l==q[i].r) {
76             ans[q[i].id]=(node){0,1};
77             continue;
78         }
79         ans[q[i].id]=(node){ac-(r-l+1),1LL*(r-l+1)*(r-l)};
80     }
81     for(int i=1;i<=m;i++) {
82         long long d=__gcd(ans[i].a,ans[i].b);
83         if(d>1)
84             printf("%lld/%lld
",ans[i].a/d,ans[i].b/d);
85         else
86             printf("%lld/%lld
",ans[i].a,ans[i].b);
87     }
88     return 0;
89 }

小Z的袜子

习题总结

谢谢，大家莫队愉快！！！！！！！！