初涉莫队

莫队？美队？暴力美学的经典诠释（两个都是

莫队是什么

呃……似乎没有找到「小Z的袜子命题报告」那一篇论文。

g1n0st：https://zhuanlan.zhihu.com/p/25017840

xsamsara：https://blog.csdn.net/qq_41357771/article/details/80470795

普通莫队

莫队用于处理一类区间问题：已知$[l,r]$就能够快速得到$[l+1,r]$,$[l,r-1]$此类区间的信息。

这种问题有一种最基础的暴力：

1     for (int i=1; i<=m; i++)
2     {
3         while (lt < q[i].l) del(lt++);
4         while (lt > q[i].l) add(--lt);
5         while (rt < q[i].r) add(++rt);
6         while (rt > q[i].r) del(rt--);
7         q[i].ans = ans;
8     }

类似于毛毛虫的思路扩张。

但是如果遇到$[1,n]$,$[mid,mid]$,$[1,n]$……的查询显然就被浪费了很多时间。

那么我们很自然地想到离线处理，把询问按照第一关键字l，第二关键字r的顺序排序。

然而光光这样是不够的，比如说$[1,100]$,$[1,200]$,$[2,3]$,$[2,100]$……的数据就可以卡爆单纯的排序。

同样是暴力的思想，同出一门的分块此时可以助莫队一臂之力。

我们可以这样：当l处在同一块时，按照r排序，否则按照l排序。

复杂度基本可以保证在$O(nsqrtn)$

带修改莫队

带修莫队其实就是莫队再加一维时间轴，换句话说就是把修改操作也按照莫队的思想处理。

把修改操作也按照莫队的思想处理！

嗯，这就是我学会带修莫队后对它的概括。

莫队例题

「普通莫队」1878: [SDOI2009]HH的项链

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一

段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一

个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只

好求助睿智的你，来解决这个问题。

Input

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

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

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

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

N ≤ 50000，M ≤ 200000。

Output

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

题目分析

正解是树状数组，不过可以作为莫队的板子题。

 1 #include<bits/stdc++.h>
 2 const int maxn = 50003;
 3 const int maxm = 200035;
 4 const int maxNum = 1000035;
 5 
 6 struct node
 7 {
 8     int l,r,x,ans,id;
 9 }q[maxm];
10 int a[maxn],hsh[maxNum],ans;
11 int n,m,size;
12 
13 bool cmp(node a, node b){return (a.l/size < b.l/size)||(a.l/size == b.l/size&&a.r < b.r);}
14 bool cmpid(node a, node b){return a.id < b.id;}
15 int read()
16 {
17     int num = 0;
18     char ch = getchar();
19     bool fl = 0;
20     for (; !isdigit(ch); ch = getchar())
21         if (ch=='-') fl = 1;
22     for (; isdigit(ch); ch = getchar())
23         num = (num<<1)+(num<<3)+ch-48;
24     if (fl) num = -num;
25     return num;
26 }
27 void add(int x){if (!(hsh[a[x]]++)) ans++;}
28 void del(int x){if (!(--hsh[a[x]])) ans--;}
29 int main()
30 {
31     n = read(), size = (int)sqrt(n);
32     for (int i=1; i<=n; i++) a[i] = read();
33     m = read();
34     for (int i=1; i<=m; i++)
35         q[i].l = read(), q[i].r = read(), q[i].id = i;
36     std::sort(q+1, q+m+1, cmp);
37     int lt = 1, rt = 0;
38     for (int i=1; i<=m; i++)
39     {
40         while (lt < q[i].l) del(lt++);
41         while (lt > q[i].l) add(--lt);
42         while (rt < q[i].r) add(++rt);
43         while (rt > q[i].r) del(rt--);
44         q[i].ans = ans;
45     }
46     std::sort(q+1, q+m+1, cmpid);
47     for (int i=1; i<=m; i++) printf("%d
",q[i].ans);
48     return 0;
49 }

「普通莫队」3339: Rmq Problem

Description

Input

Output

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

题目分析

普通莫队的板子题，不过有些细节注意一下。

 1 #include<bits/stdc++.h>
 2 const int maxn = 200035;
 3 
 4 int size,tot;
 5 struct QRs
 6 {
 7     int l,r,id;
 8     bool operator < (QRs a) const
 9     {
10         if (l/size==a.l/size)
11             return r/size < a.r/size;
12         else return l/size < a.l/size;
13     }
14     QRs() {}
15     QRs(int a, int b, int c):l(a),r(b),id(c) {}
16 }q[maxn];
17 int n,m,a[maxn],ans[maxn],hsh[maxn];
18 
19 int read()
20 {
21     int num = 0;
22     char ch = getchar();
23     bool fl = 0;
24     for (; !isdigit(ch); ch = getchar())
25         if (ch=='-') fl = 1;
26     for (; isdigit(ch); ch = getchar())
27         num = (num<<1)+(num<<3)+ch-48;
28     if (fl) num = -num;
29     return num;
30 }
31 void del(int x)
32 {
33     if (!(--hsh[x])) tot = std::min(tot, x);
34 }
35 void add(int x)
36 {
37     hsh[x]++;　　　　　　//由于这里add和del的顺序上的影响，中途修改过程中有可能hsh[]为负数
　　　　　　　　　　　　　　　//此时那么tot也要更新
38     if (x < tot){
39         if (hsh[x]==0) tot = x;
40     }else if (x==tot){
41         while (hsh[tot]) tot++;
42     }
43 }
44 int main()
45 {
46     n = read(), m = read();
47     size = (int)sqrt(n);
48     for (int i=1; i<=n; i++) a[i] = read();
49     for (int i=1; i<=m; i++)
50     {
51         int l = read(), r = read();
52         q[i] = QRs(l, r, i);
53     }
54     std::sort(q+1, q+m+1);　　　　//这些都是莫队套路了
55     int l = 1, r = 0;
56     for (int i=1; i<=m; i++)
57     {
58         while (l < q[i].l) del(a[l++]);
59         while (l > q[i].l) add(a[--l]);
60         while (r < q[i].r) add(a[++r]);
61         while (r > q[i].r) del(a[r--]);
62         ans[q[i].id] = tot;
63     }
64     for (int i=1; i<=m; i++) printf("%d
",ans[i]);
65     return 0;
66 }

「普通莫队」2038: [2009国家集训队]小Z的袜子(hose)

Description

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

Input

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

Output

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

Sample Input

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

Sample Output

2/5
0/1
1/1
4/15
【样例解释】
询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。
询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。
询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。
注：上述C(a, b)表示组合数，组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。
【数据规模和约定】
30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

题目分析

这个分析一下就可以发现需要维护区间的平方和，于是就是莫队的套路了。

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 const long long maxn = 50035;
 4 
 5 long long size;
 6 struct QRs
 7 {
 8     long long l,r,id;
 9     bool operator < (QRs a)const
10     {
11         return (l/size!=a.l/size)?l/size<a.l/size:r<a.r;
12     }
13 }q[maxn];
14 struct ANS
15 {
16     long long a,b;
17 }ans[maxn];
18 long long hsh[maxn],c[maxn];
19 long long n,m;
20 long long cnt;
21 
22 long long read()
23 {
24     long long num = 0;
25     char ch = getchar();
26     bool fl = 0;
27     for (; !isdigit(ch); ch = getchar())
28         if (ch=='-') fl = 1;
29     for (; isdigit(ch); ch = getchar())
30         num = (num<<1)+(num<<3)+ch-48;
31     if (fl) num = -num;
32     return num;
33 }
34 long long gcd(long long a, long long b){return (a%b==0)?b:gcd(b, a%b);}
35 void update(long long col, long long c)
36 {
37     cnt -= hsh[col]*hsh[col];
38     hsh[col] += c;
39     cnt += hsh[col]*hsh[col];
40 }
41 int main()
42 {
43     // freopen("bz2038.in",);
44     n = read(), m = read();
45     size = sqrt(n);
46     for (int i=1; i<=n; i++) c[i] = read();
47     for (int i=1; i<=m; i++) q[i].l = read(), q[i].r = read(), q[i].id = i;
48     std::sort(q+1, q+m+1);
49     long long L = 1, R = 0;
50     for (int i=1; i<=m; i++)
51     {
52         while (L < q[i].l) update(c[L++], -1);
53         while (L > q[i].l) update(c[--L], 1);
54         while (R < q[i].r) update(c[++R], 1);
55         while (R > q[i].r) update(c[R--], -1);
56         if (cnt-(R-L+1)==0){
57             ans[q[i].id].a = 0;
58             ans[q[i].id].b = 1;
59         }else{
60             ans[q[i].id].a = cnt-(R-L+1);
61             ans[q[i].id].b = 1ll*(R-L+1)*(R-L);
62             long long k = gcd(ans[q[i].id].a, ans[q[i].id].b);
63             ans[q[i].id].a /= k, ans[q[i].id].b /= k;
64         }
65     }
66     for (long long i=1; i<=m; i++)
67         printf("%lld/%lld
",ans[i].a,ans[i].b);
68     return 0;
69 }

「带修莫队」2120: 数颜色

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

Output

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

HINT

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

题目分析

就是上面的分析，

直接挂代码吧

 1 #include<bits/stdc++.h>
 2 const int maxn = 50035;
 3 const int maxNum = 1000035;
 4 
 5 int size;
 6 struct CHANGEs
 7 {
 8     int x,y,lst;
 9     CHANGEs() {}
10     CHANGEs(int a, int b, int c):x(a),y(b),lst(c) {}
11 }u[maxn];
12 struct QRs
13 {
14     int l,r,tim,id;
15     bool operator < (QRs a) const
16     {
17         if (l/size==a.l/size){
18             if (r/size==a.r/size){
19                 return tim < a.tim;
20             }else return r/size < a.r/size;
21         }else return l/size < a.l/size;
22     }
23     QRs() {}
24     QRs(int a, int b, int c, int d):l(a),r(b),tim(c),id(d) {}
25 }q[maxn];
26 int n,m,cntu,cntq,L,R,now,tot;
27 int a[maxn],lst[maxn],ans[maxn],hsh[maxNum];
28 char ch[13];
29 
30 int read()
31 {
32     int num = 0;
33     char ch = getchar();
34     bool fl = 0;
35     for (; !isdigit(ch); ch = getchar())
36         if (ch=='-') fl = 1;
37     for (; isdigit(ch); ch = getchar())
38         num = (num<<1)+(num<<3)+ch-48;
39     if (fl) num = -num;
40     return num;
41 }
42 void change(int x, int col)
43 {
44     if (x >= L&&x <= R){
45         if (!(--hsh[a[x]])) tot--;
46         a[x] = col;
47         if (!(hsh[a[x]]++)) tot++;
48     }else a[x] = col;
49 }
50 void add(int x){if (!(hsh[x]++)) tot++;}
51 void del(int x){if (!(--hsh[x])) tot--;}
52 int main()
53 {
54     n = read(), m = read();
55     size = pow(n, 2.0/3);
56     for (int i=1; i<=n; i++) lst[i] = a[i] = read();
57     for (int i=1; i<=m; i++)
58     {
59         scanf("%s",ch);
60         int l = read(), r = read();
61         if (ch[0]=='Q')
62             q[++cntq] = QRs(l, r, cntu, cntq);
63         else{
64             u[++cntu] = CHANGEs(l, r, lst[l]);
65             lst[l] = r;
66         }
67     }
68     std::sort(q+1, q+cntq+1);
69     L = 1, R = 0, now = 0;
70     for (int i=1; i<=cntq; i++)
71     {
72         while (q[i].tim < now) change(u[now].x, u[now].lst),now--;
73         while (q[i].tim > now) now++,change(u[now].x, u[now].y);
74         while (L < q[i].l) del(a[L++]);
75         while (L > q[i].l) add(a[--L]);
76         while (R < q[i].r) add(a[++R]);
77         while (R > q[i].r) del(a[R--]);
78         ans[q[i].id] = tot;
79     }
80     for (int i=1; i<=cntq; i++) printf("%d
",ans[i]);
81     return 0;
82 }

END