带修莫队

简述

在学习带修莫队之前，请务必学会普通莫队。

带修莫队即为：

普通莫队是不能修改的，我们可以强行让它可以修改，加上一维时间维,表示这次操作的时间。

时间维表示经历的修改次数。

即把询问$[l,r]$变成$[l,r,time]$,那么因为多了一维，我们对应的操作也会增加

  • $[l-1,r,time]$
  • $[l+1,r,time]$
  • $[l,r-1,time]$
  • $[l,r+1,time]$
  • $[l,r,time-1]$
  • $[l,r,time+1]$
    这样的转移时间复杂度仍然是$O(1)$,对应的，我们的排序规则就需要进行变动。
    这样总的时间复杂度是$O(n^{\frac{5}{3}})$ 。

排序规则

这一次的排序方式是以$n^{\frac{2}{3}}$为一块，分成了$n^{\frac{1}{3}}$ 块：

  • 第一关键词是左端点所在块
  • 第二关键词是右端点所在块
  • 第三关键词是时间

时间维

就跟普通莫队差不多，差多少时间，就补多少时间，可以把$[l,r,time]$画成一个三维空间去理解。

例题

P1903 数颜色 / 维护队列
题目大意：给你一个序列，M 个操作，有两种操作：

  1. 修改序列上某一位的数字
  2. 询问区间 $[l,r]$ 中数字的种类数（多个相同的数字只算一个）
    可以发现，如果没有操作1，我们可以用普通莫队直接秒了，但是现在增加了一个单点修改的操作，所以我们需要使用带修莫队。

做法

对于查询，就是很简单的维护一个桶，不过多赘述。
接下来考虑修改，我们把一个点修改成另一个颜色，我们需要考虑这个点是否在我当前区间里面，如果不在就不需要修改。如果在的话，增加一下修改之后的点，删除掉修改前的点。

无论是否在当前区间，都需要swap，因为修改后的下一次操作一定相反。
即为 (修改该位置->还原该位置->修改该位置->….)

警示

这里swap的时候一定要用引用，拷贝的话是没用的,这个点卡了我一下午!!!!。
因为这里的意义是，交换过后，我之后可以再修改回来。

1
2
3
4
5
6
7
8
9
auto time = [&](int x,int l,int r) -> void {
           int &w = modify[x][1], id = modify[x][0];
           if(l <= id && id <= r)
           {
               sub(v[id]);
               add(w);
           }
           swap(v[id],w);//注意这里是引用，而不是拷贝，拷贝的话swap没有意义，这个点卡了我一下午
       };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(e) push_back(e)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define endl '\n'

using namespace std;
using i64 = long long;
using PII = pair<int,int>;
const int INF = 0x3f3f3f3f;


int main()
{
    int n,m;const int N = 1e6+10;
    cin >> n >> m;
    int kn = pow(n,0.6666);
    vector<int> v(N),K(N),cnt(N);
    vector<array<int,4> > query = {{}};//l,r,time,id
    vector<array<int,2> > modify = {{}};//下标,值
    for(int i=1;i<=n;++i) cin >> v[i],K[i] = (i-1)/kn + 1;
    for(int i=1;i<=m;++i)
    {
        string s;int x,y;cin >> s >> x >> y;
        if(s == "Q") query.push_back({x,y,(int)modify.size() - 1,(int)query.size()});
        else modify.push_back({x,y});
    }
    sort(query.begin() + 1,query.end(),[&](auto x,auto y){
        if(K[x[0]] != K[y[0]]) return x[0] < y[0];
        if(K[x[1]] != K[y[1]]) return x[1] < y[1];
        return x[3] < y[3];
    });
    vector<int> ans(query.size());
    int l = 1,r = 0,val = 0,t = 0;//t为累计修改次数
    for(int i=1;i<query.size(); ++ i)
    {
        auto &e = query[i];
        int ql = e[0],qr = e[1],qt = e[2],id = e[3];
        auto add = [&](int x) -> void {
            if(!cnt[x]) val += 1;
            cnt[x] ++ ;
        };
        auto sub = [&](int x) -> void {
            cnt[x] -- ;
            if(!cnt[x]) val -=1;
        };
        auto time = [&](int x,int l,int r) -> void {
            int &w = modify[x][1], id = modify[x][0];
            if(l <= id && id <= r)
            {
                sub(v[id]);
                add(w);
            }
            swap(v[id],w);//注意这里是引用，而不是拷贝，拷贝的话swap没有意义，这个点卡了我一下午
        };
        while (l > ql) add(v[--l]);
        while (r < qr) add(v[++r]);
        while (l < ql) sub(v[l++]);
        while (r > qr) sub(v[r--]);
        while (t < qt) t+=1 ,time(t, ql, qr);
        while (t > qt) time(t, ql, qr),t-=1;
        ans[id] = val;
    }
    for(int i=1;i<ans.size();++i) cout << ans[i] << endl;
    return 0;
}

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int main()
{
    int n,m;
    cin >> n >> m;
    int kn = pow(n,0.6666);
    vector<int> v(n + 1),K(n + 1);
    vector<array<int,4>> query = {{}};//l,r,time,id
    vector<array<int,2>> modify = {{}};//下标，值
    for(int i=1;i<=n;++i) cin >> v[i],K[i] = (i-1)/kn + 1;
    for(int i=1;i<=m;++i)
    {
        string s;int x,y;cin >> s >> x >> y;
        if(s == "Q") query.emplace_back(x,y,(int)modify.size() - 1,(int)query.size());
        else modify.emplace_back(x,y);
    }
    sort(query.begin() + 1,query.end(),[&](auto x,auto y){
        if(K[x[0]] != K[y[0]]) return x[0] < y[0];
        if(K[x[1]] != K[y[1]]) return x[1] < y[1];
        return x[3] < y[3];
    });
    int l = 1,r = 0,val = 0,t = 0;//t为累计修改次数
    for(int i=1;i<query.size(); ++ i)
    {
        auto &e = query[i];
        int ql = e[0],qr = e[1],qt = e[2],id = e[3];
        auto add = [&](int x) -> void {

        };
        auto sub = [&](int x) -> void {

        };
        auto time = [&](int x,int l,int r) -> void {
            int &w = modify[x][1], id = modify[x][0];//记得引用
            if(l <= id && id <= r)
            {
                sub(v[id]);
                add(w);
            }
            swap(v[id],w);
        };
        while (l > ql) add(w[--l]);
        while (r < qr) add(w[++r]);
        while (l < ql) sub(w[l++]);
        while (r > qr) sub(w[r--]);
        while (t < qt) time(++t, ql, qr);
        while (t > qt) time(t--, ql, qr);
        ans[id] = val;
    }
    for(int i=1;i<=ans.size();++i) cout << ans[i] << endl;
    return 0;
}
算法
#algorithm #杂项
带修莫队
http://pikachuxpf.github.io/posts/84c587e8/
作者
Pikachu_fpx
发布于
2024年1月20日
许可协议