P2464 题解

· · 题解

前言

题目传送门！

更好的阅读体验？

题解做法并没有重复。

题解区大部分都是分块，唯一一篇莫队也没有离散化。（所以那篇题解带了个 O(\log n)，常数巨大）。

思路

先来一遍带修莫队板子。只有 add() 与 del() 不同，如下：

void add(int x) {cnt[x]++;}
void del(int x) {cnt[x]--;}

每次的答案就是 cnt_k。

把 cnt[] 换成 map <int , int> 即可获得 60 分（我的代码自带超大常数）。

此时就要离散化了。可能存在的数据有原本的 a_i 与每一次更新后的数 p。

将这两组数排序去重。然后将 a_i，更新用的 p，询问的 k，都离散化。

这样，cnt[] 就可以使用数组了，省下了 map 的时间。注意要开双倍空间。

sort(t + 1, t + curt + 1); //t[] 存储了所有 ai 与更新用的 p。具体可以看完整代码。
int tt = unique(t + 1, t + curt + 1) - t - 1; //去重
for (int i = 1; i <= n; i++) a[i] = lower_bound(t + 1, t + tt + 1, a[i]) - t; //对三个数组都离散化
for (int i = 1; i <= curAsk; i++) ask[i].k = lower_bound(t + 1, t + tt + 1, ask[i].k) - t;
for (int i = 1; i <= curUpd; i++) upd[i].k = lower_bound(t + 1, t + tt + 1, upd[i].k) - t;

时间复杂度 O(n^{\frac{5}{3}} + n \log n)。前面的是带修莫队正常的时间，后面是离散化的时间。

完整代码

貌似不需要什么注释？长得和板子好像，基本只有上面提到的地方改动了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define space putchar(' ')
#define endl putchar('\n')
using namespace std;
typedef long long LL;
typedef long double LD;
void fastio()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 }
int read()
{
    char op = getchar(); int x = 0, f = 1;
    while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();}
    while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar();
    return x * f;
}
void write(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
const int N = 1e5 + 5;
int len, a[N];
struct Ask {int l, r, k; int t, id;} ask[N]; int curAsk;
struct Upd {int id, k;} upd[N]; int curUpd;
bool cmp(Ask x, Ask y)
{
    if (x.l / len != y.l / len) return x.l / len < y.l / len;
    if (x.r / len != y.r / len) return x.r / len < y.r / len;
    return x.t < y.t;
}
int cnt[N << 1];
inline void add(int x) {cnt[x]++;}
inline void del(int x) {cnt[x]--;}
inline void update(int l, int r, int t)
{
    if (l <= upd[t].id && upd[t].id <= r) del(a[upd[t].id]), add(upd[t].k);
    swap(a[upd[t].id], upd[t].k);
}
int ans[N];
int t[N << 1], curt;
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read(), t[++curt] = a[i];
    len = pow(n, 2.0 / 3);
    for (int i = 1; i <= m; i++)
    {
        char op; cin >> op;
        if (op == 'C')
        {
            int x = read(), y = read();
            upd[++curUpd] = (Upd){x, y};
            t[++curt] = y;
        }
        else
        {
            int l = read(), r = read(), k = read();
            curAsk++, ask[curAsk] = (Ask){l, r, k, curUpd, curAsk};
        }
    }
    sort(t + 1, t + curt + 1);
    int tt = unique(t + 1, t + curt + 1) - t - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(t + 1, t + tt + 1, a[i]) - t;
    for (int i = 1; i <= curAsk; i++) ask[i].k = lower_bound(t + 1, t + tt + 1, ask[i].k) - t;
    for (int i = 1; i <= curUpd; i++) upd[i].k = lower_bound(t + 1, t + tt + 1, upd[i].k) - t;
    sort(ask + 1, ask + curAsk + 1, cmp);
    for (int i = 1, l = 1, r = 0, t = 0; i <= curAsk; i++)
    {
        while (l < ask[i].l) del(a[l++]);
        while (l > ask[i].l) add(a[--l]);
        while (r < ask[i].r) add(a[++r]);
        while (r > ask[i].r) del(a[r--]);
        while (t < ask[i].t) update(ask[i].l, ask[i].r, ++t);
        while (t > ask[i].t) update(ask[i].l, ask[i].r, t--);
        ans[ask[i].id] = cnt[ask[i].k];
    }
    for (int i = 1; i <= curAsk; i++) write(ans[i]), endl;
    return 0;
}

希望能帮助到大家！