应用场景

    一般用于快速找到一个子数组是否完整地出现，主要是利用了异或的性质和哈希降低冲突的原理 .

原理介绍

    异或满足交换律，判断某一段数字是否一一出现(排序后相同)，可以通过其区间异或值是否相同判定 .
    区间异或值需要先维护前缀异或和，区间 $[l,r]$ 的区间异或值为$Sum[r] \oplus Sum[l-1]$ .

代码模版

  例：判断区间[l,r]的数字是否包含数字 $l - r$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
mt19937_64 rnd(time(0)); //随机数生成
int n, q, l,r,a[300010];
i64 base[300010], Xor[300010], Hash[300010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n;i++)
        base[i] = rnd(), Xor[i] = Xor[i - 1] ^ base[i];
    for (int i = 1; i <= n; i++)
        cin >> a[i], Hash[i] = Hash[i - 1] ^ base[a[i]];
    while(q--){
        int l, r;
        cin >> l >> r;
        cout<<(Hash[r] ^ Hash[l-1] == Xor[r] ^ Xor[l-1] ?" Yes" : "No) << endl;
    }
    if(Hash)
    return 0;
}

  其中,mt19937_64 rnd(time(0))是C++ \库自带的梅森旋转伪随机数，可以随机生成64位整数，随机的内容直到$2^{19937}$次调用后才会重复.

题目链接：https://codeforces.com/contest/1175/problem/F

题意

给定一个$a$数组，如果该数组的某个子数组 $a_l,a_{l+1}…,a_{r-1},a_r$ 包含从1到$r-l+1$的所有整数有且只有一次，那么该子数组称之为”子排列”。请计算子排列的数量 .

数据范围

  • $1 \le n \le 3 \cdot 10^5$
  • $1 \le a_i \le n$

分析

    不难发现，一个区间子排列必然包含1和子区间最大值；假设最大值在$1$的右侧，当我们枚举到各点的最大值(右端点)时，最大值就是该区间的长度，所以我们可以推断出理论的区间左端点，设当前最大值为$mx$,当前下标为$i$，上一次出现$1$的位置是$cur$条件是：

  1. $cur \ge i-mx+1$ ,即左端点一定要包含最近的$1$
  2. 区间$[l,r]$对应的$[1 , r-l+1]$数值恰好出现一次，套用异或哈希的模版即可

    上述便是最大值出现在$1$右侧的情况；反之，我们将数组翻转(reverse)，再进行一次遍历就能统计出最大值出现在$1$左侧的情况。如若满足两者条件，计数值加一，并记得特判$a_i=1$本身同样是子排列 .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
mt19937_64 rnd(time(0));
int n, a[300010];
i64 base[300010], Xor[300010], Hash[300010];
i64 ans = 0;
void solve(){
    int cur = -1, mx;
    for (int i = 1; i <= n;i++){
        if(a[i]==1){
            mx = 0, cur = i;
            continue;
        }
        mx = max(mx, a[i]);
        if(cur!=-1&&mx>=i-cur+1){
            int l = i - mx + 1;
            if(l<1)
                continue;
            i64 res1 = Hash[i] ^ Hash[l - 1], res2 = Xor[mx];
            ans += (res1 == res2);
        }
    }
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n;i++)
        base[i] = rnd(), Xor[i] = Xor[i - 1] ^ base[i];
    for (int i = 1; i <= n; i++){
        cin >> a[i], Hash[i] = Hash[i - 1] ^ base[a[i]];
        if(a[i]==1)
            ans++;
    }
    solve();
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n;i++)
        Hash[i] = Hash[i - 1] ^ base[a[i]];
    solve();
    cout << ans << endl;
    return 0;
}