首页 > 其他分享 >莫队

莫队

时间：2023-07-11 17:48:40浏览次数：31  
标签：cnt frac int res 端点 莫队

简介

用于解决一类离线区间询问问题。将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

普通莫队算法

概述

对于序列上的区间询问问题，如果从 \([l, r]\) 答案能够 \(O(1)\) 扩展到 \([l - 1, r],[l + 1, r],[l, r + 1],[l, r - 1]\)（即与 \([l, r]\) 相邻的区间）的答案，那么可以在 \(O(n \sqrt n)\) 的复杂度内求出所有询问的答案。

例题

HH的项链

做法概述

先将每次询问的区间离线下来，然后进行排序，再顺序处理每个询问，暴力从上一个区间转移到下一个区间。

排序方法：对于这些区间（\([l, r]\)），右端点（\(l\)）单调，左端点（\(r\)）用分块的思想进行处理。左端点（\(r\)）按分块编号排序，若编号不同，则从小到大排序；若编号相同，则按右端点（\(l\)）下标从小到大排序（双关键字排序）。

实现

struct Query {
	int id, l, r;
} q[S];

int cnt[S];

int get(int x) {
	return x / len;
}

bool cmp(const Query &a, const Query &b) {
	int i = get(a.l), j = get(b.l);
	if (i != j) return i < j;
	return a.r < b.r;
}

void add(int x, int &res) {
	cnt[x]++;
	if (cnt[x] == 1) res++;
}

void del(int x, int &res) {
	cnt[x]--;
	if (cnt[x] == 0) res--;
}

void solve() {
	for (int k = 0, i = 0, j = 1, res = 0; k < m; k ++ ) {// j 为左端点，i 为右端点
		int id = q[k].id, l = q[k].l, r = q[k].r;
		while (i < r) add(w[ ++ i], res);
		while (i > r) del(w[i -- ], res);
		while (j < l) del(w[j ++ ], res);
		while (j > l) add(w[ -- j], res);
		ans[id] = res;
	}
}

int main() {
	n = read();
	for (int i = 1; i <= n; i ++ ) w[i] = read();
	m = read();
	len = sqrt((double)n);
	for (int i = 0; i < m; i ++ ) {
		int l = read(), r = read();
		q[i] = {i, l, r};
	}
	sort(q, q + m, cmp);
	solve();
	for (int i = 0; i < m; i ++ ) write(ans[i]), puts("");
	return 0;
}

一些优化：

  1. 可以适当将块长增长。

    设块长为 \(a\)，则共有 \(\frac n a\) 块。

    右端点（\(r\)）：\(n \times \frac{n}{a} = \frac{n^2}{a}\)

    左端点（\(l\)）：\(m \times a = am\)

    当 \(\frac{n ^ 2}{a} = am\) 时，速度最快。

    解得 \(a = \sqrt{\frac{n ^ 2}{m}}\)。

    所以上面的代码中第 42 行就可以改成：

    len = sqrt((double)n * n / m);

  2. 进行奇偶排序

    奇数块递增排序，偶数块递减排序（反之亦可）（不太好证明，在此不作解释）。

    struct node {
	int id, l, r;
	
	bool operator < (const node &x) const {
		if (l / len != x.l / len) return l < x.l;
		if ((l / len) & 1) return r < x.r;
		return r > x.r;
	}
};

    细节,如果使用 sort 比较两个函数,不能出现 a < b 和 a > b 同时为真的情况,否则会运行错误

复杂度分析

\(O(n \sqrt m)\)

（不想写了，暂时先不展开写）

带修改莫队

特点

强行让普通莫队待修改，像 DP 一样，强行加上一维时间维，表示这次操作的时间。

时间维表示经历的修改次数。

即把询问 \([l, r]\) 变成 \([l, r, time]\)。

那么坐标也可以在时间维上移动，即 \([l, r, time]\) 多了一维可以移动的方向，可以变成：

  • \([l - 1, r, time]\)

  • \([l + 1, r, time]\)

  • \([l, r - 1, time]\)

  • \([l, r + 1, time]\)

  • \([l, r, time - 1]\)

  • \([l, r, time + 1]\)

这样转移也是 \(O(1)\) 的，只是排序又多了一个关键字。

可以用和普通莫队类似的方法排序转移，做到 \(O(n^\frac 5 3)\)。

这一次的排序方式是以 \(n^\frac 2 3\) 为一块，分成了 \(n^\frac 1 3\) 块。

第一关键字是左端点所在块，第二关键字是右端点所在块（不同于普通莫队），第三关键字是时间。

最优块长及时间复杂度分析：

（要求导啊！！！不会啊！！！）那就直接上结论吧……

当块长取 \(\frac{n^\frac 2 3 t ^ \frac 1 3}{m ^ \frac 1 3}\) 时有最优时间复杂度 \(O(n^\frac 2 3 m ^\frac 2 3 t ^ \frac 1 3)\)。

常说的 \(O(n^\frac 5 3)\) 便是把 \(n, m, t\) 当作同数量级的时间复杂度。

例题

[国家集训队] 数颜色 / 维护队列

题目大意：给定一个序列，\(M\) 个操作。

有两种操作：

  1. 修改序列上某一位的数字

  2. 询问区间 \([l, r]\) 中数字的种类数（多个相同数字只算一个）

可以发现，如果没有操作 1（修改）的话，用普通莫队就可以解决，但是题目带有单点修改，所以用带修改的莫队。

过程

首先是普通莫队（具体过程略），接下来考虑修改（单点修改）：

  • 把某一位的数字修改掉。加入我们是从一个经理修改次数为 &i& 的询问转移到修改次数为 \(j\) 的询问上。若 \(i < j\)，我们需要把第 \(i + 1\) 个到第 \(j\) 个修改强行加上；若 \(i > j\)，则需要把第 \(i\) 个到第 \(j + 1\) 个修改强行还原。

  • 例如，我们从修改次数为 \(3\) 的询问转移到修改次数为 \(5\) 的询问上，那么就需要加上第 \(4, 5\) 次修改，反之，就要将第 \(4, 5\) 次修改还原。

修改过程：

  1. 若在区间内，则删除原有的数，再加上改变后的的数；

  2. 若不在区间内，\(cnt\) 不变，直接修改该项为改变后的数（看代码）

  3. trick：修改时，善于运用 swap 函数，交换即可，这样在还原的时候便于再交换回来（看代码）。

实现

#include <bits/stdc++.h>

using namespace std;

const int N = 133335, S = 1000010;

int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];

struct Query {
	int id, l, r, t;
} q[N];

struct Modify {
	int p, c;
} c[N];

int get(int x) {
	return x / len;
}

bool cmp(const Query &a, const Query &b) {
	int al = get(a.l), ar = get(a.r);
	int bl = get(b.l), br = get(b.r);
	if (al != bl) return al < bl;
	if (ar != br) return ar < br;
	return a.t < b.t;
}

void add(int x, int &res) {
	res += !cnt[x]++;
}

void del(int x, int &res) {
	res -= !--cnt[x];
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ ) scanf("%d", w + i);
	for (int i = 0; i < m; i ++ ) {
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);
		if (*op == 'Q') mq ++, q[mq] = (Query) {mq, a, b, mc};
		else c[ ++ mc] = (Modify) {a, b};
	}
	len = pow(n, 2.0 / 3.0);//虽然但是，不知道为啥，
	//块长设置为 cbrt((double)n * mc) + 1 就是不行
	//块长设置成这样才能过
	//这个是当 n 和 t 是同一数量级的时候的块长
	sort(q + 1, q + mq + 1, cmp);
	for (int i = 0, j = 1, t = 0, k = 1, res = 0; k <= mq; k ++ ) {
		int id = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
		while (i < r) add(w[ ++ i], res);
		while (i > r) del(w[i -- ], res);
		while (j < l) del(w[j ++ ], res);
		while (j > l) add(w[ -- j], res);
		while (t < tm) {
			t ++ ;
			if (c[t].p >= j && c[t].p <= i) {
				del(w[c[t].p], res);
				add(c[t].c, res);
			}
			swap(w[c[t].p], c[t].c);
		}
		while (t > tm) {
			if (c[t].p >= j && c[t].p <= i) {
				del(w[c[t].p], res);
				add(c[t].c, res);
			}
			swap(w[c[t].p], c[t].c);
			t -- ;
		}
		ans[id] = res;
	}
	for (int i = 1; i <= mq; i ++ ) printf("%d\n", ans[i]);
	return 0;
}

回滚莫队

引入

有些题目在区间转移时，可能会出现增加或删除无法实现，那么这个时候就要使用回滚莫队，时间复杂度是 \(O(n \sqrt m)\)。

核心思想：既然只能实现一个操作，那就只使用一个操作，剩下的用回滚解决。

下面介绍插入简单，删除不易的回滚莫队：

首先，和普通莫队一样，是双关键字排序：

  1. \(l\) 所在块的编号；

  2. \(r\) 右端点下标。

处理询问时分两种：

  1. 块内。暴力求即可，这样，剩下的必然在块间（跨块）。

  2. \(j\) 是左端点，\(i\) 是右端点，假设询问区间包含了块 \(1\) 的后半截和块 \(2\) 的前半截，那么处理时分成两个部分——在块 \(1\) 内的部分 和 不在块 \(1\) 内的部分。先说第二个部分，此时 \(cnt\) 和 \(res/sum/ans\) 维护的不是整个区间，而是块 \(2\) 中询问的部分。\(j\) 应从块 \(2\) 的第一个位置开始，\(i\) 应在块 \(1\) 与块 \(2\) 的分界线上（此时区间为空）。至于第一个部分，长度一定小于等于 \(\sqrt n\)，所以可以暴力加，之后再暴力删（\(cnt\) 更新，不用维护 \(res\)，\(res\) 只存初始的（备份）（具体看代码））。

回滚指的就是暴力加，再回滚删除。

例题

歴史の研究

给定一个长度为 \(n\) 的数组 \(A\) 和 \(m\) 个询问（\(1 \leqslant n, m \leqslant 10^5\)），每次询问一个区间 \([L, R]\) 内重要度最大的数字，要求输出其重要度。一个数字 \(i\) 的重要度定义为 \(i \) 乘上 \(i\) 在区间内出现的次数。

实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m, len;
int w[N], cnt[N];
long long ans[N];

struct Query {
	int id, l, r;
} q[N];

vector <int> nums;

int get(int x) {
	return x / len;
}

bool cmp(const Query &a, const Query &b) {
	int i = get(a.l), j = get(b.l);
	if (i != j) return i < j;
	return a.r < b.r;
}

void add(int x, long long &res) {
	cnt[x]++;
	res = max(res, (long long)cnt[x] * nums[x]);
}

int main() {
	scanf("%d%d", &n, &m);
	len = sqrt(n);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), nums.push_back(w[i]);
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	for (int i = 1; i <= n; i ++ )
		w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();
		//离散化
	for (int i = 0; i < m; i ++ ) {
		int l, r;
		scanf("%d%d", &l, &r);
		q[i] = (Query) {i, l, r};
	}
	sort(q, q + m, cmp);
	
	for (int x = 0; x < m;) {
		int y = x;
		while (get(q[y].l) == get(q[x].l) && y < m) y ++ ;
		int right = get(q[x].l) * len + len - 1;
		while (x < y && q[x].r <= right) {
			long long res = 0;
			int id = q[x].id, l = q[x].l, r = q[x].r;
			for (int k = l; k <= r; k ++ ) add(w[k], res);
			ans[id] = res;
			for (int k = l; k <= r; k ++ ) cnt[w[k]] -- ;
			x ++ ;
		}
		long long res = 0;
		int i = right, j = right + 1;
		while (x < y) {
			int id = q[x].id, l = q[x].l, r = q[x].r;
			while (i < r) add(w[ ++ i], res);
			long long bres = res;
			while (j > l) add(w[ -- j], res);
			ans[id] = res;
			while (j < right + 1) cnt[w[j ++ ]] -- ;
			res = bres;
			x ++ ;
		}
		memset(cnt, 0, sizeof cnt);
	}
	for (int i = 0; i < m ; i ++ ) printf("%lld\n", ans[i]);
	return 0;
}

复杂度证明

假设块长为 \(a\)：

  • 对于左右端点在同一个块内的询问，可以在 \(O(b)\) 时间内计算；

  • 对于其他询问，考虑左端点在相同块内的询问，他们的右端点单调递增，移动右端点的时间复杂度是 \(O(n)\)，而左端点单次询问的移动不超过 \(a\)，因为有 \(\frac n a\) 个块，所以总复杂度是 \(O(am + \frac {n^2} {a})\)，取 \(a = \frac n {\sqrt m}\) 最优，时间复杂度为 \(O(n \sqrt m)\)。

参考资料：AcWing、Oi Wiki、《算法训练营》

标签：cnt,frac,int,res,端点,莫队
From： https://www.cnblogs.com/Ifyoung/p/17516721.html

相关文章

  • 莫队学习笔记
    这是一篇模仿算导的学习笔记/题解。例题：P1494给定一个长为\(n\)的数组\(a\)和\(m\)个询问（有序数对）\(b_i=(l_i,r_i)\)，询问允许离线，对每个询问\((l,r)\)求出满足\(l\lei\ltj\ltr\wedgea_i=a_j\)的数对\((i,j)\)数量.证明：若数\(x\)在\(a\)数组下标为......
  • 莫队学习笔记
    引入问题给出一个长度为\(n\)的数组\(A\)，接下来\(q\)次询问，每次询问求\([l,r]\)中有多少组\((i,j,k)\)使得\(a_i=a_j=a_k(i<j<k)\)。保证\(1\leqn\leq10^5,1\leqA_i\leqn(1\leqi\leqn)\)。莫队的基础思想——区间转移简单分析问题，貌似并没有可加性，所以分块和......
  • 莫队 学习笔记
    莫队学习笔记引入莫队算法是一种优美的暴力算法，可以用来处理大量的区间询问。前提是，维护的信息可以高效地插入、删除。我们就以一道题为例，来初探莫队：洛谷P3901数列找不同题意：给定一个数列，\(q\)次询问，问区间\([l,r]\)内的数是否各不相同。首先，我们很容易想到，问某个区间......
  • permu题解(树上莫队)(非正解)
    题目传送门题意给出一个长度为$n$的排列$P(P1,P2,...Pn)$，以及$m$个询问。每次询问某个区间$[l,r]$中，最长的值域连续段长度。思路首先这道题事求连续段的长度，打个莫队先#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;namespaceTestify{ inlineint......
  • 【学习笔记】(2) 基础莫队——优美的暴力
    莫队，是莫涛发明的一种解决区间查询等问题的离线算法，基于分块思想，复杂度一般为\(\mathcal{O}(N\sqrt{N})\)普通莫队例题：P1972[SDOI2009]HH的项链（其实这道题用莫队过不了，就仅是用来引入莫队而已）题意：长度为\(N\)的序列，\(M\)次询问，每次询问一段闭区间内有多少个不同的数。......
  • 【BZOJ4241】【回滚莫队模板题】历史研究
    Description给定一个序列，每次询问区间[l,r][l,r]内，所有权值与其出现次数的乘积的最大值。Solution回滚莫队模板题。将询问以左端点所在块为第一关键字，右端点为第......
  • 莫队学习笔记
    概念莫队是一种幽雅的暴力。用于处理区间问题。核心思想就是把询问离线下来，然后维护双指针按一定顺序处理每个询问。精髓就在于一定顺序。首先确定一个块长，然后将左端点的位置除以块长，把询问分成若干块。在每个块里按右端点排序。发现当块长为\(\sqrtn\)时两个指针各移动\(......
  • 数据结构-莫队二次离线
    莫队二次离线问题：给一个序列a，每次询问区间里面有几个逆序对刚刚又睡了半小时，终于睡醒了\(n,m\leq1e5\)实现询问首先想一想莫队：对于初始询问区间[l,r]，将右指针r扩展到r+1，对于答案的贡献就是[l,r]里面大于a[r+1]的数量，写成数学公式就是\(\sum_{i=l}^r(a[i]>a[r+1])\)然后可......
  • 分块思想基础莫队
    分块将数组分成sqrt(n)块，每次进行区间操作或者查询的时候，对于完整的块可以通过预处理的信息o1得到，不完整的块直接暴力跑，所以最坏复杂度是sqrt(n)。分块模板constintN=100010,B=sqrt(N);intblock;intst[B],ed[B],bel[N];intsum[B],tag[B];inta[N],sz[B];vo......
  • 莫队
    一种用来处理序列上区间询问问题的算法。来看一下最经典的莫队题。区间不同数给定长为\(n\)的序列\(a\),有\(m\)组询问。每组询问给定一个区间\([l,r]\),求区间内有多少种不同的数。\(n,m\le10^5\)，\(a_i\in[0,10^6]\)我们可以观察到如果我们已知\([l,r]\)的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99