20240923 分块莫队专题
回滚莫队
回滚莫队适用于添加与删除中有一种较为困难的情况。大致思想如下:
对原序列分块,将询问按左端点所在块编号排序,同一块内按右端点排序。对每个块,视情况初始化左右指针,扫一遍询问。先移动右指针到询问右端点,记录当前状态的答案,再将左指针移到询问左端点,计算询问的答案,最后把左指针撤回块的左端点,答案撤销,撤销对某些状态的影响。这样每一块中右指针移动 \(O(n)\) 次,对于每个询问左端点最多移动 \(O(\sqrt n)\) 次,于是可以保证时间复杂度。
注意:在不删除的回滚莫队中,询问左右端点在同一块中时需要暴力求解。
[1.历史研究](歴史の研究 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) (不删除莫队)
给你一个数组 \(a\) 和 \(m\) 个询问 \((1\leq n,m\leq10^5)\),每次询问一个区间内重要度最大的数字,输出其重要度。一个数字 \(i\) 的重要度的定义为 \(i\) 乘上 \(i\) 在区间内出现的次数。
这个题目提添加很好实现,因为如果添加影响答案,那么新答案一定是刚刚添加的数字的重要度,但是删除很难实现。所以使用回滚莫队。
struct Query{
int l, r, ans, idx;
}q[N];
int n, Q, a[N], b[N], T, pos[N], L[N], R[N], cnt[N];
void init(){
map<int, int> mp;
sort(b + 1, b + n + 1);
int m = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= m; i++) mp[b[i]] = i;
for (int i = 1; i <= n; i++) a[i] = mp[a[i]]; //离散化
int K = sqrt(n); T = n / K + (bool)(n % K); //对原序列分块
for (int i = 1; i <= T; i++){
L[i] = R[i - 1] + 1;
R[i] = min(L[i] + K - 1, n);
for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
}
sort(q + 1, q + Q + 1, [&](Query a, Query b){
return pos[a.l] != pos[b.l] ? pos[a.l] < pos[b.l] : a.r < b.r;
}); //对询问排序
}
void add(int p, int &maxn){
maxn = max(maxn, ++cnt[a[p]] * b[a[p]]);
}
signed main(){
n = read(), Q = read();
for (int i = 1; i <= n; i++) a[i] = b[i] = read();
for (int i = 1; i <= Q; i++) q[i] = {read(), read(), 0, i};
init();
for (int i = 1, p = 1; i <= T; i++){
int ans = 0, l = R[i] + 1, r = R[i];
while (pos[q[p].l] == i){
if (pos[q[p].l] == pos[q[p].r]){ //暴力求解
for (int i = q[p].l; i <= q[p].r; i++){
q[p].ans = max(q[p].ans, ++cnt[a[i]] * b[a[i]]);
}
for (int i = q[p].l; i <= q[p].r; i++) --cnt[a[i]];
p++;
continue;
}
while (r < q[p].r) add(++r, ans); //移动右指针
int tmp = ans; //记录状态
while (l > q[p].l) add(--l, ans); //移动左指针
q[p].ans = ans; ans = tmp;
while (l < R[i] + 1) cnt[a[l++]]--; //回滚
p++;
}
while (l <= r) cnt[a[l++]]--; //清空
}
sort(q + 1, q + Q + 1, [&](Query a, Query b){
return a.idx < b.idx;
});
for (int i = 1; i <= Q; i++) printf("%lld\n", q[i].ans);
return 0;
}
[2.秃子酋长]([[P8078 WC2022] 秃子酋长 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) (不添加莫队)
给一个排列 \(a\),有 \(m\) 次询问,每次询问区间内,排序后相邻的数在原序列中的位置的差的绝对值之和。\(1\leq n,m\leq 5\times10^5\)。
容易想到 set 维护当前集合,更新方式显然,设 \(n,m\) 同阶,那么这样是 \(O(n\sqrt{n\log n})\) 的。
注意到删除操作可以用链表做到 \(O(1)\),但链表难以添加,于是使用回滚莫队。
这题时限较紧,常数较小才能通过。
#define fi first
#define se second
int n, Q, T, a[N], L[N], R[N], pos[N], dlt[N], _[N];
long long ans[M], res;
struct Query{
int l, r, idx;
}q[M];
struct Node{
int pre, nxt, val;
}lst[N];
inline bool cmp(const Query &a, const Query &b){
return pos[a.l] != pos[b.l] ? pos[a.l] < pos[b.l] : a.r > b.r;
}
inline void init(){
int K = sqrt(2 * n); T = n / K + (bool)(n % K);
for (int i = 1; i <= T; i++){
L[i] = R[i - 1] + 1;
R[i] = min(L[i] + K - 1, n);
for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
}
sort(q + 1, q + Q + 1, cmp);
for (int i = 1; i <= n; i++) _[a[i]] = i;
for (int i = 1; i <= n; i++) lst[i] = {i - 1, i + 1, _[i]};
lst[1].pre = 0, lst[n].nxt = 0;
for (int i = 1 + 1; i <= n; i++) res += abs(lst[i].val - lst[lst[i].pre].val);
}
inline int del(const int &p){
int nxt = lst[p].nxt, pre = lst[p].pre, res = 0;
lst[pre].nxt = nxt, lst[nxt].pre = pre;
if (pre && nxt) res += labs(lst[nxt].val - lst[pre].val);
if (nxt) res -= labs(lst[nxt].val - lst[p].val);
if (pre) res -= labs(lst[p].val - lst[pre].val);
return dlt[p] = res; //这里用数组记录下删数时的贡献,回滚时直接调用,减小常数
}
inline int ret(const int &p){
int nxt = lst[p].nxt, pre = lst[p].pre;
lst[pre].nxt = lst[nxt].pre = p;
return -dlt[p];
}
int main(){
n = read(), Q = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= Q; i++) q[i] = {read(), read(), i};
init();
for (int i = 1, p = 1, l = 1, r = n; i <= T; i++){
if (pos[q[p].l] != i) continue;
for (; r < n; ) res += ret(a[++r]);
for (; l < L[i]; ) res += del(a[l++]);
for (; pos[q[p].l] == i; ){
for (; r > q[p].r; ) res += del(a[r--]);
for (; l < q[p].l; ) res += del(a[l++]);
ans[q[p].idx] = res;
for (; l > L[i]; ) res += ret(a[--l]);
p++;
}
}
for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
return 0;
}
这题还有一个版本,就是将求和改为求最小值,仍然用链表维护。查询最值可以用值域分块 \(O(1)\) 修改,\(O(\sqrt n)\) 查询。块长取 \(\sqrt{\frac{n^2}{m}}\) 时最优理论复杂度 \(O(n\sqrt m)\),但是常数过大,无法通过原题。
未完待续。。。
标签:分块,int,询问,pos,20240923,端点,ans,莫队 From: https://www.cnblogs.com/luyuyang/p/18535163