题解 CF1175F 【The Number of Subpermutations】
SIGSEGV
2020-01-04 12:48:35
考虑给每一个$1$~$n$的整数赋一个64位无符号值用于哈希，记为$h_1,h_2,...,h_n$，则序列中$[l,r]$的哈希值为
$h_{a_l} \oplus h_{a_{l+1}} \oplus ... \oplus h_{a_r} $，同理可得一个$1$~$k$排列的哈希值为$h_1 \oplus h_2 \oplus ... \oplus h_k$，且由于异或操作具有交换律和结合律，所以所得的哈希值与排列顺序无关。
对于每个$a_k=1$，从$k+1$开始递增枚举右端点$r$(长度为$1$的子排列单独统计)，令$L=\max_{k\le j\le r}a_j$，则显然$L$也为子排列长度（如果存在子排列的话），因此比较$h_1 \oplus h_2 \oplus ... \oplus h_L$与$h_{a_{r-L+1}} \oplus h_{a_{r-L+2}} \oplus ... \oplus h_{a_r}$，若相等则答案加一。当$a_r=1\lor r>n$时停止枚举（显然一个子排列里不会出现两个$1$）
这样珂以统计所有最大值在$1$右侧的子排列，再把整个序列反转一下进行统计，最后加上序列中$1$的个数即为答案
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
using ull = unsigned long long;
int n,a[N];
ull h[N],num[N],pre[N];
int calc(int pos)
{
int mx = 1,ret = 0;
for (int i = pos + 1;i <= n && a[i] != 1;i++)
{
mx = max(mx,a[i]);
if (i >= mx && i - mx + 1 <= pos && num[mx] == (pre[i] ^ pre[i - mx])) ++ret;
}
return ret;
}
int main ()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
default_random_engine e;uniform_int_distribution<ull> u;
e.seed(time(0));
for (int i = 1;i <= n;i++) h[i] = u(e),num[i] = num[i - 1] ^ h[i];
int ans = 0;
for (int i = 1;i <= n;i++) pre[i] = pre[i - 1] ^ h[a[i]];
for (int i = 1;i <= n;i++) if (a[i] == 1) ans += calc(i) + 1;
reverse(a + 1,a + n + 1);
for (int i = 1;i <= n;i++) pre[i] = pre[i - 1] ^ h[a[i]];
for (int i = 1;i <= n;i++) if (a[i] == 1) ans += calc(i);
cout << ans << endl;
return 0;
}
```