【数据结构】带修莫队

2024-05-24 03:12

文章标签 数据结构修莫队

本文主要是介绍【数据结构】带修莫队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这篇中我们探讨了莫队的基础应用，但我们知道，莫队是个离线算法，需要读入所有询问才能进行处理，那如果遇到在线修改、但不需要在线输出的问题，我们有没有办法用莫队解决呢？

于是就产生了带修莫队，普通的莫队我们只记录下当前的左右端点，和当前询问的左右端点进行比较，对于带修改的问题，我们只需要多记录一个时间戳 time 就可以解决了

对于每一个询问，首先依然是处理当前端点和询问端点的关系：

while (l < ql) del(l ++ );
while (l > ql) add( -- l);
while (r > qr) del(r -- );
while (r < qr) add( ++ r);

然后处理当前时间和询问时间的关系：

while (time < qt)
{time ++ ; // 更新时间if (ql <= md[time].pos && md[time].pos <= qr) del(md[time].pos); // 删除旧的swap(a[md[time].pos], md[time].color); // 更新原数组if (ql <= md[time].pos && md[time].pos <= qr) add(md[time].pos); // 加上新的while (time > qt)
{if (ql <= md[time].pos && md[time].pos <= qr) del(md[time].pos); // 删除旧的swap(a[md[time].pos], md[time].color); // 更新原数组if (ql <= md[time].pos && md[time].pos <= qr) add(md[time].pos); // 加上新的time -- ; // 更新时间
}

记得修改一下排序条件：

bool cmp (query a, query b)
{return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r] ? belong[a.r] < belong[b.r] : a.t < b.t));
}

看个例题：P1903 [国家集训队] 数颜色 / 维护队列

$co d e$

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;struct query {int l, r, t, id;
} q[N];struct modify {int pos, color;
} md[N];int a[N], belong[N], cnt1, cnt2, nw, cnt[N], ans[N], sz, bnum;bool cmp (query a, query b)
{return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r] ? belong[a.r] < belong[b.r] : a.t < b.t));
}void add(int pos)
{if (!cnt[a[pos]]) nw ++ ;cnt[a[pos]] ++ ;
}void del(int pos)
{cnt[a[pos]] -- ;if (!cnt[a[pos]]) nw -- ; 
}void solve()
{int n, m;cin >> n >> m;sz = pow(n, 2.0 / 3.0);bnum = ceil((double)n / sz);for (int i = 1; i <= bnum; i ++ ) for (int j = (i - 1) * sz + 1; j <= i * sz; j ++ )belong[j] = i;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 0; i < m; i ++ ){char c; cin >> c;if (c == 'Q'){int l, r; cin >> l >> r;q[ ++ cnt1].l = l;q[cnt1].r = r;q[cnt1].t = cnt2;q[cnt1].id = cnt1;}else if (c == 'R'){int pos, x; cin >> pos >> x;md[ ++ cnt2].pos = pos;md[cnt2].color = x;}}sort(q + 1, q + cnt1 + 1, cmp);int l = 1, r = 0, time = 0;for (int i = 1; i <= cnt1; i ++ ){int ql = q[i].l, qr = q[i].r, qt = q[i].t;while (l < ql) del(l ++ );while (l > ql) add( -- l);while (r > qr) del(r -- );while (r < qr) add( ++ r);while (time < qt){time ++ ;if (ql <= md[time].pos && md[time].pos <= qr) del(md[time].pos);swap(a[md[time].pos], md[time].color);if (ql <= md[time].pos && md[time].pos <= qr) add(md[time].pos);}while (time > qt){if (ql <= md[time].pos && md[time].pos <= qr) del(md[time].pos);swap(a[md[time].pos], md[time].color);if (ql <= md[time].pos && md[time].pos <= qr) add(md[time].pos);time -- ;}ans[q[i].id] = nw;}for (int i = 1; i <= cnt1; i ++ ) cout << ans[i] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}