基础莫队
适用于求区间内不同数的个数问题
排序方式
如果当前两个区间左端点在同一个奇数块，那么按右端点递减排序，否则按右端点递增排序
分块大小和时间复杂度
模板代码
#include<bits/stdc++.h> #include<unordered_map> #pragma GCC optimize(2) // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } //template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 50010, M = 200010, S = 1000010; int n, m; int a[N], cnt[S], ans[M]; int block; struct Node { int id, l, r; }node[M]; bool cmp(const Node& a, const Node& b) { // 如果当前两个区间左端点在同一个奇数块，那么按右端点递减排序，否则按右端点递增排序 int l = a.l / block, r = b.l / block; return l ^ r ? l < r : (l & 1 ? a.r < b.r : 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])res--; } void solve() { cin >> n; for (int i = 1; i <= n; ++i)scanf("%d", &a[i]); cin >> m; for (int i = 1; i <= m; ++i) { int l, r; scanf("%d%d", &l, &r); node[i] = { i,l,r }; } block = n / sqrt(n); sort(node + 1, node + 1 + m, cmp); int i = 0, j = 1; int res = 0; for (int k = 1; k <= m; ++k) {// 对排序后的查询进行计算 int l = node[k].l; int r = node[k].r; // 将add del函数 通过运算优先级优化成常数 while (i < r)res += !cnt[a[++i]]++; while (i > r)res -= !--cnt[a[i--]]; while (j < l)res -= !--cnt[a[j++]]; while (j > l)res += !cnt[a[--j]]++; ans[node[k].id] = res; } for (int i = 1; i <= m; ++i) { printf("%d\n", ans[i]); } } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
HH的项链
题意
HH 有一串由各种漂亮的贝壳组成的项链。
HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。
HH 不断地收集新的贝壳，因此他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？
这个问题很难回答，因为项链实在是太长了。
于是，他只好求助睿智的你，来解决这个问题。
思路
莫队模板题
数据范围
与求某区间内不同数的思路相同，先用莫队思想把查询区间排序，与上题（HH的项链）不同的是，将 l 初始为 0，r初始为 n + 1，最初包括整个区间。这样每次用 l，r与当前查询的 lr比较。
例如，如果e[i].r
l 从0 开始类似。
相应的add del 操作也要进行更改，因为 r 变大或者 l 变小时，区间里的数是减少的。r 变小或者 l 变大时，区间里的数是增加的。
代码
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 1e5 + 10; int n, m; int a[N], ans[N], cnt[N]; int block; struct Node { int id, l, r; }node[N]; bool cmp(const Node& a, const Node& b) { if (a.l / block == b.l / block)return a.r < b.r; return a.l / block < b.l / block; } void add(int x, int& res) { cnt[x] ++; if (cnt[x] == 1)res++; } void del(int x, int& res) { cnt[x]--; if (!cnt[x])res--; } void solve() { while (~scanf("%d%d", &n, &m)) { memset(cnt, 0, sizeof cnt); for (int i = 1; i <= n; ++i)scanf("%d", &a[i]); block = sqrt(n); for (int i = 1; i <= m; ++i) { scanf("%d%d", &node[i].l, &node[i].r); node[i].id = i; } sort(node + 1, node + 1 + m, cmp); int l = 0, r = n + 1; int res = 0; for (int i = 1; i <= m; ++i) { int id = node[i].id; while (r < node[i].r)del(a[r++], res); while (r > node[i].r)add(a[--r], res); while (l < node[i].l)add(a[++l], res); while (l > node[i].l)del(a[l--], res); ans[id] = res; } for (int i = 1; i <= m; ++i)printf("%d\n", ans[i]); } } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
带修莫队
适用于查询区间内不同数的个数，加修改区间内某个数
排序方式：
bool cmp(Query& a, Query& b) { return (a.l / block) ^ (b.l / block) ? (a.l / block < b.l / block) : (a.r / block) ^ (b.r / block) ? (a.r / block < b.r / block) : (a.t < b.t); }
如果左端点块号奇偶性不同，按照块号递增排序
否则 如果右端点奇偶性不同，按照块号递增排序
否则 按照时间戳递增排序
分块大小和时间复杂度
模板代码
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 2e5 + 10, S = 1e6 + 10; int n, m; int cnt[S]; // 记录每个数出现的次数 int a[N]; // 原数组 int mq, mc; // 询问和修改的次数 int block; // 分块的大小 int ans[N]; // 记录每个询问的答案 struct Query { // 询问操作结构体 int id, l, r, t; // id 表示询问的先后顺序 // t 表示 时间戳 即离它最近的修改操作的编号 }q[N]; struct Modify { // 修改操作结构体 // 将 l 位置上的数修改成 r int l, r; }c[N]; bool cmp(Query& a, Query& b) { // 排序比较函数 return (a.l / block) ^ (b.l / block) ? (a.l / block < b.l / block) : (a.r / block) ^ (b.r / block) ? (a.r / block < b.r / block) : (a.t < b.t); } void del(int x,int &res){ // 删除操作 cnt[x]--; if (!cnt[x])res--; } void add(int x, int& res) { // 增加操作 if (!cnt[x])res++; cnt[x]++; } void solve() { cin >> n >> m; for (int i = 1; i <= n; ++i)scanf("%d", &a[i]); for (int i = 1; i <= m; ++i) { char op[2]; int l, r; scanf("%s%d%d", op, &l, &r); //离线存储所有询问和修改操作 if (op[0] == 'Q') q[++mq] = { mq,l,r,mc }; else c[++mc] = { l,r }; } block = cbrt((double)n * n); // 计算分块的大小 sort(q + 1, q + 1 + mq, cmp); int l = 1, r = 0, t = 0, res = 0; for (int k = 1; k <= m; ++k) { int id = q[k].id; // 水平区间上进行移动 while (l < q[k].l)res -= !--cnt[a[l++]]; while (l > q[k].l)res += !cnt[a[--l]]++; while (r < q[k].r)res += !cnt[a[++r]]++; while (r > q[k].r)res -= !--cnt[a[r--]]; // 时间戳上进行移动 // t 表示 1-t 的修改操作已经执行 while (t < q[k].t) { // 需要将时间戳往后移动 t++; // 如果需要修改的数在当前 [l, r] 区间内 // 将被修改的数删除，将修改成的数加入 if (c[t].l >= l && c[t].l <= r) { res -= !--cnt[a[c[t].l]]; res += !cnt[c[t].r]++; } // 每次操作将两个数 swap 一下，就不用存当前数被修改成了哪个数 swap(a[c[t].l], c[t].r); } while (t > q[k].t) { // 因为 t 较大 所以要先把当前的 t 删除 再 t-- if (c[t].l >= l && c[t].l <= r) { res -= !--cnt[a[c[t].l]]; res += !cnt[c[t].r]++; } swap(a[c[t].l], c[t].r); t--; } ans[id] = res; } for (int i = 1; i <= mq; ++i)printf("%d\n", ans[i]); } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
