带修莫队+值域分块

sccc_ · 2025-08-07 14:27:18 · 个人记录

带修莫队

初始化

在 q 数组里记录 $(l,r,k)，分别为每次查询的左边界，右边界与时间戳。

在 M 数组里记录 (pos,val)，分别为每次修改操作的下标与值。

while (t--) {
  char c;
  cin >> c;
  if (c == 'Q') {
    ++cnt_q;
    cin >> q[cnt_q].l >> q[cnt_q].r;
    q[cnt_q].t = cnt_r;
    q[cnt_q].id = cnt_q;
  } else {
    ++cnt_r;
    cin >> M[cnt_r].pos >> M[cnt_r].val;
  }
}

修改与查询

我们需要同时进行查询与修改操作。

先进行普通的查询操作。

接着，当当前时间 < q_i 的时间戳时，证明我们需要修改从当前时间到 q_i 的时间戳的操作。当当前时间 > q_i 的时间戳时，证明我们需要修改回来过多修改的操作。

int l = 1, r = 0, t = 0;
for (int i = 1; i <= cnt_q; i++) {
  while (l < q[i].l)
    SUB(a[l++]);
  while (l > q[i].l)
    ADD(a[--l]);
  while (r < q[i].r)
    ADD(a[++r]);
  while (r > q[i].r)
    SUB(a[r--]);
  while (t < q[i].t) 
    modify(i, ++t);
  while (t > q[i].t)
    modify(i, t--);
  ans[q[i].id] = tot;
}

修改

直接修改值，最后 swap 一下，方便下次修改回来。

void modify(int x, int t) {
    if (M[t].pos >= q[x].l && M[t].pos <= q[x].r) {
        SUB(a[M[t].pos]);
        ADD(M[t].val);
    }
    swap(a[M[t].pos], M[t].val);
}

P1903 [国家集训队] 数颜色 / 维护队列

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, t, tot, a[N], b[N], cnt[N * 10], pos[N], ans[N]; 

struct Query {
    int l, r, id, t;
} q[N];

struct MODIFY {
    int pos, val;
} M[N];

void ADD(int x) {
    (++cnt[x] == 1) && (tot++);
}

void SUB(int x) {
    (--cnt[x] == 0) && (tot--);
}

bool cmp(Query a, Query b) {
    if (pos[a.l] != pos[b.l]) {
        return a.l < b.l;
    }
    if (pos[a.r] != pos[b.r]) {
        return a.r < b.r;
    }
    return a.t < b.t;
}

void modify(int x, int t) {
    if (M[t].pos >= q[x].l && M[t].pos <= q[x].r) {
        SUB(a[M[t].pos]);
        ADD(M[t].val);
    }
    swap(a[M[t].pos], M[t].val);
}

signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n >> t;
    int len = int(pow(n, 2.0 / 3.0));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[i] = (i - 1) / len + 1;
    }
    int cnt_r = 0, cnt_q = 0;
    while (t--) {
        char c;
        cin >> c;
        if (c == 'Q') {
            ++cnt_q;
            cin >> q[cnt_q].l >> q[cnt_q].r;
            q[cnt_q].t = cnt_r;
            q[cnt_q].id = cnt_q;
        } else {
            ++cnt_r;
            cin >> M[cnt_r].pos >> M[cnt_r].val;
        }
    }
    sort (q + 1, q + 1 + cnt_q, cmp);
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= cnt_q; i++) {
        while (l < q[i].l)
            SUB(a[l++]);
        while (l > q[i].l)
            ADD(a[--l]);
        while (r < q[i].r)
            ADD(a[++r]);
        while (r > q[i].r)
            SUB(a[r--]);
        while (t < q[i].t) 
            modify(i, ++t);
        while (t > q[i].t)
            modify(i, t--);
        ans[q[i].id] = tot;
    }
    for (int i = 1; i <= cnt_q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

CF940F Machine Learning

数字过大，先离散化。

对于求出现次数的 mex，我们在修改完后暴力求就可以了。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, t, tot, a[N], b[N], cnt[N], pos[N], ans[N], sum[N], idx;

struct Query {
    int l, r, id, t;
} q[N];

struct MODIFY {
    int pos, val;
} M[N];

void ADD(int x) {
    sum[cnt[x]]--, cnt[x]++, sum[cnt[x]]++;
}

void SUB(int x) {
    sum[cnt[x]]--, cnt[x]--, sum[cnt[x]]++;
}

bool cmp(Query a, Query b) {
    if (pos[a.l] != pos[b.l]) {
        return a.l < b.l;
    }
    if (pos[a.r] != pos[b.r]) {
        return a.r < b.r;
    }
    return a.t < b.t;
}

void modify(int x, int t) {
    if (M[t].pos >= q[x].l && M[t].pos <= q[x].r) {
        SUB(a[M[t].pos]);
        ADD(M[t].val);
    }
    swap(a[M[t].pos], M[t].val);
}

signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n >> t;
    int len = int(pow(n, 2.0 / 3.0));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[++idx] = a[i];
        pos[i] = (i - 1) / len + 1;
    }
    int cnt_r = 0, cnt_q = 0;
    while (t--) {
        int op;
        cin >> op;
        if (op == 1) {
            ++cnt_q;
            cin >> q[cnt_q].l >> q[cnt_q].r;
            q[cnt_q].t = cnt_r;
            q[cnt_q].id = cnt_q;
        } else {
            ++cnt_r;
            cin >> M[cnt_r].pos >> M[cnt_r].val;
            b[++idx] = M[cnt_r].val;
        }
    }
    sort (b + 1, b + 1 + idx);
    int length = unique(b + 1, b + 1 + idx) - (b + 1);
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b + 1, b + 1 + length, a[i]) - b;
        a[i] = x;
    }
    for (int i = 1; i <= cnt_r; i++) {
        int x = lower_bound(b + 1, b + 1 + length, M[i].val) - b;
        M[i].val = x;
    }
    sort (q + 1, q + 1 + cnt_q, cmp);
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= cnt_q; i++) {
        while (l < q[i].l)
            SUB(a[l++]);
        while (l > q[i].l)
            ADD(a[--l]);
        while (r < q[i].r)
            ADD(a[++r]);
        while (r > q[i].r)
            SUB(a[r--]);
        while (t < q[i].t)
            modify(i, ++t);
        while (t > q[i].t)
            modify(i, t--);
        int tmp = 1;
        while (sum[tmp])
            tmp++;
        ans[q[i].id] = tmp;
    }
    for (int i = 1; i <= cnt_q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}