Acwing 2521. 数颜色
墨墨购买了一套 N NN 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。
墨墨会像你发布如下指令：
Q L R 代表询问你从第 L 支画笔到第 R 支画笔中共有几种不同颜色的画笔。
R P Col 把第 P支画笔替换为颜色 C o ll。
为了满足墨墨的要求，你知道你需要干什么了吗？
输入格式
第 1 行两个整数 N , M 分别代表初始画笔的数量以及墨墨会做的事情的个数。
第 2 行 N个整数，分别代表初始画笔排中第 i 支画笔的颜色。
第 3 行到第 2+M 行，每行分别代表墨墨会做的一件事情，格式见题干部分。
输出格式
对于每一个 Query 的询问，你需要在对应的行中给出一个数字，代表第 L 支画笔到第 R 支画笔中共有几种不同颜色的画笔。
数据范围
1 ≤ N , M ≤ 10000
修改操作不多于 1000 次，
所有的输入数据中出现的所有整数均大于等于 1 且不超过 10^6
代码
#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; }q[N]; struct Modify { 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--]]; while (t < q[k].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); } while (t > q[k].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; }
回滚莫队
适用于加入一个数很方便，但是删除一个数很困难的问题
①暴力求右端点在块内的情况
②右端点不在块内时 ，cnt[] res 维护区间的块外部分
排序方式
因为需要保持同一个块内的询问右端点递增，所以不能使用基础莫队的优化版排序方式，而应该：
首先按照分块的编号递增排序，然后块内按照右端点递增排序
分块大小和时间复杂度
模板代码
#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, S = 1e6 + 10; int n, m; int cnt[N], a[N]; LL ans[N]; vector<int>nums; int block; struct Query { int id, l, r; }q[N]; bool cmp(const Query& a, const Query& b) { int l = a.l / block, r = b.l / block; if (l != r)return l < r; return a.r < b.r; } void add(int x, LL& res) { cnt[x]++; res = max(res, (LL)cnt[x] * nums[x]); } void solve() { scanf("%d%d", &n, &m); block = sqrt(n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); nums.push_back(a[i]); } // 离散化 sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); for (int i = 1; i <= n; ++i) a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin(); // 离线存储询问 for (int i = 0; i < m; ++i) { int l, r; scanf("%d%d", &l, &r); q[i] = { i,l,r }; } sort(q, q + m, cmp); // x y 为询问的编号 for (int x = 0; x < m;) { // 求出当前块包含了哪些询问 [x,y) int y = x; while (y < m && q[x].l / block == q[y].l / block)y++; // right 表示当前块的右端点 int right = q[x].l / block * block + block - 1; // 如果当前询问的右端点在块内 那么就暴力求 while (x < y && q[x].r <= right) { LL res = 0; int id = q[x].id, l = q[x].l, r = q[x].r; for (int k = l; k <= r; ++k)add(a[k], res); ans[id] = res; // 每次求完，要将cnt数组清空 for (int k = l; k <= r; ++k)cnt[a[k]]--; x++; } // 如果当前询问的右端点在块外 LL res = 0; int i = right, j = right + 1; // 左右指针 while (x < y) { int id = q[x].id, l = q[x].l, r = q[x].r; // 因为按右端点排序 所以 i 只会往右递增 不会对 i 指向的数进行删除操作 while (i < r)add(a[++i], res); // 对于每个查询 都让 j 从块的右端点向左移动 // 先将答案（分块右端点 --- 右指针）备份 LL backup = res; // 左指针 j 往左扫到查询的左端点，看能否更新res while (j > l)add(a[--j], res); ans[id] = res; // 每次将 通过 j 加入的数删除 while (j < right + 1)cnt[a[j++]]--; // 恢复 res 的备份 res = backup; x++; } // 对每个块处理完后 cnt要清零 memset(cnt, 0, sizeof cnt); } for (int i = 0; i < m; ++i)printf("%lld\n", ans[i]); } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
Acwing2523. 历史研究
IOI 国历史研究的第一人——JOI 教授，最近获得了一份被认为是古代IOI 国的住民写下的日记。
JOI 教授为了通过这份日记来研究古代IOI 国的生活，开始着手调查日记中记载的事件。
日记中记录了连续 N天发生的时间，大约每天发生一件。
事件有种类之分。第 i 天 (1≤i≤N) 发生的事件的种类用一个整数 X i 表示，X i越大，事件的规模就越大。
JOI 教授决定用如下的方法分析这些日记：
选择日记中连续的一些天作为分析的时间段
事件种类 t 的重要度为 t× (这段时间内重要度为 t 的事件数)
计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。
输入格式
第一行两个空格分隔的整数 N 和 Q，表示日记一共记录了 N天，询问有 Q 次。
接下来一行 N NN 个空格分隔的整数 X 1 … X N ，X i 表示第 i 天发生的事件的种类。
接下来 Q 行，第 i行 (1≤i≤Q) 有两个空格分隔整数 A i 和 B i，表示第 i次询问的区间为 [ A i , B i ]
输出格式
输出 Q行，第 i行(1≤i≤Q) 一个整数，表示第 i 次询问的最大重要度。
数据范围
代码
#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, S = 1e6 + 10; int n, m; int cnt[N], a[N]; LL ans[N]; vector<int>nums; int block; struct Query { int id, l, r; }q[N]; bool cmp(const Query& a, const Query& b) { int l = a.l / block, r = b.l / block; if (l != r)return l < r; return a.r < b.r; } void add(int x, LL& res) { cnt[x]++; res = max(res, (LL)cnt[x] * nums[x]); } void solve() { scanf("%d%d", &n, &m); block = sqrt(n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); nums.push_back(a[i]); } // 离散化 sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); for (int i = 1; i <= n; ++i) a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin(); // 离线存储询问 for (int i = 0; i < m; ++i) { int l, r; scanf("%d%d", &l, &r); q[i] = { i,l,r }; } sort(q, q + m, cmp); // x y 为询问的编号 for (int x = 0; x < m;) { // 求出当前块包含了哪些询问 [x,y) int y = x; while (y < m && q[x].l / block == q[y].l / block)y++; // right 表示当前块的右端点 int right = q[x].l / block * block + block - 1; // 如果当前询问的右端点在块内 那么就暴力求 while (x < y && q[x].r <= right) { LL res = 0; int id = q[x].id, l = q[x].l, r = q[x].r; for (int k = l; k <= r; ++k)add(a[k], res); ans[id] = res; // 每次求完，要将cnt数组清空 for (int k = l; k <= r; ++k)cnt[a[k]]--; x++; } // 如果当前询问的右端点在块外 LL res = 0; int i = right, j = right + 1; // 左右指针 while (x < y) { int id = q[x].id, l = q[x].l, r = q[x].r; // 因为按右端点排序 所以 i 只会往右递增 不会对 i 指向的数进行删除操作 while (i < r)add(a[++i], res); // 对于每个查询 都让 j 从块的右端点向左移动 // 先将答案（分块右端点 --- 右指针）备份 LL backup = res; // 左指针 j 往左扫到查询的左端点，看能否更新res while (j > l)add(a[--j], res); ans[id] = res; // 每次将 通过 j 加入的数删除 while (j < right + 1)cnt[a[j++]]--; // 恢复 res 的备份 res = backup; x++; } // 对每个块处理完后 cnt要清零 memset(cnt, 0, sizeof cnt); } for (int i = 0; i < m; ++i)printf("%lld\n", ans[i]); } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
