莫队
假设 \(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}\) 。
原理:因为右指针移动到右边后就不需要跳回左边了,而跳回左边后处理下一个块是要跳动到右边的。
应用
\(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;
}
\(q\) 次询问区间数字出现次数平方和。
\(n, m, a_i \leq 5 \times 10^4\)
因为 \(a_i\) 的值域只有 \(5 \times10^4\) ,所以我们开个桶记录每个数出现次数。
注意到:
\[(a+1)^2=a^2+2a+1 \]于是我们就可以很轻松地设计 add
函数和 del
函数了。
\(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}})\) 。
应用
\(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)\) 即可。
注意查询时应忽略出现两次的点,括号序要开两倍内存。
时间复杂度和普通莫队时一样的。
应用
给定一棵 \(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;
}
给定一棵树,\(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;
}
\(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;
}
\(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