P2464

Walrus · 2024-01-26 16:24:59 · 题解

P2464

一道区间问题，看到 1\leq N,M \leq 10^5，考虑离线算法。

这里把带修莫队补上。

题意

有一排书架，编号为 1 到 N，上面放有 N 本书，依次编码为 a_1 \sim a_N，支持两种操作。

• 把书架上编号为 A 上的书的编码改为 P。
• 询问 l\sim r 的区间内有多少本书的编号为 K。

做法

显然是一个可支持修改的数据结构，又是离线算法，理应想到带修莫队。

又由于 1\leq a_i\leq 2^{31}-1，所以应当离散化。这里介绍一种比较便捷且快捷的方法。

先考虑哪些东西需要离散化。

• 查询操作的值。
• 修改操作的编码和值。

用 map 离散化就不用我多说了，这里提一下预处理。

当我们为每一个值赋上了一个对应的编号时，我们可以直接将这个值改为为其赋的编号，就像这样。

for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    if(!mp[a[i]])
        mp[a[i]] = ++tot;
    a[i] = mp[a[i]];
}

这样做有什么好处呢？

• 避免了在莫队进行 add 和 del 操作时多次使用 map 查询。
• 避免了多次在一些东西前加 map，减少犯错的可能性。

带修莫队的好处还有一点：

• 在进行 add 和 del 操作时不需要一直统计答案，只需要在循环结束后直接取出。

Code

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

const int N = 1e5 + 5;
const int M = 1e6 + 5;

int a[N], ans[N], c[M << 1], cnt, n, m, k, len, l, r, val;
int qcnt, rcnt;
char op;

struct node {
    int l, r, val, id, t;
    #define l(p) t[p].l
    #define r(p) t[p].r
    #define id(p) t[p].id
    #define val(p) t[p].val
    #define t(p) t[p].t

    bool operator < (const node &a) const {
        if(l / len != a.l / len)
            return l / len > a.l / len;
        else if(r / len != a.r / len)
            return r / len > a.r / len;
        else
            return t > a.t;
    }
} t[N];

struct time {
    int p, x;
    #define p(i) R[i].p
    #define x(i) R[i].x
} R[N];

unordered_map<int, int> mp;
int tot;

void add(int x, int V) {
    ++c[x];
}

void del(int x, int V) {
    --c[x];
}

void update(int x, int val) {
    if(l <= p(x) && p(x) <= r)
        add(x(x), 1), del(a[p(x)], 1);
    swap(x(x), a[p(x)]);
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        if(!mp[a[i]])
            mp[a[i]] = ++tot;
        a[i] = mp[a[i]];
    }


    len = pow(n, 2.0 / 3);//带修莫队的块长一般以它为标准

    for(int i = 1; i <= m; ++i) {
        cin >> op >> l >> r;
        if(op == 'Q')  {
            cin >> val;
            if(!mp[val])
                mp[val] = ++tot;
            val = mp[val];
            t[++qcnt] = {l, r, val, qcnt, rcnt};
        }
        else {
            if(!mp[r])
                mp[r] = ++tot;
            r = mp[r];
            R[++rcnt] = {l, r};
        }
    }

    sort(t + 1, t + 1 + qcnt);

    l = 1, r = 0;

    for(int i = 1, last = 0; i <= qcnt; ++i) {
        while(l > l(i)) add(a[--l], 1);
        while(r < r(i)) add(a[++r], 1);
        while(l < l(i)) del(a[l++], 1);
        while(r > r(i)) del(a[r--], 1);
        while(last < t(i)) update(++last, 1);
        while(last > t(i)) update(last--, 1);
        ans[id(i)] = c[val(i)];
    } 
    for(int i = 1; i <= qcnt; ++i)
        cout << ans[i] << '\n';
    return 0;
}