P4119 [Ynoi2018] 未来日记

有一个长为 \(n\) 的序列 \(a\)，有 \(m\) 次操作：

• 把区间 \([l,r]\) 内所有的 \(x\) 变成 \(y\)。
• 查询区间 \([l,r]\) 内第 \(k\) 小值。

\(1 \leq n,m,a_i \leq 10^5\)，时限 \(1.00\text{s}\)，空限 \(512\text{MB}\)。

sol

最初分块。

难度评分：\(8.5\)。

下面先假定 \(V\) 为值域。

先看查询区间第 \(k\) 大。

可以维护每个数在区间内出现了多少次。

这个可以用一个二维的 \(sum\) 数组维护：\(sum[i][j]\) 表示前 \(i\) 块中 \(j\) 出现的次数。

这样区间内一个数 \(x\) 出现的次数就是中间整块 \(sum\)的两个前缀和相减，再加上两边散块的出现次数，散块的出现个数可暴力。

然而这样时间复杂度为 \(\mathcal O(nV)\)，无法通过。

考虑优化。

考虑再加上值域分块。

首先预处理 \(cnt1[i][j]\) 表示前 \(i\) 块中在第 \(j\) 块值域的数出现次数，\(cnt2[i][j]\) 表示前 \(i\) 块中 \(j\) 出现次数。

预处理 \(\mathcal{O}(n \sqrt{n})\)。

这样查询的时候，整块用 \(cnt1\) 和 \(cnt2\) 处理，散块用桶维护一下即可，单次时间复杂度为 \(\mathcal{O}(\sqrt{n})\)。

再看修改。

散块暴力即可。

再考虑并查集，记 \(id[x][i]\) 为第 \(x\) 块中第一个值为 \(i\) 的数的下标。

同时其逆也记下，记 \(rid[x][i]\) 表示第 \(x\) 块中下标 \(i\) 对应的值。

再用 \(pos_i\) 记录每一位的 \(id\)。（\(i\) 是序列上位置）

如果要还原序列，只需让 \(a_i=rid[bl_i][pos_i]\)。

再分情况讨论。

• 块内无 \(x\)，跳过。
• 块内有 \(x\) 无 \(y\)，可将 \(id[bl][y]=id[bl][x]\)，同时 \(rid[bl][id[bl][x]]=y\)，记得 \(id[bl][x]=0\)。
• 块内有 \(x,y\)， 考虑此时块内权值种类少 \(1\)， 而权值种类总共不超过 \(n+m\)， 均摊后暴力重构复杂度总和为 \(\mathcal O((n+m)\sqrt{n})\)， 暴力重构即可，对于两个 \(cnt\) 数组的更新，可以先将其差分为每块的，最后再合并，一次 \(O(\sqrt{n})\)。

总时间和空间复杂度为 \(\mathcal O((n+m)\sqrt {n})\)。

总结：分块套分块，加套路并查集。

\(\text{5.97s / 202.38MB / 6.29KB C++98 O2}\)。

#include <cstdio>
#include <cmath>
#include <algorithm>

namespace Fread
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S, *T;
    inline char getchar()
    {
        if (S == T)
        {
            T = (S = buf) + fread(buf, 1, SIZE, stdin);
            if (S == T)
                return '\n';
        }
        return *S++;
    }
}
namespace Fwrite
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S = buf, *T = buf + SIZE;
    inline void flush()
    {
        fwrite(buf, 1, S - buf, stdout);
        S = buf;
    }
    inline void putchar(char c)
    {
        *S++ = c;
        if (S == T)
            flush();
    }
    struct NTR
    {
        ~NTR()
        {
            flush();
        }
    } ztr;
}

#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

const int N = 1e5 + 7, SQ = 620;

int n, m, a[N], len, bl[N], L[N], R[N], sum1[SQ], sum2[N];

int id[SQ][N], rid[SQ][N], pos[N];

int cnt1[SQ][SQ], cnt2[SQ][N];

inline void build(int x)
{
    int tot = 0;
    for (int i = 1; i <= len; ++i)
        id[x][rid[x][i]] = 0;
    for (int i = L[x]; i <= R[x]; ++i)
        if (!id[x][a[i]])
        {
            id[x][a[i]] = ++tot;
            rid[x][tot] = a[i];
        }
    for (int i = L[x]; i <= R[x]; ++i)
        pos[i] = id[x][a[i]];
}

inline void rest(int x)
{
    for (int i = L[x]; i <= R[x]; ++i)
        a[i] = rid[x][pos[i]];
}

inline void cg(int l, int r, int x, int y)
{
    for (int i = l; i <= r; ++i)
        if (a[i] == x)
        {
            --cnt1[bl[l]][bl[x]], ++cnt1[bl[l]][bl[y]];
            --cnt2[bl[l]][x], ++cnt2[bl[l]][y];
            a[i] = y;
        }
}

inline void change(int i, int x, int y)
{
    id[i][y] = id[i][x];
    rid[i][id[i][x]] = y;
    id[i][x] = 0;
}

inline void modify(int l, int r, int x, int y)
{
    if (x == y || cnt2[bl[r]][x] - cnt2[bl[l] - 1][x] == 0)
        return;
    for (int i = bl[n]; i >= bl[l]; --i)
    {
        cnt2[i][x] -= cnt2[i - 1][x];
        cnt2[i][y] -= cnt2[i - 1][y];
        cnt1[i][bl[x]] -= cnt1[i - 1][bl[x]];
        cnt1[i][bl[y]] -= cnt1[i - 1][bl[y]];
    }
    if (bl[l] == bl[r])
    {
        rest(bl[l]), cg(l, r, x, y);
        build(bl[l]);
        for (int i = bl[l]; i <= bl[n]; ++i)
        {
            cnt2[i][x] += cnt2[i - 1][x];
            cnt2[i][y] += cnt2[i - 1][y];
            cnt1[i][bl[x]] += cnt1[i - 1][bl[x]];
            cnt1[i][bl[y]] += cnt1[i - 1][bl[y]];
        }
        return;
    }
    rest(bl[l]), rest(bl[r]);
    cg(l, R[bl[l]], x, y), cg(L[bl[r]], r, x, y);
    build(bl[l]), build(bl[r]);
    for (int i = bl[l] + 1; i < bl[r]; ++i)
    {
        if (!cnt2[i][x])
            continue;
        if (cnt2[i][y])
        {
            rest(i), cg(L[i], R[i], x, y);
            build(i);
        }
        else
        {
            cnt1[i][bl[y]] += cnt2[i][x];
            cnt1[i][bl[x]] -= cnt2[i][x];
            cnt2[i][y] = cnt2[i][x];
            cnt2[i][x] = 0;
            change(i, x, y);
        }
    }
    for (int i = bl[l]; i <= bl[n]; ++i)
    {
        cnt2[i][x] += cnt2[i - 1][x];
        cnt2[i][y] += cnt2[i - 1][y];
        cnt1[i][bl[x]] += cnt1[i - 1][bl[x]];
        cnt1[i][bl[y]] += cnt1[i - 1][bl[y]];
    }
}

inline int kth(int l, int r, int k)
{
    int sum = 0;
    if (bl[l] == bl[r])
    {
        rest(bl[l]);
        for (int i = l; i <= r; ++i)
            sum2[i] = a[i];
        std::nth_element(sum2 + l, sum2 + l + k - 1, sum2 + r + 1);
        int ans = sum2[l + k - 1];
        for (int i = l; i <= r; ++i)
            sum2[i] = 0;
        return ans;
    }
    rest(bl[l]), rest(bl[r]);
    for (int i = l; i <= R[bl[l]]; ++i)
    {
        ++sum1[bl[a[i]]];
        ++sum2[a[i]];
    }
    for (int i = L[bl[r]]; i <= r; ++i)
    {
        ++sum1[bl[a[i]]];
        ++sum2[a[i]];
    }
    for (int i = 1; i <= (N - 1) / len + 1; ++i)
        if (sum + sum1[i] + cnt1[bl[r] - 1][i] - cnt1[bl[l]][i] >= k)
        {
            for (int j = (i - 1) * len + 1; j <= i * len; ++j)
                if (sum + sum2[j] + cnt2[bl[r] - 1][j] - cnt2[bl[l]][j] >= k)
                {
                    for (int i = l; i <= R[bl[l]]; ++i)
                    {
                        --sum1[bl[a[i]]];
                        --sum2[a[i]];
                    }
                    for (int i = L[bl[r]]; i <= r; ++i)
                    {
                        --sum1[bl[a[i]]];
                        --sum2[a[i]] = 0;
                    }
                    return j;
                }
                else
                    sum += sum2[j] + cnt2[bl[r] - 1][j] - cnt2[bl[l]][j];
        }
        else
            sum += sum1[i] + cnt1[bl[r] - 1][i] - cnt1[bl[l]][i];
}

int main()
{
    n = read(), m = read();
    len = sqrt(n * 8 / 5);
    for (int i = 1; i < N; ++i)
        bl[i] = (i - 1) / len + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= bl[n]; ++i)
        L[i] = (i - 1) * len + 1, R[i] = i * len;
    R[bl[n]] = n;
    for (int i = 1; i <= bl[n]; ++i)
        build(i);
    for (int x = 1; x <= bl[n]; ++x)
    {
        for (int i = 1; i <= bl[N - 1]; ++i)
            cnt1[x][i] = cnt1[x - 1][i];
        for (int i = 1; i < N; ++i)
            cnt2[x][i] = cnt2[x - 1][i];
        for (int i = L[x]; i <= R[x]; ++i)
            ++cnt1[x][bl[a[i]]], ++cnt2[x][a[i]];
    }
    for (int i = 1, opt, l, r, x, y; i <= m; ++i)
    {
        opt = read(), l = read(), r = read();
        if (opt == 1)
        {
            x = read(), y = read();
            modify(l, r, x, y);
        }
        else
        {
            x = read();
            write(kth(l, r, x));
            putchar('\n');
        }
    }
    return 0;
}