UVa12345 Dynamic len(set(a[L:R]))

@[TOC](UVa12345 Dynamic len(set(a[L:R])))

题目链接

  UVA - 12345 Dynamic len(set(a[L:R]))

题意

  有编号从 0 到 n−1 的 n 个数，有两种操作：

• Q L R 询问编号 L 到编号 R−1 的数中有多少个不同的数字。
• M X Y 将编号为 X 的数字改为 Y。

  你的任务就是要完成这一系列操作。

输入格式

  输入仅包含一组数据，其中第一行为两个整数 n 和 m（1≤n,m≤50 000），第二行为列表 a 的各个元素值。每个元素都是 $1$~$10^6$ 之间的整数。以下 m 行的格式有两种情况：M x y（$1\le y\le 10^6$）表示执行赋值 a[x]=y；Q x y 表示输出 len(set(a[x:y])) 的值。输入保证不会出现访问越界的情况。

输出格式

  对于每条 Q 指令，输出结果。

分析

  本题可以用分块来做，很多题解说了可以用带修改莫队算法，等掌握了莫队算法再补上来。

分块

  要统计区间 [L,R) 中有多少个不同的数，可以分析一下每个数它前面相同的数在什么位置，可以只统计前面相同的数位置小于 L 的那些数（前面不存在相同数的可以按前面相同的数位置为 -1 处理，自然小于 L)。

  用数组 p[n] 记录每个位置的前一个相同数的位置，初始输入各个元素值时可以初始化 p 数据。取分块大小为 $s=\sqrt{n}$，为了后续高效查询，需要给每个块再用一个数组 pre[s] 保存数组 p[n] 中对应块的排序结果。这样在查询时，首尾的块直接在数组 p[n] 中遍历统计，中间哪些块直接对其数组 pre 二分查找小于 L 的有几个就能得到答案，单次查询的时间复杂度为$O(\sqrt{n}\log \sqrt{n})$。

  为了满足查询的要求，对每次修改 $a[x]=y$ 的操作，需要更新数组 p 并对相应受影响的分块更新其数组 pre 的排序。不妨再加一个数组 nxt[n] 记录每个位置的后一个相同数的位置（位置 x 不存在后一个相同数时可赋值 next[x] = n）。

  每次修改 $a[x]=y$ 的操作受影响的块最多有三个：旧 nxt[x] 所在的块，因为旧 nxt[x] < n 时会更新 p[ nxt[x] ] = 旧 p[x]；x 所在的块，因为会更新 p[x]；新 nxt[x] 所在的块，因为新 nxt[x] < n 时会更新 p[ nxt[x] ] = x。

  旧 nxt[x] 的更新容易，难点是更新 p[x] 和新 nxt[x]。考虑对每个块，再维护一个值索引数组 b[s]，用于修改 $a[x]=y$ 操作时快速找出位置 x 处的前一个 y 的位置和后一个 y 的位置。举例第一个块（假设 s = 10）如下：

  即值索引数组 b 的排序规则是：若索引 i 对应的值 v[i] 小于 索引 j 对应的值 v[j] 即 v[i] < v[j]， 则 i 排在 j 前面；若 v[i] = v[j]，则 i < j 时 i 排在 j 前面。有了值索引数组 b，修改 $a[x]=y$ 操作时找位置 x 处的前一个 y 的位置和后一个 y 的位置可以用二分查找。

  对于修改 $a[x]=y$ 操作，找位置 x 处的前一个 y 的位置和后一个 y 的位置的时间复杂度都是 $O(\sqrt{n}\log \sqrt{n})$；维护位置 x 所在块的值索引数组 b 排序和维护受影响的最多三个块的 pre 数组排序都可以用插入排序的思想，时间复杂度时 $O(\log \sqrt{n}+\sqrt{n})=O(\sqrt{n})$。因此修改操作整体的时间复杂度是 $O(\sqrt{n}\log \sqrt{n})$。

  输入数据时需要初始化数组 p、nxt、pre、b 并对每个分块的 pre、b 数组排序，初始化处理的时间复杂度为 $O(n\log \sqrt{n})$，单次修改或查询的时间复杂度是 $O(\sqrt{n}\log \sqrt{n})$，修改和查询的总次数是 m，因此整个算法的时间复杂度是 $O((n+m\sqrt{n})\log \sqrt{n})$。

  最后，说一个工程实践上的点，c++ STL 的 lower_bound、upper_bound 方法可以传一个自定义比较函数 Compare comp，但是要注意 lower_bound 和 upper_bound 用的比较函数的参数顺序不一样。lower_bound 调用的是 comp(*it, val)， 而 upper_bound 调用的是 comp(val, *it)。

带修改莫队算法

  后面补。

AC 代码

分块

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define M 1000010
#define N 50010
#define S 224
int a[N], b[N], p[N], q[M], nxt[N], pre[N], m, n;

bool cmp(int i, int j) {
    return a[i] < a[j] || (a[i] == a[j] && i < j);
}

bool cmp2(int i, int v) {
    return a[i] < v;
}

bool cmp3(int v, int i) {
    return v < a[i];
}

int get_pre(int x, int y) {
    if (x % S) {
        int h = x - x%S, t = min(h+S, n), r = lower_bound(b+h, b+t, y, cmp2) - b;
        if (r < t && b[r] < x && a[b[r]] == y) {
            while (++r < t && b[r] < x && a[b[r]] == y);
            return b[r-1];
        }
        x = h;
    }
    for (int i = x; i >= S; i -= S) {
        int r = upper_bound(b+i-S, b+i, y, cmp3) - b - 1;
        if (b[r] < x && a[b[r]] == y) return b[r];
    }
    return -1;
}

int get_next(int x, int y) {
    if (++x % S) {
        int h = x - x%S, t = min(h+S, n), r = upper_bound(b+h, b+t, y, cmp3) - b - 1;
        if (b[r] >= x && a[b[r]] == y) {
            while (--r >= h && b[r] >= x && a[b[r]] == y);
            return b[r+1];
        }
        x = t;
    }
    for (int i=x; i<n; i+=S) {
        int t = min(i+S, n), r = lower_bound(b+i, b+t, y, cmp2) - b;
        if (r < t && a[b[r]] == y) return b[r];
    }
    return n;
}

void update_pre(int x, int u) {
    int h = x - x%S, t = min(h+S, n);
    if (p[x] > u) {
        int i = lower_bound(pre+h, pre+t, p[x]) - pre;
        while (i > h && pre[i-1] > u) pre[i] = pre[i-1], --i;
        pre[i] = p[x] = u;
    } else {
        int i = upper_bound(pre+h, pre+t, p[x]) - pre - 1;
        while (i+1 < t && pre[i+1] < u) pre[i] = pre[i+1], ++i;
        pre[i] = p[x] = u;
    }
}

void modify(int x, int y) {
    if (a[x] == y) return;
    int u = get_pre(x, y), v = get_next(x, y), h = x - x%S, t = min(h+S, n);
    int i = lower_bound(b+h, b+t, x, cmp) - b;
    if (a[x] < y) {
        while (i+1 < t && (a[b[i+1]] < y || (a[b[i+1]] == y && b[i+1] < x))) b[i] = b[i+1], ++i;
        b[i] = x;
    } else {
        while (i > h && (a[b[i-1]] > y || (a[b[i-1]] == y && b[i-1] > x))) b[i] = b[i-1], --i;
        b[i] = x;
    }
    if (p[x] >= 0) nxt[p[x]] = nxt[x];
    if (nxt[x] < n) update_pre(nxt[x], p[x]);
    if (u >= 0) nxt[u] = x;
    if (v < n) update_pre(v, x);
    update_pre(x, u); nxt[x] = v; a[x] = y;
}

void query(int x, int y) {
    int cnt = 0, l = x, r = y-1;
    for (int i = min(l-l%S+S, min(y, n)); l<i; ++l) if (p[l] < x) ++cnt;
    for (int i = max(r-r%S, l); r >= i; --r) if (p[r] < x) ++cnt;
    for (int i=l; i<r; i+=S) cnt += lower_bound(pre+i, pre+i+S, x) - pre - i;
    cout << cnt << endl;
}

void solve() {
    cin >> n >> m; memset(q, -1, sizeof(q));
    for (int i=0; i<n; ++i) {
        cin >> a[i]; b[i] = i;
        if (q[a[i]] >= 0) nxt[q[a[i]]] = i;
        pre[i] = p[i] = q[a[i]]; nxt[i] = n; q[a[i]] = i;
        if (i > 0 && i%S == 0) sort(pre+i-S, pre+i), sort(b+i-S, b+i, cmp);
    }
    int h = n - (n%S ? n%S : S);
    sort(pre+h, pre+n); sort(b+h, b+n, cmp);
    while (m--) {
        char ch; int x, y; cin >> ch >> x >> y;
        ch == 'M' ? modify(x, y) : query(x, y);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

带修改莫队算法

  后面补。