莫队算法(模板+带修莫队)

莫队算法

  这个算法的思想比较简单,我们在做RMQ类问题时,有多次询问的那种,其实在这些询问中有很多都是问的同一段区间,即有的区间被询问的多次,所以我们对询问进行一个排序,假设上次询问我们得到了区间[l,r]的值,那本次询问跟上次相比,多的我们加上即可,少的减掉即可。然后用到分块思想。

  所以,比较重要的就是这个排序和每次询问与上次之间的转化。
  排序:这里用到分块,根据区间左界所在的块的序号从小到大排,若在同一区间,则根据序号的奇偶性,奇则根据右边界从小到大,偶则根据右边界从大到小
  与上次的转化:通过四个while来实现。

1
2
3
4
while(l < ask[i].l) del(c[l++]);
while(l > ask[i].l) add(c[--l]);
while(r < ask[i].r) add(c[++r]);
while(r > ask[i].r) del(c[r--]);

P1494 小z的袜子(模板题)

分析:
弄明白那个排列组合和概率就基本模板题惹

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, m, len;
int ar[50050];
struct node
{
ll l, r, id;
}ask[50050];
struct node1
{
ll x, y;
}ans[50050], now;
int pos[50050];
ll cnt[50050];

bool cmp(node a, node b)
{
if(pos[a.l] == pos[b.l])
{
if(pos[a.l] & 1) return a.r < b.r;
else return a.r > b.r;
}
else return pos[a.l] < pos[b.l];
}

ll gcd(ll x, ll y)
{
return !y ? x : gcd(y, x % y);
}

void add(int x)
{
++cnt[x];
if(cnt[x] > 1)
now.x = now.x + cnt[x] * (cnt[x] - 1) - (cnt[x] - 1) * (cnt[x] - 2);
}

void del(int x)
{
--cnt[x];
if(cnt[x] > 0)
now.x = now.x + cnt[x] * (cnt[x] - 1) - (cnt[x] + 1) * cnt[x];
}

void divgcd(ll x, ll y, int id)
{
if(!x) x = 0, y = 1;
else
{
ll g = gcd(x, y);
x /= g;
y /= g;
}
ans[id].x = x;
ans[id].y = y;
}

int main()
{
scanf("%d%d", &n, &m);
len = sqrt(n + 0.5);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &ar[i]);
pos[i] = (i - 1) / len + 1;
}
for(int i = 1; i <= m; ++i)
{
scanf("%lld%lld", &ask[i].l, &ask[i].r);
ask[i].id = i;
}
sort(ask + 1, ask + m + 1, cmp);
for(int i = ask[1].l; i <= ask[1].r; ++i) add(ar[i]);
now.y = (ask[1].r - ask[1].l + 1) * (ask[1].r - ask[1].l);
divgcd(now.x, now.y, ask[1].id);
int l = ask[1].l, r = ask[1].r;
for(int i = 2; i <= m; ++i)
{
while(l < ask[i].l) del(ar[l++]);
while(l > ask[i].l) add(ar[--l]);
while(r > ask[i].r) del(ar[r--]);
while(r < ask[i].r) add(ar[++r]);
now.y = (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l);
divgcd(now.x, now.y, ask[i].id);
}

for(int i = 1; i <= m; ++i) printf("%lld/%lld\n", ans[i].x, ans[i].y);
return 0;
}

P1903 数颜色(带简单修改的莫队)

题目描述

墨墨购买了一套 $N$ 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:

  1. $Q\ L\ R$ 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。

  2. $R\ P\ C$ 把第 $P$ 支画笔替换为颜色 $C$。

为了满足墨墨的要求,你知道你需要干什么了吗?

输入格式

第 $1$ 行两个整数 $N$,$M$,分别代表初始画笔的数量以及墨墨会做的事情的个数。

第 $2$ 行 $N$ 个整数,分别代表初始画笔排中第 $i$ 支画笔的颜色。

第 $3$ 行到第 $2+M$ 行,每行分别代表墨墨会做的一件事情,格式见题干部分。

输出格式

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

样例输入 #1

1
2
3
4
5
6
7
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

样例输出 #1

1
2
3
4
4
4
3
4

提示

对于30%的数据,$n,m \leq 10000$

对于60%的数据,$n,m \leq 50000$

对于所有数据,$n,m \leq 133333$

所有的输入数据中出现的所有整数均大于等于 $1$ 且不超过 $10^6$。

本题可能轻微卡常数。

分析:
  首先考虑普通的莫队,这个题带了修改,那么我们依旧按照莫队来做,我们需要记录一下当前这次询问经过了几次修改,然后跟上一次比较,那就跟普通莫队一样了,只是4个while要变成6个while了。这是大体方向,然后还有一点点细节。
  1.分块大小:sz = pow(n, 0.666);
  2.排序:第一关键字是区间左界所在的块的序号,第二关键字是区间右界所在的块的序号,第三关键字是这次询问经过了几次修改,均按照从小到大排。
  3.对于修改,如果碰到某次修改需要操作,那么一定需要做一个交换swap(ar[qr[t].l], qr[t].r);,交换完之后,ar数组得到了修改,然后这次修改指令也得到了修改,因为后面再操作这次修改的时候就是改回来了,所以一个交换解决。另外,需要判断这次修改是不是发生在查询的区间内,是则需要做一些add和del。
  4.维护的容器,以及作用
  cnt[i] : 数字i在当前区间出现的次数
   ar[i]; 原数组在位置i应该是的值
  qq[i] 表示第i次询问的左右边界已经发生在几次修改之后,id代表修改序号
  qr[i] 表示第i次修改是将l位置的数字改成r

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>

using namespace std;

int sum;
int cnt[1000050];
int ar[10050];
int ans[10050];
int cntq, cntr;
int n, m, sz;
char op[5];
int l, r;

struct node
{
int l, r, t, id;
}qq[10050], qr[10050];//两个数组分解记录每一个询问以及修改的状态

inline bool cmp(const node &a, const node &b)
{
if(a.l / sz == b.l / sz)
{
if(a.r / sz == b.r / sz) return a.t < b.t;
else return a.r < b.r;
}
else return a.l < b.l;
}

inline void add(int x)
{
sum += !cnt[x]++;
}

inline void del(int x)
{
sum -= !--cnt[x];
}

inline void upd(int x, int t)//upd是对于时间上的变化所造成变化的维护
{
if(qq[x].l <= qr[t].l && qr[t].l <= qq[x].r)
{
del(ar[qr[t].l]);
add(qr[t].r);
}
swap(ar[qr[t].l], qr[t].r);
}

int main()
{
scanf("%d%d", &n, &m);
sz = pow(n, 0.666);
for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
for(int i = 1; i <= m; ++i)
{
scanf("%s%d%d", op, &l, &r);
if(op[0] == 'Q')
{
++cntq;
qq[cntq].id = cntq;
qq[cntq].l = l;
qq[cntq].r = r;
qq[cntq].t = cntr;
}
else
{
++cntr;
qr[cntr].l = l;
qr[cntr].r = r;
}
}
sort(qq + 1, qq + cntq + 1, cmp);
int lcur = 1, rcur = 0, tcur = 0;
for(int i = 1; i <= cntq; ++i)
{
while(lcur > qq[i].l) add(ar[--lcur]);
while(lcur < qq[i].l) del(ar[lcur++]);
while(rcur > qq[i].r) del(ar[rcur--]);
while(rcur < qq[i].r) add(ar[++rcur]);
while(tcur < qq[i].t) upd(i, ++tcur);
while(tcur > qq[i].t) upd(i, tcur--);//增加t轴上的移动
ans[qq[i].id] = sum;
}
for(int i = 1; i <= cntq; ++i) printf("%d\n", ans[i]);
return 0;
}