P3380 【模板】树套树

wtyqwq · 2020-06-07 14:02:47 · 题解

• P3380 【模板】树套树

• 解题思路：分块套值域分块。

  首先对下标进行分块。每块的长度为 \lfloor \sqrt{n} \rfloor。

  同时对值域进行分块。设有 (n+m) 个不同的数值，离散化之后，将值域分成 \sqrt{n+m} 个块。

  接下来，我们预处理两个表：

  仔细想一想，这样的话，在单点修改和查询的时候，我们就可以完美地实现暴力与暴力之间的平衡。

  具体每个操作的处理方式如下：

  • 修改操作：将下标为 p 的数修改为 v。

    令 v 所在的值域块的编号为 \text{pos}，按下标分一共有 \text{num} 个块，\text{BEL}(i) 表示第 i 个值所在值域块的编号, \text{bel}(i) 表示下标 i 所在下标块的编号，a_i 表示离散化之后的数列。

    对于第 i 个下标块（i\in [\text{bel}(p),\text{num}]），进行如下操作：

    ++C1[i][BEL[v]], ++C2[i][v], --C1[i][BEL[a[p]], --C2[i][a[p]];

    最后，别忘了更新 a 数组。

  • 查询排名操作：

    令查询区间为 [l, r]，查询 k 的排名（k 经过离散化），即比 k 小的数的数量 +1 的值。

    如果 \text{bel}(l) = \text{bel}(r)，我们直接暴力统计区间 [l, r] 内有几个数（离散化后）比 k 小即可。

    否则，边角暴力统计（和上面类似），中间部分靠我们维护的 \text{C1} 和 \text{C2} 数组快速累加：

    //中间快速累加部分代码：
    for (int i = 1; i < BEL[k]; ++i) ret += C1[bel[r] - 1][i] - C1[bel[l]][i];
    for (int i = L[BEL[k]]; i < k; ++i) ret += C2[bel[r] - 1][i] - C2[bel[l]][i]; //L(i)表示第i个值域块的左端点。

    最后返回 \text{ret+1} 即可。

  • 查询第 k 小操作：

    令查询区间为 [l, r]。和后面的前驱、后继操作，我们都需临时维护两个数组 \text{Cnt} 和 \text{cnt}。\text{Cnt}(i) 表示在查询区间的边角部分中，落在第 i 个值域块的数有多少个，\text{cnt}(i) 表示在查询区间的边角部分中，值恰好为 i 的数有多少个（经过离散化）。在求出返回答案，别忘了将其清零。

    void Add(int x, int y) {//统计     a[x...y] 中的信息
      for (int i = x; i <= y; ++i) ++Cnt[BEL[a[i]]], ++cnt[a[i]];
    }
    void Minus(int x, int y) {//恢复初始状态
      for (int i = x; i <= y; ++i) --Cnt[BEL[a[i]]], --cnt[a[i]];
    }

    有了 \text{C1},\text{C2},\text{Cnt},\text{cnt} 这四个数组，我们可以先确定答案在哪个值域块，再在那个值域块中求出精确的答案。这样，复杂度完美地停留在 \sqrt{n+m}。

    查询第 k 小代码：

    inline int Get(int x, int y, int k) {//返回 a[x...y] 中第 k+1 大的值。
        int P1 = bel[x], P2 = bel[y], A = 1, B, cur = 0;//A表示答案在哪个值域块，B表示答案具体的值。先确定A，后求B。
        if (P1 == P2) {//查询区间在同一个块中。
            Add(x, y);
            for (; k >= Cnt[A]; ++A) k -= Cnt[A];
            for (B = L[A]; k >= cnt[B]; ++B) k -= cnt[B];
            Minus(x, y);
            return val[B];
        }
        Add(x, r[P1]), Add(l[P2], y);//求出 Cnt,cnt 数组。
        for (; k >= (cur = Cnt[A] + C1[P2 - 1][A] - C1[P1][A]); ++A) k -= cur;//确定答案在哪个值域块。
        for (B = L[A]; k >= (cur = cnt[B] + C2[P2 - 1][B] - C2[P1][B]); ++B) k -= cur;//精确答案。
        Minus(x, r[P1]), Minus(l[P2], y);
        return val[B];
    }       

  • 查询前驱、后继操作：只需不断向前或向后找到第一个满足条件的即可。思维难度较低，但是细节比较繁琐，实现时一定要非常注意。

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <algorithm>
#define N 50005
#define LEN (1 << 9)
#define _R register
#define INF 0x7FFFFFFF
using namespace std;
char Buf[1 << 24], *S(Buf), *T(Buf);
#define getchar() (S == T && (T = (S = Buf) + fread(Buf, 1, 1 << 24, stdin), S == T) ? EOF : *S++)
inline int input() {
    _R int x(0), f(0);
    _R char c(getchar());
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
int a[N << 1], val[N << 1];
int bel[N], BEL[N << 1];
int len, num, Len, Num, n, m; 
int C1[LEN][LEN], C2[LEN][N << 1];
int L[LEN], R[LEN], l[LEN], r[LEN];
struct Oper { int F, S, E, opt; };
Oper d[N];
struct Data {
    int pos, val;
    inline Data() {}
    inline Data(int POS, int VAL) : pos(POS), val(VAL) {}
};
Data b[N << 1];
inline bool cmp(const Data &A, const Data &B) { return A.val < B.val; }
inline void Init_Data() {
    n = input(), m = input();
    int cnt = n, tot = 0;
    for (int i = 1; i <= n; ++i) b[i] = Data(i, input());
    for (int i = 1; i <= m; ++i) {
        int opt = d[i].opt = input();
        int F = input(), S = input(), T;
        if (opt == 3)
            d[i].F = F, d[i].E = ++cnt, b[cnt] = Data(cnt, S);
        else {
            T = input(), d[i].F = F, d[i].S = S;
            if (opt != 2)
                d[i].E = ++cnt, b[cnt] = Data(cnt, T); 
            else
                d[i].E = T;
        }
    }
    sort(b + 1, b + cnt + 1, cmp);
    for (int i = 1; i <= cnt; ++i)
        if (i == 1 || b[i].val != b[i - 1].val)
            val[a[b[i].pos] = ++tot] = b[i].val;
        else
            val[a[b[i].pos] = tot] = b[i].val;
    len = sqrt(n), num = n / len;
    Len = sqrt(tot), Num = tot / Len;
    for (int i = 1; i <= n; ++i) bel[i] = (i - 1) / len + 1;
    for (int i = 1; i <= tot; ++i) BEL[i] = (i - 1) / Len + 1;
    for (int i = 1; i <= num; ++i) l[i] = r[i - 1] + 1, r[i] = l[i] + len - 1;
    if (r[num] != n)
        ++num, l[num] = r[num - 1] + 1, r[num] = n;
    for (int i = 1; i <= Num; ++i) L[i] = R[i - 1] + 1, R[i] = L[i] + Len - 1;
    if (R[Num] != tot)
        ++Num, L[Num] = R[Num - 1] + 1, R[Num] = tot;
    for (_R int i = 1; i <= num; ++i) {
        for (_R int j = l[i], lim = r[i]; j <= lim; ++j) ++C2[i][a[j]], ++C1[i][BEL[a[j]]];
        for (_R int j = 1; j <= tot; ++j) C2[i][j] += C2[i - 1][j];
        for (_R int j = 1; j <= Num; ++j) C1[i][j] += C1[i - 1][j];
    }
}
inline int Rank(int x, int y, int val) {
    int P1 = bel[x], P2 = bel[y], ret = 0, pos = BEL[val];
    if (P1 == P2) {
        for (_R int i = x; i <= y; ++i) ret += (a[i] < val);
        return ret + 1;
    }
    for (_R int i = x; i <= r[P1]; ++i) ret += (a[i] < val);
    for (_R int i = l[P2]; i <= y; ++i) ret += (a[i] < val);
    for (_R int i = 1; i < pos; ++i) ret += C1[P2 - 1][i] - C1[P1][i];
    for (_R int i = L[pos]; i < val; ++i) ret += C2[P2 - 1][i] - C2[P1][i];
    return ret + 1;
}
int Cnt[LEN], cnt[N << 1];
inline void Add(int x, int y) {
    for (_R int i = x; i <= y; ++i) ++Cnt[BEL[a[i]]], ++cnt[a[i]];
}
inline void Minus(int x, int y) {
    for (_R int i = x; i <= y; ++i) --Cnt[BEL[a[i]]], --cnt[a[i]];
}
inline int Get(int x, int y, int k) {
    int P1 = bel[x], P2 = bel[y], A = 1, B, cur = 0;
    if (P1 == P2) {
        Add(x, y);
        for (; k >= Cnt[A]; ++A) k -= Cnt[A];
        for (B = L[A]; k >= cnt[B]; ++B) k -= cnt[B];
        Minus(x, y);
        return val[B];
    }
    Add(x, r[P1]), Add(l[P2], y);
    for (; k >= (cur = Cnt[A] + C1[P2 - 1][A] - C1[P1][A]); ++A) k -= cur;
    for (B = L[A]; k >= (cur = cnt[B] + C2[P2 - 1][B] - C2[P1][B]); ++B) k -= cur;
    Minus(x, r[P1]), Minus(l[P2], y);
    return val[B];
}
inline void Modify(int pos, int x) {
    int P = a[pos], BP = BEL[P], BN = BEL[x];
    for (_R int i = bel[pos]; i <= num; ++i) ++C1[i][BN], ++C2[i][x], --C1[i][BP], --C2[i][P];
    a[pos] = x;
}
inline int Pre(int x, int y, int k) {
    int P1 = bel[x], P2 = bel[y], pos = BEL[k], A = pos - 1, B = k - 1;
    if (P1 == P2) {
        Add(x, y);
        while (B >= L[pos] && cnt[B] == 0) --B;
        if (B == L[pos] - 1) {
            while (Cnt[A] == 0 && A >= 1) --A;
            if (A == 0) {
                Minus(x, y);
                return -INF;
            }
            for (B = R[A]; (!cnt[B]) && (B > L[A]); --B);
        }
        Minus(x, y);
        return val[B];
    }
    Add(x, r[P1]), Add(l[P2], y);
    while (B >= L[pos] && cnt[B] + C2[P2 - 1][B] - C2[P1][B] == 0) --B;
    if (B == L[pos] - 1) {
        while (Cnt[A] + C1[P2 - 1][A] - C1[P1][A] == 0 && A >= 1) --A;
        if (A == 0) {
            Minus(x, r[P1]), Minus(l[P2], y);
            return -INF;
        }
        for (B = R[A]; (cnt[B] + C2[P2 - 1][B] - C2[P1][B] == 0) && (B > L[A]) ; --B);
    }
    Minus(x, r[P1]), Minus(l[P2], y);
    return val[B];
}
inline int Nex(int x, int y, int k) {
    int P1 = bel[x], P2 = bel[y], pos = BEL[k], A = pos + 1, B = k + 1;
    if (P1 == P2) {
        Add(x, y);
        while (B <= R[pos] && cnt[B] == 0) ++B;
        if (B == R[pos] + 1) {
            while (Cnt[A] == 0 && A <= Num) ++A;
            if (A == Num + 1) {
                Minus(x, y);
                return INF;
            }
            for (B = L[A]; (!cnt[B]) && (B < R[A]); ++B);
        }
        Minus(x, y);
        return val[B];
    }
    Add(x, r[P1]), Add(l[P2], y);
    while (B <= R[pos] && cnt[B] + C2[P2 - 1][B] - C2[P1][B] == 0) ++B;
    if (B == R[pos] + 1) {
        while (Cnt[A] + C1[P2 - 1][A] - C1[P1][A] == 0 && A <= Num) ++A;
        if (A == Num + 1) {
            Minus(x, r[P1]), Minus(l[P2], y);
            return INF;
        }
        for (B = L[A]; (cnt[B] + C2[P2 - 1][B] - C2[P1][B] == 0) && (B < R[A]); ++B);
    }
    Minus(x, r[P1]), Minus(l[P2], y);
    return val[B];
}
int main() {
    Init_Data();
    for (int i = 1; i <= m; ++i) {
        if (d[i].opt == 1)
            printf("%d\n", Rank(d[i].F, d[i].S, a[d[i].E]));
        else if (d[i].opt == 2)
            printf("%d\n", Get(d[i].F, d[i].S, d[i].E - 1));
        else if (d[i].opt == 3)
            Modify(d[i].F, a[d[i].E]);
        else if (d[i].opt == 4)
            printf("%d\n", Pre(d[i].F, d[i].S, a[d[i].E]));
        else
            printf("%d\n", Nex(d[i].F, d[i].S, a[d[i].E]));
    }
    return 0;
}

• 算法标签：分块（分块套值域分块），排序，离散化。

• 时间复杂度：O((n+m)\sqrt{n+m})。

• 空间复杂度：O((n+m)\sqrt{n})。

• 期望得分：100 分。提交记录。

• 备注：这是一份在评测机不断变慢后仍然进了最优解前 20 的代码。