Gty的二逼妹子序列-分块与莫队算法的应用

Gty的二逼妹子序列

Autumn 和 Bakser 正在研究 Gty 的妹子序列，但遇到了一个难题。他们希望计算某个区间内美丽度属于 [a, b] 的妹子的美丽度种类数。为了简化问题，假设所有妹子的美丽度都在 [1, n] 范围内。

给定一个长度为 n (1 <= n <= 100000) 的正整数序列 s (1 <= si <= n)，以及 m (1 <= m <= 1000000) 次询问 “l, r, a, b”。每次询问需要输出 sl 到 sr 中，权值属于 [a, b] 的权值的种类数。

输入格式

第一行包含两个整数 n 和 m (1 <= n <= 100000, 1 <= m <= 1000000)，表示数列 s 中的元素数和询问数。

第二行包含 n 个整数 s1 到 sn (1 <= si <= n)。

接下来 m 行，每行包含 4 个整数 l, r, a, b (1 <= l <= r <= n, 1 <= a <= b <= n)，表示一次询问。

保证所有涉及的数在 C++ 的 int 范围内，并且输入是合法的。

输出格式

对于每个询问，单独输出一行，表示 sl 到 sr 中权值属于 [a, b] 的权值的种类数。

样例输入

10 10
    4 4 5 1 4 1 5 1 2 1
    5 9 1 2
    3 4 7 9
    4 4 2 5
    2 3 4 7
    5 10 4 4
    3 9 1 1
    1 4 5 9
    8 9 3 3
    2 2 1 6
    8 9 1 4

样例输出

样例解释

部分解释如下：

5 9 1 2: 子序列为 4 1 5 1 2，在 [1, 2] 里的权值有 1, 1, 2，共 2 种，因此答案为 2。
3 4 7 9: 子序列为 5 1，在 [7, 9] 里的权值有 5，共 1 种，因此答案为 1。
4 4 2 5: 子序列为 1，没有权值在 [2, 5] 中，因此答案为 0。
2 3 4 7: 子序列为 4 5，权值在 [4, 7] 中的有 4, 5，因此答案为 2。

建议使用输入/输出优化。

解决方案

使用分块和莫队算法可以高效地解决这个问题。具体步骤如下：

对权值进行分块处理。
使用莫队算法对询问进行排序和处理。

关键点在于询问的排序方式，确保每次移动指针时的复杂度尽可能低。

代码实现

#include
#include
#include
#include
#include
using namespace std;

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

#define maxn 100010
#define maxm 1000100

int n, m, a[maxn], pos[maxn], num[maxn], an[maxn], bll, bln;

struct Asknode {
    int l, r, a, b, id;
    bool operator <(const Asknode &A) const {
        if (pos[l] == pos[A.l]) return r  R) move1(nr), nr--;
    while (nl > L) nl--, move2(nl);
    while (nr

感谢 Gty 大哥、块爷和 Bakser 学长的指导。

前排围观自己的傻逼错误:

技术分享