问题:https://codeforces.com/contest/1175/problem/F
关键点:随机化+异或
1.为何要异或:忽略顺序
将1~n随机的一一映射到long long值域内,形成新的映射数组b。再根据异或的特点,只需要判断:
b[1]⊕b[2]⊕…………⊕b[n]==b[a[l]]⊕b[a[l+1]]⊕……⊕b[a[r]]
2.为何要随机,因为若不随机,二进制位数有限,会存在一些情况使得异或并不正确.
例如:1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6 ⊕ 7 = 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 4 ⊕ 5
其实上述等式成立实质上就是等式两边每一个二进制位上的1的个数都相等。
那么当二进制位数变多了之后,发生错误的概率也会下降(但不会没有,只是可以近似看作没有)
问题二:如何找到所有合法子数组?
考虑以下这几个 合法子数组 一定满足的条件:
1.序列含有且仅含有一个1.
2.合法子数组的最大值就是它的长度
3.最大值要么出现在1的左边,要么出现在1的右边.
那么我们遍历序列每一个1的位置,先假设最大值出现在1的右边,那么循环遍历它右边的位置,同时统计区间最大值。然后对于每一个位置,我们假设它就是某个合法子数组的右端点。然后确定左端点。再O ( 1 ) O(1)O(1)hash判排列。然后再revese一下再跑一遍该算法即可。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=5e5+10,mod=998244353;
typedef pair<int,int> PII;
int n;
int bk[N] , a[N] , b[N] , p[N];
//异或哈希
void slove(){
int n;
cin>>n;
srand(9904);
//将n个数映射到一个ll范围下的桶中
for (int i = 1 ; i <= n ; i++){
bk[i] = ((long long)rand()<<30) + 1ll * (rand()<<16) + 1ll * rand();//可以
p[i] = p[i - 1] ^ bk[i];//p[i]表示1~i的异或和
}
for (int i = 1 ; i <= n ; i++) cin>>a[i];
int ans = 0;//
for (int t = 0 ; t < 2 ; t++){//正着跑一遍,倒着跑一遍(正着跑是假定最大值在1的右边,倒着跑是假定最大值在1的左边)
for (int i = 1 ; i <= n ; i++)
b[i] = bk[a[i]] ^ b[i - 1];
int now = -1 , mx = 0;//mx记录的是最大值,now表示当前的1的位置
for (int i = 1 ; i <= n ; i++){
if (a[i] == 1){
ans += (t == 0);//特殊记录为1的情况
now = i;
mx = 1;
continue;
}
if (now == -1) continue;//
mx = max(mx , a[i]);
if (mx < (i - now + 1)) continue;//如果mx小于区间长度的话
int x = now - (mx - (i - now + 1));//如果mx大于等于区间长度的话,找到左端点
if (x <= 0) continue;
ans += ((b[i] ^ b[x - 1]) == p[mx]);//查看异或和是否相等
}
reverse(a + 1 , a + 1 + n);
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T=1;
// cin>>T;
while(T--) slove();
}
标签:数组,int,最大值,long,异或,哈希,define
From: https://www.cnblogs.com/mendax-Z/p/18152024