Rearrange Query#

题目大意#

给你两个长度为 $N$ 的数组，分别为 $A$ 和 $B$ ，有 $Q$ 个询问，每个询问有四个值，分别为 $l, r, L, R$ ，问 $A[l-r],B[L-R]$ 的多重集是否相等。

题目链接：https://atcoder.jp/contests/abc367/tasks/abc367_f

数据范围#

$1 \le N,Q \le 2\times10^5$
$1 \le A_i, B_i \le N$
$1 \le l \le r \le N$
$1 \le L \le R \le N$

题解#

使用 Zobrist哈希 判断，具体操作如下：

取两个较大值 $L,MOD$
给 $1$ 到 $N$ 的每个值都映射到一个 $[0, L - 1]$ 里面的数，比如 $$
根据随机好的值求 $A$ 和 $B$ 的前缀值，比如 $S_A(r) = (\sum_{i=1}^r random[A[i]]) \% MOD$
根据前缀和判断两多重集是否相等，如果值不相等为 no-instance，如果相等，则至少有 $1-\frac{1}{L}$ 的概率认为其为yes-instance，因此对于一个具有 $Q$ 次询问的题，通过测试的概率为有 $(1-\frac{1}{L})^Q$ （可能有误）

因此，建议 $L$ 取 $2^{45}$ 或者 $10^{13}$ ， $MOD$ 取 $2^{61}-1$

拓展

如果不是求多重集合，而是求集合呢？？更简单了，那么就不是求前缀和，而是求前缀异或，同时也不需要 $MOD$ 了

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
#include <random>
5

6
using namespace std;
7

8
random_device rd;
9
mt19937_64 gen(rd());
10

11
using LL = long long;
12

13

14
const int N = 200010;
15
const LL L = 1e13, MOD = (1ll << 61) - 1;
16

17
LL h[N];
18
LL A[N], B[N];
19

20

21
LL g(LL x) {
22
    return (x % MOD + MOD) % MOD;
23
}
24

25
int main() {
26

27
    // freopen("../in.txt", "r", stdin);
28
    // freopen("../out.txt", "w", stdout);
29
    int n, q; scanf("%d%d", &n, &q);
30
    for (int i = 1; i <= n; i ++ ) h[i] = gen() % L;
31

32
    for (int i = 1; i <= n; i ++ ) {
33
        int x; scanf("%d", &x);
34
        A[i] = (A[i - 1] + h[x]) % MOD;
35
    }
36
    for (int i = 1; i <= n; i ++ ) {
37
        int x; scanf("%d", &x);
38
        B[i] = (B[i - 1] + h[x]) % MOD;
39
    }
40

41
    while (q -- ) {
42
        int l, r, L, R; scanf("%d%d%d%d", &l, &r, &L, &R);
43
        if (g(A[r] - A[l - 1]) == g(B[R] - B[L - 1])) puts("Yes");
44
        else puts("No");
45
    }
46

47
    return 0;
48
}

NOTE
证明自行查阅资料

[SDOI2009] HH的项链#

题目大意#

给你一个长度为 $n$ 的数组 $A$ ，给你 $q$ 个询问。每个询问有两个整数 $l, r$ ，问 $A$ 数组中区间 $[l,r]$ 的集合个数

题目链接：https://www.luogu.org/problemnew/show/P1972

数据范围#

$1\le n, q \le 10^6$
$1 \le A_i \le 10^9$
$1 \le l,r \le n$

题解#

离线+树状数组#

时间复杂度 $O(nlogn)$

第一步，首先把所有的询问存储下来，然后根据右端点排序

第二步，记录项链中每个贝壳其左边第一个相同种类的下标

第三步，把所有贝壳的种类的贡献都放在最右边的贝壳中

第四步，处理询问，按照右端点从大到小来处理，如果此时的右端点是大于上一轮右端点，也就意味着当前右端点的后面部分已经没用了，所有需要更新。更新的原则是：1. 转移贡献，根据第二步计算的当前贝壳其左边第一个相同种类的下标贡献+1，当前贝壳贡献减一

第五步，当前询问的答案是 $query(r) - query(l - 1)$

代码如下

1
#include <iostream>
2
#include <unordered_map>
3
#include <algorithm>
4
#include <map>
5

6
#define lowbit(x) ((x) & (-x))
7

8
using namespace std;
9

10
typedef tuple<int, int, int> TIII;
11

12
const int N = 1000010;
13

14
int tr[N];
15
int n, q;
16
TIII arr[N];
17
int color[N];
18
int res[N];
19
int pre[N];
20
map<int, int> um;
21

22
void add(int x, int val) {
23
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += val;
24
}
25

26
int query(int r) {
27

28
    int res = 0;
29
    for (int i = r; i; i -= lowbit(i)) res += tr[i];
30
    return res;
31
}
32

33
int main() {
34

35
    scanf("%d", &n);
36
    for (int i = 1; i <= n; i ++ ) scanf("%d", &color[i]);
37

38
    for (int i = 1; i <= n; i ++ ) {
39
        if (um.count(color[i])) {
40
            add(um[color[i]], -1);
41
            pre[i] = um[color[i]];
42
        }
43
        add(i, 1);
44
        um[color[i]] = i;
45
    }
46

47
    scanf("%d", &q);
48
    for (int i = 1; i <= q; i ++ ) {
49
        int x, y; scanf("%d%d", &x, &y);
50
        arr[i] = {y, x, i};
51
    }
52

53
    sort(arr + 1, arr + 1 + q);
54
    reverse(arr + 1, arr + 1 + q);
55

56
    int last = n;
57
    for (int i = 1; i <= q; i ++ ) {
58
        auto [r, l, id] = arr[i];
59
        while (last > r) {
60
            if (pre[last]) {
61
                add(pre[last], 1);
62
            }
63
            add(last, -1);
64
            last -- ;
65
        }
66
        res[id] = query(r) - query(l - 1);
67
    }
68

69
    for (int i = 1; i <= q; i ++ ) printf("%d\n", res[i]);
70
    return 0;
71
}

NOTE
hh，其实可以算左端点的贡献，按照左端点排序，应该更简洁