#创作计划# 回滚莫队

userId_undefined

周子逸(地铁老六)（互关）

出道萌新时空双修者倔强青铜分支·分支解题者格式·格式排版员I/O·IO入门者

2026-01-02 15:16:31

发布于：广东

22阅读
0回复
0点赞

与一维数组值域处理方法的区别

一维数组做值域题时可能会出现删除复杂度过高或者添加复杂度过高的情况，有时对于大型样例会超时，这时候我们就需要用到回滚莫队

传统莫队算法中，我们通常维护一个值域数组（桶数组）cnt[]来统计每个值的出现次数，并通过add()和remove()两个函数来动态维护当前区间。然而，这种方法存在一个根本性问题：添加操作和删除操作的时间复杂度可能不对称。

以一维数组维护区间最大值为例：

// 传统方法 - 不对称的复杂度
int cnt[MAX_VAL], maxn = 0;

void add(int x) {
    cnt[x]++;
    if (x > maxn)
        maxn = x; // O(1)操作, 或者maxn = max(maxn, x);
}

void remove(int x) {
    cnt[x]--;
    if (cnt[x] == 0 && x == maxn) {
        // 需要重新扫描整个值域寻找新的最大值
        max = 0;
        for (int i = MAX_VAL; i >= 1; i--) {
            if (cnt[i] > 0) {
                maxn = i;
                break;
            }
        }
        // 最坏情况 O(MAX_VAL) 时间复杂度
    }
}

如上所示，添加操作是O(1)的，但删除操作在最坏情况下需要O(值域大小)的时间。这种不对称性在某些题目中会导致算法效率急剧下降。

回滚莫队正是为了解决这个问题而提出的。

回滚莫队通过以下策略解决不对称性问题：

基本策略

  • 只实现添加操作（或只实现删除操作，但通常实现添加更简单）
  • 不实现删除操作，当需要"删除"时，通过回滚到之前保存的状态
  • 将查询按块排序，保证右端点单调递增

现在看看完整的代码(维护最大值，代码AI声明)：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;
const int MAXV = 1000010;
const int BLOCK = 450;  // sqrt(MAXN)

int n, q;
int arr[MAXN];
int cnt[MAXV];
int max_val;  // 当前最大值
int block_size;

struct Query {
    int l, r, id;
    bool operator<(const Query &other) const {
        int block_a = l / block_size;
        int block_b = other.l / block_size;
        if (block_a != block_b) return block_a < block_b;
        return r < other.r;  // 同块内按右端点升序
    }
} queries[MAXN];

int ans[MAXN];

// 只实现添加操作
void add(int x) {
    cnt[x]++;
    if (x > max_val) max_val = x;
}

// 注意：没有remove函数！

void solve() {
    cin >> n >> q;
    block_size = sqrt(n);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }
    
    sort(queries, queries + q);
    
    int cur_r = -1, cur_l = 0;
    int last_block = -1;
    
    for (int i = 0; i < q; i++) {
        int L = queries[i].l, R = queries[i].r;
        int block_id = L / block_size;
        
        // 如果跳到了新的块
        if (block_id != last_block) {
            // 重置所有状态
            memset(cnt, 0, sizeof(cnt));
            max_val = 0;
            cur_l = (block_id + 1) * block_size;  // 新块的开始
            cur_r = cur_l - 1;
            last_block = block_id;
        }
        
        // 情况1：查询完全在块内，暴力计算
        if (R / block_size == block_id) {
            int temp_max = 0;
            int temp_cnt[MAXV] = {0};
            
            for (int j = L; j <= R; j++) {
                temp_cnt[arr[j]]++;
                temp_max = max(temp_max, arr[j]);
            }
            ans[queries[i].id] = temp_max;
            continue;
        }
        
        // 情况2：跨块查询
        // 2.1 向右扩展右指针
        while (cur_r < R) {
            cur_r++;
            add(arr[cur_r]);
        }
        
        // 2.2 保存状态
        int backup_max = max_val;
        int backup_cnt[MAXV];
        memcpy(backup_cnt, cnt, sizeof(cnt));
        
        // 2.3 临时向左扩展左指针
        int temp_l = cur_l;
        while (temp_l > L) {
            temp_l--;
            add(arr[temp_l]);
        }
        
        // 2.4 记录答案
        ans[queries[i].id] = max_val;
        
        // 2.5 回滚状态
        max_val = backup_max;
        memcpy(cnt, backup_cnt, sizeof(cnt));
    }
    // 输出答案
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
}

int main() {
    solve();
    return 0;
}

养成习惯，看完点赞！

userId_undefined
去预览
0/2000

全部评论 2

热门讨论