首页 > 其他分享 >分块莫队

分块莫队

时间：2024-08-28 14:56:27浏览次数：14  
标签：cnt 分块 -- belong int now 莫队

莫队

序言

其实我不是很赞成把分块和莫队放到一起的（可能是我太菜了），原本这周先学的树上合并，树分治扫描线那些的，但是没怎么懂，先写一个记忆最新的吧。

简介

莫队算法是由莫涛提出的算法，莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

其实就是暴力，不过是更加优美的暴力。

咳咳，不过其实莫队的实现因为很容易，相较于市面上的那些码量动不动上百行的算法，可以说是很仁慈了，而且很容易入手（当然个例分支除外）。

普通莫队

现在我们考虑这么一个问题：

给定一个序列，我们每次询问一个区间，询问这个区间里的不同元素的个数。

现在肯定又有人要跳出来说用线段树了，那你请出门左转 luogu 去看看 noip 出的（毒瘤）题单，这时候你会发现 线段树就是弱智才去写的。

莫队的思想就是我们定义两个指针 \(l\)，\(r\) 表示莫队的区间，然后我们将所有询问区间离线下来离散化，按照左端点排序，然后每次优先把 \(l\)，向最近的询问区间移动，然后移动 \(r\) 就行。

给个示意图吧：

img

我们初始化 \(l=1,r=0\)，下面开始移动两个指针。

img

我们发现 \(l\) 已经是查询区间的左端点了，现在开始移动 \(r\) 到 \(Q_1\) 的右端点，右移一位，发现新数值 1，总数 +1 。

img

接着移动，遇到 2 答案 +1。

img

直到遇到第二个 2，总数不变（这个可以用个 map 啥的记录一下出现过的）。

img

接下来两个 7 同理，总数+1。

img

继续

img

最后两个都访问过了，总数不加。

img

至此，我们处理完了第一个询问的区间答案，答案为 5。

下面处理 \(Q_2\) 的问题，需要先把 \(l\) 移动到其左区间，剩下的操作和之前一样。

注意 \(l\) 右移时，需要判断一下当前元素删掉会不会使得总数减少，这个同理也是用 map 记录下来过的。

粘个我认为写的很好的代码吧：

int aa[maxn], cnt[maxn], l = 1, r = 0, now = 0; //每个位置的数值、每个数值的计数器、左指针、右指针、当前统计结果（总数）
void add(int pos) {//添加一个数
    if(!cnt[aa[pos]]) ++now;//在区间中新出现，总数要+1
    ++cnt[aa[pos]];
}
void del(int pos) {//删除一个数
    --cnt[aa[pos]];
    if(!cnt[aa[pos]]) --now;//在区间中不再出现，总数要-1
}
void work() {//优化2主过程
    for(int i = 1; i <= q; ++i) {//对于每次询问
        int ql, qr;
        scanf("%d%d", &ql, &qr);//输入询问的区间
        while(l < ql) del(l++);//如左指针在查询区间左方，左指针向右移直到与查询区间左端点重合
        while(l > ql) add(--l);//如左指针在查询区间左端点右方，左指针左移
        while(r < qr) add(++r);//右指针在查询区间右端点左方，右指针右移
        while(r > qr) del(r--);//否则左移
        printf("%d\n", now);//输出统计结果
    }
}

但其实这个代码的思路其实是不完整的，我们考虑这样的一个情况：

img

这样的话，\(l\) 和 \(r\) 就会左跳一下右跳一下，直接寄。

接下来就是优化了。

优化1

分块大法好！我们把序列分成 \(\sqrt{n}\) 个块，然后将询问区间排序，按左端点从小到大排序，如果左端点在同一个块内，则按照右端点从小到大排序。这样复杂度就降到了 \(O(n\sqrt{n})\)。

下面乱胡一个证明（网上看的）:

  1. 排序复杂度 \(O(n\log n)\)。
  2. 左指针位移，假设最坏情况下每个询问都不在同一个块中，那么一次移动均摊最多是 \(O(\sqrt n)\) 的，所以总时间复杂度是 \(O(n\sqrt n)\)。
  3. 右指针位移，同理，最坏情况下每次移动会扫完整个序列，即 \(O(n)\)，但是总共只有 \(\sqrt n\) 个块，意味着最多只会有 \(\sqrt n\) 个不在一个块的左端点，所以右指针移动的次数最多是 \(O(\sqrt n)\)，所以总时间复杂度是 \(O(n\sqrt n)\)。

综述，莫队的复杂度为 \(O(n\log n)+O(n\sqrt n)+O(n\sqrt n)=O(n\sqrt n)\)。

参考的排序 cmp 函数

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

优化玄学卡常

1. #pragma GCC optimize(2) and #pragma GCC optimize(3)

不好多说了，反正吸个氧的莫队速度飞快，\(1e6\) 毫无压力。

2. 奇偶性排序

网上学的，看起来没什么鸟用，其实会让代码平均每个点快 \(200ms\) 左右。

思路就是对于左端点在同一奇数块的区间，右端点按升序排列，反之降序。

主要原理便是右指针跳完奇数块往回跳时在同一个方向能顺路把偶数块跳完，然后跳完这个偶数块又能顺带把下一个奇数块跳完。理论上主算法运行时间减半，实际情况有所偏差。（不过能优化得很爽就对了）

代码：

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);
}

3.函数拆分

就是把 \(add\) 和 \(del\) 硬生生拆开，速度更快（我不李姐）。

while(l < ql) now -= !--cnt[aa[l++]];
while(l > ql) now += !cnt[aa[--l]]++;
while(r < qr) now += !cnt[aa[++r]]++;
while(r > qr) now -= !--cnt[aa[r--]];

现在代码也就不难写了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

#define maxn 1010000
#define maxb 1010
int aa[maxn], cnt[maxn], belong[maxn];
int n, m, size, bnum, now, ans[maxn];
struct query {
	int l, r, id;
} q[maxn];

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);
}
#define isdigit(x) ((x) >= '0' && (x) <= '9')
int read() {
	int res = 0;
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
	return res;
}
void printi(int x) {
	if(x / 10) printi(x / 10);
	putchar(x % 10 + '0');
}

int main() {
	scanf("%d", &n);
	size = sqrt(n);
	bnum = ceil((double)n / size);
	for(int i = 1; i <= bnum; ++i) 
		for(int j = (i - 1) * size + 1; j <= i * size; ++j) {
			belong[j] = i;
		}
	for(int i = 1; i <= n; ++i) aa[i] = read(); 
	m = read();
	for(int i = 1; i <= m; ++i) {
		q[i].l = read(), q[i].r = read();
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	for(int i = 1; i <= m; ++i) {
		int ql = q[i].l, qr = q[i].r;
		while(l < ql) now -= !--cnt[aa[l++]];
		while(l > ql) now += !cnt[aa[--l]]++;
		while(r < qr) now += !cnt[aa[++r]]++;
		while(r > qr) now -= !--cnt[aa[r--]];
		ans[q[i].id] = now;
	}
	for(int i = 1; i <= m; ++i) printi(ans[i]), putchar('\n');
	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

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

样例输出 #1

4
4
3
4

修改操作也分两种，一种是离线可做，一种是强制在线，如果是强制在线基本上莫队就萎了，可离线的话还可以做，这道题就是属于离线可做的类型。做法就是对每个询问区间再加上一维时间维度 \(t\)。

做法是把修改操作编号，称为"时间戳"，而查询操作的时间戳沿用之前最近的修改操作的时间戳。跑主算法时定义当前时间戳为 \(t\) ，对于每个查询操作，如果当前时间戳相对太大了，说明已进行的修改操作比要求的多，就把之前改的改回来，反之往后改。只有当当前区间和查询区间左右端点、时间戳均重合时，才认定区间完全重合，此时的答案才是本次查询的最终答案。

通俗地讲，就是再弄一指针，在修改操作上跳来跳去，如果当前修改多了就改回来，改少了就改过去，直到次数恰当为止。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int T=1;

const int N=250000;
const int M=1111111;

int n,m;
int cnt[M],a[N],ans[N],sum,cntq=0,cntr=0,siz;
struct dat{
    int l,r,t,id;
}qq[N];
struct change{
    int pos,val;
}qr[N];

inline bool cmp(dat a,dat b){
	return a.l/siz==b.l/siz?a.r/siz==b.r/siz?a.t<b.t:a.r<b.r:a.l<b.l;
}

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

inline void update(int x,int t){
    if(qq[x].l<=qr[t].pos && qr[t].pos<=qq[x].r){
        del(a[qr[t].pos]);
        add(qr[t].val);
    }
    swap(a[qr[t].pos],qr[t].val);
}

signed main(){
	read(n),read(m);
	siz=pow(n,0.666);
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1;i<=m;++i){
		char opt;
		int l,r;
		cin>>opt;
		read(l),read(r);
		if(opt=='Q') qq[++cntq].l=l,qq[cntq].r=r,qq[cntq].t=cntr,qq[cntq].id=cntq;
		else qr[++cntr].pos=l,qr[cntr].val=r;
	}
	sort(qq+1,qq+cntq+1,cmp);
	int l=1,r=0,t=0;
	for(int i=1;i<=cntq;++i){
		while(l<qq[i].l) del(a[l++]);
		while(l>qq[i].l) add(a[--l]);
		while(r>qq[i].r) del(a[r--]);
		while(r<qq[i].r) add(a[++r]);
		while(t<qq[i].t) update(i,++t);
		while(t>qq[i].t) update(i,t--);
		ans[qq[i].id]=sum;
	}
	for(int i=1;i<=cntq;++i) printf("%d\n",ans[i]);
    return 0;
}

剩下的莫队不会，以后再学吧。

标签：cnt,分块,--,belong,int,now,莫队
From： https://www.cnblogs.com/lizihan00787/p/18377952

相关文章

  • 莫队算法
    特点：快速、离线处理（支持查询，不支持修改）、暴力处理长序列问题核心思想：双指针的移动分块和排序示例题洛谷P1972[SDOI2009]HH的项链ps:实际这道题用莫队会被卡，仅用于举例#include<bits/stdc++.h>usingnamespacestd;structq{intl;intr;intid;}ql......
  • 分块学习记录
    Referencelink1hzwer分块9题老年退役选手学点东西之前学过分块但是已经忘得差不多了今天稍微补一补吧。用一道区间最值典题来讲一下。\(1e5\)数列\([l,r]\)最大值。假设数组叫做a长度为\(n\)从一开始标号，那么就可以把这个数组分块每一块的长度是\(\sqrt{n}\)......
  • 解读GaussDB(for MySQL)表级恢复，看线程数及分块分行策略如何提升恢复性能？
    本文分享自华为云社区《【华为云MySQL技术专栏】GaussDB(forMySQL)表级恢复中mydumper、myloader的应用与性能优化》，作者：GaussDB数据库。 背景介绍表级时间点恢复技术为“误删表”场景提供了一种快速且精确的恢复方案。通过将指定时间点的数据恢复到临时实例，再把用户所需的......
  • 莫队
    普通版前言莫队是由集训队大佬莫涛提出来的，在此再次膜拜大佬！思想普通莫队主要用于离线的区间查询操作，当然，也不是所有的都适用，当一个区间\([l,r]\)的答案可以用\(O(1)\)的时间转化成\([l+1,r],[l-1,r],[l,r+1],[l,r-1]\)的答案，我们就可以考虑使用莫队。具体怎么做呢？其实......
  • 莫队算法C/C++实现
    目录简介 算法原理算法步骤C++实现应用场景莫队算法（Mo'sAlgorithm）是一种用于解决区间查询和更新问题的算法，由俄罗斯选手莫洛佐夫（MoMorozov）提出。它在算法竞赛和某些计算密集型任务中非常有用，尤其是在需要处理大量区间查询和更新操作时。莫队算法以其高效性和简洁性......
  • 区间众数（分块）
    题目描述给定一个序列\(a_1,a_2,\dots,a_n\)，\(m\)个询问。每个询问指定一个区间\([l,r]\)，你需要输出\(a_l,a_{l+1},\dots,a_r\)这些数字里出现次数最多的数的出现次数。输入第一行一个整数\(T(1\leqT\leq6)\)，表示测试数据的组数。每组数据第一行两个数\(n,m(1\leqn,m\leq......
  • 莫队详解
    莫队详解一、莫队定义莫队是由2010年信息学国家集训队队员莫涛发明的一种算法，可以将静态离线区间查询的时间复杂度将至\(O(m\sqrt{n})\)下面便是一道莫队例题Lougu1972[SDOI2009]HH的项链虽然这道题莫队过不了，但是确实是很好的一道莫队题。题意:给你一个又\(n\)个......
  • 分块、莫队、块状链表及一些根号方法 总结
    第二分块没改出来给我干破防了。提交记录：五彩斑斓的世界（）。分块的种类序列分块：本质是在下标轴（\(i\)）上分块。值域分块：本质是在值的轴（\(a_i\)）上分块。操作分块：本质是在时间轴（一般是输入顺序）上分块。这几种分块应该是可以套的。分块、莫队、根号分治的核心平衡。平衡整块......
  • 莫队的 1.5 近似构造 题解
    前言题目链接：洛谷。感觉T4比T3水，虽然我都没做出来。题意简述给定\(1\simn\)的排列\(a\)和\(m\)个区间\([l_i,r_i]\)。定义值域区间\([L,R]\)的价值为\(\operatorname{val}([L,R])\operatorname{:=}\max\limits_{i=1}^m\sum\limits_{k=l_i}^{r_i}[L......
  • 莫队算法
    前言莫队是由莫涛提出的一种离线算法，是分块与双指针的结合，一般可以在\(O(n\sqrtn)\)或者\(O(n\sqrtm)\)的复杂度解决一些种类问题。普通莫队SP3267DQUERY-D-query给你一个长度为\(n\)的数列\(A\)，\(m\)次询问，每次询问区间\([l,r]\)内的不同数字的个数。如果......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99