首页 > 其他分享 >莫队

莫队

时间：2024-07-20 15:51:33浏览次数：15  
标签：cnt int rhs while qry 莫队 bid

莫队

假设 \(n, m\) 同阶，对于序列上的区间询问问题，如果得知 \([l, r]\) 的答案，可以在 \(O(1)\) 的时间推算出 \([l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1]\) 的答案，那么我们就可以在 \(O(n \sqrt{n})\) 的时间求出所有询问的答案。

普通莫队

实现

将所有的询问离线后以左端点所在的块为第一关键字，右端点为第二关键字进行排序。按排序后的顺序处理每一个询问，暴力从上一个区间的答案推出当前区间的答案。

注意移动指针时应先扩大区间, 后缩小区间。

时间复杂度 \(O(n \sqrt{n})\) 。

for (int i = 1, l = 1, r = 0; i <= m; ++i) {
    while (l > qry[i].l)
        add(--l);

    while (r < qry[i].r)
        add(++r);
    
    while (l < qry[i].l)
        del(l++);

    while (r > qry[i].r)
        del(r--); // 先扩大区间, 后缩小区间

    ans[qry[i].id] = result;
}

优化

调整块长

在随机数据下，块长设为 \(\dfrac{n}{\sqrt{m}}\)​ 会快一些。

奇偶性排序

在选择奇数块时，按照右端点从小到大排序，在偶数块时从大到小排序，这样可以减少右端点进行大跳动的次数，常数优化为原来的 \(\dfrac{1}{2}\) 。

原理：因为右指针移动到右边后就不需要跳回左边了，而跳回左边后处理下一个块是要跳动到右边的。

应用

SP3267 DQUERY - D-query

\(q\) 次询问区间数字种数。

\(n \leq 3 \times 10^4, q \leq 2 \times 10^5, a_i \leq 10^6\)

模板，下给出参考代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 7, Q = 2e5 + 7, V = 1e6 + 7;

struct Query {
	int l, r, bid, *ans;
	
	inline bool operator < (const Query &rhs) const {
		return bid == rhs.bid ? (bid & 1 ? r > rhs.r : r < rhs.r) : bid < rhs.bid;
	}
} qry[Q];

int a[N], cnt[V], ans[Q];

int n, q, Answer;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

inline void add(int x) {
	if (!cnt[a[x]])
		++Answer;
	
	++cnt[a[x]];
}

inline void del(int x) {
	--cnt[a[x]];
	
	if (!cnt[a[x]])
		--Answer;
}

signed main() {
	n = read();
	
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	
	q = read();
	int blocksiz = n / sqrt(q) + 1;
	
	for (int i = 1; i <= q; ++i) {
		qry[i].l = read(), qry[i].r = read();
		qry[i].bid = qry[i].l / blocksiz, qry[i].ans = ans + i;
	}
	
	sort(qry + 1, qry + 1 + q);
	
	for (int i = 1, l = 1, r = 0; i <= q; ++i) {
		while (l > qry[i].l)
			add(--l);
		
		while (r < qry[i].r)
			add(++r);
		
		while (l < qry[i].l)
			del(l++);
		
		while (r > qry[i].r)
			del(r--);
		
		*qry[i].ans = Answer;
	}
	
	for (int i = 1; i <= q; ++i)
		printf("%d\n", ans[i]);
	
	return 0;
}

P2709 小B的询问

\(q\) 次询问区间数字出现次数平方和。

\(n, m, a_i \leq 5 \times 10^4\)

因为 \(a_i\) 的值域只有 \(5 \times10^4\) ，所以我们开个桶记录每个数出现次数。

注意到：

\[(a+1)^2=a^2+2a+1 \]

于是我们就可以很轻松地设计 add 函数和 del 函数了。

P1494 [国家集训队] 小 Z 的袜子

\(m\) 次询问区间内任选两个数相同的概率。

\(n, m \leq 5 \times 10^4, a_i \leq n\)

将题意用式子可以表示为：

\[\cfrac{\sum \dfrac{cnt_k(cnt_k - 1)}{2}}{\dfrac{len(len-1)}{2}} = \dfrac{\sum cnt_k^2 - \sum cnt_k}{len(len-1)} = \dfrac{\sum cnt_k^2 - len}{len(len-1)} \]

问题就转化为求区间数字出现次数平方和。

CF617E XOR and Favorite Number

给定 \(k\) ，\(m\) 次询问区间内有多少子段异或和为 \(k\) 。

\(n, m \leq 10^5\) ，\(k, a_i \leq 10^6\)

可以先预处理出前缀异或值，由前缀和性质可知，问题转化为有多少对 \(i,j\) 满足 \(s_i \oplus s_j = k\) 。注意到 \(x \oplus y = k\) 等价于 \(x \oplus k = y\) 。于是问题转化为区间数字出现次数。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7, V = 2e6 + 7;

struct Query {
	int l, r, id, bid;

	inline bool operator < (const Query &rhs) const {
		return bid == rhs.bid ? (bid & 1 ? r > rhs.r : r < rhs.r) : l < rhs.l;
	}
} qry[N];

ll ans[N];
int a[N], cnt[V];

ll result;
int n, m, k, block;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

inline void add(int x) {
	result += cnt[a[x] ^ k], ++cnt[a[x]];
}

inline void del(int x) {
	--cnt[a[x]], result -= cnt[a[x] ^ k];
}

signed main() {
	n = read(), m = read(), k = read(), block = n / sqrt(m) + 1;

	for (int i = 1; i <= n; ++i)
		a[i] = a[i - 1] ^ read();

	for (int i = 1; i <= m; ++i)
		qry[i].l = read() - 1, qry[i].r = read(), qry[i].id = i, qry[i].bid = qry[i].l / block;

	sort(qry + 1, qry + 1 + m);

	for (int i = 1, l = 1, r = 0; i <= m; ++i) {
		while (l > qry[i].l)
			add(--l);

		while (r < qry[i].r)
			add(++r);

		while (l < qry[i].l)
			del(l++);

		while (r > qry[i].r)
			del(r--);

		ans[qry[i].id] = result;
	}

	for (int i = 1; i <= m; ++i)
		printf("%lld\n", ans[i]);

	return 0;
}

带修莫队

实现

强行加上一维时间维，表示该操作的时间。在查询时修改，改多了就还原回来，改少了就改过去。

设 \(n\) 为序列长度，\(m\) 个询问， \(t\) 个修改，则最佳块长为 \(\sqrt[3]{\dfrac{n^2 t}{m}}\) ，实际操作取块长为 \(n^{\frac{2}{3}}\) 即可。当 \(n, m, t\) 同数量级时时间复杂度为 \(O(n^{\frac{5}{3}})\) 。

应用

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

\(m\) 次操作：

  • Q l r ：求 \(a_{l, r}\) 中颜色总数。
  • R p c ：将 \(a_p\) 改为颜色 \(c\) 。

\(n, m \leq 1.5 \times 10^5, a_i \leq 10^6\)

模板，下给出参考代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 1.4e5 + 7, V = 1e6 + 7;

struct Update {
    int pos, val;
} upd[N];

int bel[N];

struct Query {
    int l, r, t, id;
    
    inline bool operator < (const Query &rhs) const {
        return bel[l] == bel[rhs.l] ? (bel[r] == bel[rhs.r] ? t < rhs.t : r < rhs.r) : l < rhs.l;
    }
} qry[N];

int a[N], cnt[V], ans[N];

int n, m, block, cntC, cntQ, result;

template <class T = int>
inline T read() {
    char c = getchar();
    bool sign = (c == '-');
    
    while (c < '0' || c > '9')
        c = getchar(), sign |= (c == '-');
    
    T x = 0;
    
    while ('0' <= c && c <= '9')
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return sign ? (~x + 1) : x;
}

inline char readc() {
    char c = getchar();

    while (c != 'Q' && c != 'R')
        c = getchar();

    return c;
}

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

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

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

signed main() {
    n = read(), m = read(), block = pow(n, 0.667) + 1;
    
    for (int i = 1; i <= n; ++i)
        a[i] = read(), bel[i] = i / block;
    
    for (int i = 1; i <= m; ++i) {
        if (readc() == 'R')
            upd[++cntC].pos = read(), upd[cntC].val = read();
        else
            qry[++cntQ].l = read(), qry[cntQ].r = read(), qry[cntQ].t = cntC, qry[cntQ].id = cntQ;
    }
    
    sort(qry + 1, qry + 1 + cntQ);
    
    for (int i = 1, l = 1, r = 0, t = 0; i <= cntQ; ++i) {
        while (l > qry[i].l)
            add(a[--l]);
        
        while (r < qry[i].r)
            add(a[++r]);
        
        while (l < qry[i].l)
            del(a[l++]);
        
        while (r > qry[i].r)
            del(a[r--]);
        
        while (t < qry[i].t)
            update(++t, qry[i]);
        
        while (t > qry[i].t)
            update(t--, qry[i]);
        
        ans[qry[i].id] = result;
    }
    
    for (int i = 1; i <= cntQ; ++i)
        printf("%d\n", ans[i]);
    
    return 0;
}

树上莫队

实现

考虑将树的括号序跑下来，在括号序上跑莫队。

设点 \(i\) 入栈时时间戳为 \(st_i\) ，出栈时时间戳为 \(ed_i\) ，则对于查询 \(u \to v\) 路径上的信息分类讨论（钦定 \(dfn_u < dfn_v\) ）：

  • \(u\) 是 \(v\) 的祖先：查询 \([st_u, st_v]\) 即可。
  • \(u\) 不是 \(v\) 的祖先：查询 \([ed_u, st_v]\) 和 \(LCA(u, v)\) 即可。

注意查询时应忽略出现两次的点，括号序要开两倍内存。

时间复杂度和普通莫队时一样的。

应用

COT2 - Count on a tree II

给定一棵 \(n\) 个点的树，\(m\) 次查询 \(u \to v\) 路径上节点颜色种数。

\(n \leq 4 \times 10^4, m \leq 10^5\)

模板，下给出参考代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

struct Graph {
	vector<int> e[N];
	
	inline void insert(int u, int v) {
		e[u].emplace_back(v);
	}
} G;

struct Query {
	int l, r, lca, id, bid;

	inline bool operator < (const Query &rhs) const {
		return bid == rhs.bid ? (bid & 1 ? r > rhs.r : r < rhs.r) : l < rhs.l;
	}
} qry[N];

int a[N], fa[N], dep[N], siz[N], son[N], top[N], st[N], ed[N], seq[N], cnt[N], ans[N];
bool tag[N];

int n, m, block, dfstime, result;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

void dfs1(int u, int f) {
	fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
	int mxsiz = -1;

	for (int v : G.e[u]) {
		if (v == f)
			continue;

		dfs1(v, u), siz[u] += siz[v];

		if (siz[v] > mxsiz)
			son[u] = v, mxsiz = siz[v];
	}
}

void dfs2(int u, int topf) {
	top[u] = topf, seq[st[u] = ++dfstime] = u;

	if (son[u])
		dfs2(son[u], topf);

	for (int v : G.e[u])
		if (v != fa[u] && v != son[u])
			dfs2(v, v);

	seq[ed[u] = ++dfstime] = u;
}

inline int LCA(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);

		x = fa[top[x]];
	}

	return dep[x] < dep[y] ? x : y;
}

inline void add(int x) {
	if (!cnt[a[x]])
		++result;

	++cnt[a[x]];
}

inline void del(int x) {
	--cnt[a[x]];

	if (!cnt[a[x]])
		--result;
}

inline void update(int x) {
	if (tag[x])
		del(x), tag[x] = false;
	else
		add(x), tag[x] = true;
}

signed main() {
	n = read(), m = read();
	vector<int> vec;

	for (int i = 1; i <= n; ++i)
		vec.emplace_back(a[i] = read());

	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());

	for (int i = 1; i <= n; ++i)
		a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();

	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		G.insert(u, v), G.insert(v, u);
	}

	dfs1(1, 0), dfs2(1, 1);
	block = n * 2 / sqrt(m * 0.667);

	for (int i = 1; i <= m; ++i) {
		int x = read(), y = read();

		if (st[x] > st[y])
			swap(x, y);

		qry[i].id = i, qry[i].lca = LCA(x, y);

		if (qry[i].lca == x)
			qry[i].l = st[x], qry[i].r = st[y], qry[i].lca = 0;
		else
			qry[i].l = ed[x], qry[i].r = st[y];

		qry[i].bid = qry[i].l / block;
	}

	sort(qry + 1, qry + 1 + m);

	for (int i = 1, l = 1, r = 0; i <= m; ++i) {
		while (l > qry[i].l)
			update(seq[--l]);

		while (r < qry[i].r)
			update(seq[++r]);

		while (l < qry[i].l)
			update(seq[l++]);

		while (r > qry[i].r)
			update(seq[r--]);

		if (qry[i].lca)
			update(qry[i].lca);

		ans[qry[i].id] = result;

		if (qry[i].lca)
			update(qry[i].lca);
	}

	for (int i = 1; i <= m; ++i)
		printf("%d\n", ans[i]);

	return 0;
}

P4074 [WC2013] 糖果公园

给定一棵树，\(q\) 次询问 \(u \to v\) 路径上 \(\sum a_{c_i} \sum_{j = 1}^{cnt_{c_i}} w_i\) 的值，其中 \(a_{c_i}\) 表示颜色 \(c_i\) 的价值，\(cnt_{c_i}\) 表示 \(c_i\) 出现次数，\(w_i\) 表示出现 \(i\) 次的价值。

\(n, m, q \leq 10^5\) 。

树上带修莫队模板，下给出参考代码。

回滚莫队

大前提：一类可离线问题。

  • 有些信息区间伸长时很好维护，区间缩短时却不好维护。
  • 有些信息区间缩短时很好维护，区间伸长时却不好维护。

实现

只增不删回滚莫队

首先将询问排序，应保证左端点在同一块内的询问的右端点单调不降。

若区间端点在同一块内，直接暴力解决即可。

否则每次处理询问时，令 \(l\) 指针指向块尾，\(r\) 指针指向块尾。先移动 \(r\) 指针，由于右端点不降，于是只要插入即可。保留下来信息，后移动 \(l\) 指针求解，处理完后用前面保留下来的信息恢复即可。

只删不增回滚莫队

首先将询问排序，应保证左端点在同一块内的询问的右端点单调不升。

若区间端点在同一块内，直接暴力解决即可。

否则每次处理询问时，令 \(l\) 指针指向块头，\(r\) 指针指向 \(n\) 。先移动 \(r\) 指针，由于右端点不升，于是只要删除即可。保留下来信息，后移动 \(l\) 指针求解，处理完后用前面保留下来的信息恢复即可。

时间复杂度分析

设分块大小为 \(B\) ，则时间复杂度为 \(O(mB + \dfrac{n^2}{B})\) ，当 \(B= \dfrac{n}{\sqrt{m}}\) 时复杂度最优为 \(O(n \sqrt{m})\) 。

应用

歴史の研究

\(m\) 次询问区间内 \(\max a_i \times cnt_{a_i}\) 。

\(n, m \leq 10^5\)

模板，下给出参考代码。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 7;

int bid[N];

struct Query {
	int l, r, id;
	
	inline bool operator < (const Query &b) const {
		return bid[l] == bid[b.l] ? r < b.r : l < b.l;
	}
} qry[N];

vector<int> vec;

ll ans[N];
int a[N], L[N], R[N], cnt[N], BFcnt[N];

ll result;
int n, m, block, tot;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

inline void prework() {
	block = pow(n, 0.666) + 1;

	while (++tot) {
		L[tot] = R[tot - 1] + 1, R[tot] = min(block * tot, n);
		fill(bid + L[tot], bid + R[tot] + 1, tot);

		if (R[tot] == n)
			break;
	}
}

inline ll BruteForce(int l, int r) {
	ll BFres = 0;
	
	for (int i = l; i <= r; ++i)
		BFres = max(BFres, 1ll * (++BFcnt[a[i]]) * vec[a[i]]);

	for (int i = l; i <= r; ++i)
		--BFcnt[a[i]];
	
	return BFres;
}

signed main() {
	n = read(), m = read();
	prework();
	
	for (int i = 1; i <= n; ++i)
		vec.emplace_back(a[i] = read());
	
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	
	for (int i = 1; i <= n; ++i)
		a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
	
	for (int i = 1; i <= m; ++i)
		qry[i].l = read(), qry[i].r = read(), qry[i].id = i;
	
	sort(qry + 1, qry + 1 + m);
	
	for (int i = 1, pos = 1; i <= tot; ++i) {
		memset(cnt, 0, sizeof(int) * vec.size());
		result = 0;
		
		for (int r = R[i], l = R[i] + 1; pos <= m && bid[qry[pos].l] == i; ++pos) {
			if (bid[qry[pos].r] == i) {
				ans[qry[pos].id] = BruteForce(qry[pos].l, qry[pos].r);
				continue;
			}
			
			while (r < qry[pos].r)
				++cnt[a[++r]], result = max(result, 1ll * cnt[a[r]] * vec[a[r]]);
			
			ll nowresult = result;
			
			while (l > qry[pos].l)
				++cnt[a[--l]], nowresult = max(nowresult, 1ll * cnt[a[l]] * vec[a[l]]);
			
			ans[qry[pos].id] = nowresult;
			
			while (l <= R[i])
				--cnt[a[l++]];
		}
	}
	
	for (int i = 1; i <= m; ++i)
		printf("%lld\n", ans[i]);
	
	return 0;
}

P5906 【模板】回滚莫队&不删除莫队

\(m\) 次询问区间中相同的数的最大出现下标差。

\(n, m \leq 2 \times 10^5\)

你说的对但这个是真模板题。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;

int bid[N];

struct Query {
	int l, r, id;
	
	inline bool operator < (const Query &b) const {
		return bid[l] == bid[b.l] ? r < b.r : l < b.l;
	}
} qry[N];

vector<int> vec;

int a[N], L[N], R[N], lpos[N], rpos[N], BFlpos[N], BFrpos[N], ans[N];

int n, m, block, tot;

template <class T = int>
inline T read() {
	char c = getchar();
	bool sign = (c == '-');
	
	while (c < '0' || c > '9')
		c = getchar(), sign |= (c == '-');
	
	T x = 0;
	
	while ('0' <= c && c <= '9')
		x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	
	return sign ? (~x + 1) : x;
}

inline void prework() {
	block = pow(n, 0.666) + 1;

	while (++tot) {
		L[tot] = R[tot - 1] + 1, R[tot] = min(block * tot, n);
		fill(bid + L[tot], bid + R[tot] + 1, tot);

		if (R[tot] == n)
			break;
	}
}

inline int BruteForce(int l, int r) {
	int result = 0;
	
	for (int i = l; i <= r; ++i) {
		BFlpos[a[i]] = min(BFlpos[a[i]], i), BFrpos[a[i]] = max(BFrpos[a[i]], i);
		result = max(result, BFrpos[a[i]] - BFlpos[a[i]]);
	}

	for (int i = l; i <= r; ++i)
		BFlpos[a[i]] = n + 1, BFrpos[a[i]] = 0;
	
	return result;
}

signed main() {
	n = read(), prework();
	
	for (int i = 1; i <= n; ++i)
		vec.emplace_back(a[i] = read());
	
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	
	for (int i = 1; i <= n; ++i)
		a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();

	m = read();
	
	for (int i = 1; i <= m; ++i)
		qry[i].l = read(), qry[i].r = read(), qry[i].id = i;
	
	sort(qry + 1, qry + 1 + m);
	fill(BFlpos, BFlpos + vec.size(), n + 1);
	fill(BFrpos, BFrpos + vec.size(), 0);
	
	for (int i = 1, pos = 1; i <= tot; ++i) {
		fill(lpos, lpos + vec.size(), n + 1);
		fill(rpos, rpos + vec.size(), 0);
		int result = 0;
		
		for (int r = R[i], l = R[i] + 1; pos <= m && bid[qry[pos].l] == i; ++pos) {
			if (bid[qry[pos].r] == i) {
				ans[qry[pos].id] = BruteForce(qry[pos].l, qry[pos].r);
				continue;
			}
			
			while (r < qry[pos].r) {
				++r;
				lpos[a[r]] = min(lpos[a[r]], r), rpos[a[r]] = max(rpos[a[r]], r);
				result = max(result, rpos[a[r]] - lpos[a[r]]);
			}
			
			int nowresult = result;
			
			while (l > qry[pos].l) {
				--l;
				BFlpos[a[l]] = min(BFlpos[a[l]], l), BFrpos[a[l]] = max(BFrpos[a[l]], l);
				nowresult = max(nowresult, max(rpos[a[l]], BFrpos[a[l]]) - min(lpos[a[l]], BFlpos[a[l]]));

			}			
			ans[qry[pos].id] = nowresult;

			while (l <= R[i])
				BFlpos[a[l]] = n + 1, BFrpos[a[l]] = 0, ++l;
		}
	}
	
	for (int i = 1; i <= m; ++i)
		printf("%d\n", ans[i]);
	
	return 0;
}

ZQUERY - Zero Query

\(m\) 次询问区间内区间和为 \(0\) 的最大区间长。

\(n, m \leq 5 \times 10^4, a_i = \pm 1\)

做完前缀和就和上题差不多了。

标签：cnt,int,rhs,while,qry,莫队,bid
From： https://www.cnblogs.com/wshcl/p/18313245/MoAlgorithm

相关文章

  • 二次离线莫队
    更新答案不是\(O(1)\)？答案可差分？二离来啦。P4887【模板】莫队二次离线先考虑贡献：\(f(x,[l,r])\)表示\(x\)对区间\([l,r]\)。考虑莫队每次的移动：\(r\tor'\)。答案增加为：\[\sum_{i\in[r+1,r']}f(i,[l,i-1])=\sum_{i\in[r+1,r']}f(i,[1,i-1])-f(i,[1,l-1])\]发现前......
  • 莫队
    普通莫队DQUERY-D-query先想一下最朴素的暴力怎么写。显然可以用一个\(cnt\)数组记录每种元素的出现次数，然后如果这种元素是第一次出现，则增加答案，时间复杂度\(O(nq)\)。然后考虑如果如何用一个已经求出来答案的询问推出另外一个询问的答案。显然我们要增加一部分数和删掉......
  • 【离线】- 莫队
    前言莫队是由莫涛提出的一种离线算法，是分块与双指针的结合，一般可以在\(O(n\sqrtn)\)或者\(O(n\sqrtm)\)的复杂度解决一些种类问题。普通莫队SP3267DQUERY-D-query给你一个长度为\(n\)的数列\(A\)，\(m\)次询问，每次询问区间\([l,r]\)内的不同数字的个数。如果......
  • 带修莫队模板
    取分块大小\(n^\frac{2}{3}\)最优。例题：数颜色#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;constintN=1e6+5;intcnt[N],a[N];structquery{intl,r,t,id;//加入时间戳};structmodfiy{intpos,val;};intmain(......
  • 莫队模板
    #include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;constintN=1e6+5;intcnt[N],a[N];structquery{intl,r,id;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;......
  • 从值域分块+莫队到二次离线莫队
    值域分块Q给定一个序列，实现单点修改\(O(1)\)，以及区间查询\(O(\sqrtn)\)A考虑设\(block_i\)表示块\(i\)的和，那么修改便是\(O(1)\)全局查询时，整块调用\(block\)，散块暴力即可\(O(\sqrtn)\)还有一些常见的例子，比如配合莫队代替主席树（区间mex）莫队二次离线普通莫队......
  • 算法课程笔记——普通莫队
    算法课程笔记——普通莫队......
  • 分块和莫队
    一、分块概念与作用1.概念：将数列等分为若干个不相交的区间，每一个区间称为一个块。2.作用：优化算法，降低复杂度。分块入门1题面：给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查询。分析：将n个元素等分成若干块，比如\(\{1,4,8,2,9,6,3,7,5\}\)，等分成3块，则第一块包含的数......
  • 莫队
    膜拜“莫涛”巨佬思路如果说给你一个数组，有\(q\)组询问，询问一个区间的区间和，那么有最原始的做法。维护一个左端点和一个右端点，每次一位一位移动断点，那么时间复杂度是\(n\timesq\)，那么如果我们将查询存起来，按一种我们想要的顺序去做呢？我们就可以排序，排序规则就是：B=sqrt(n......
  • 莫队（板子）
    莫队参考博客玄学暴力区间操作算法PPT解释的很清楚啦~,导致我没什么可写的\(qwq\)把所有询问离线下来后排序（左端点按块，右端点升序），然后从一个小区间通过左右端点的移动扩大区间，更新答案。复杂度主要在区间扩展,也就是左右指针的移动，对于莫队所有的优化几乎都是调整分块或排......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99