牛客练习赛69 E 字串（思维 || 单调栈 + 扫描线 + 树状数组）

链接：https://ac.nowcoder.com/acm/contest/7329/E
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给出一个长度为 n 排列 pi

规定一个区间 [l,r] (l<=r) 是 fair 的，当且仅当区间中最小值等于 l 并且最大值等于 r

求 fair 区间的个数

输入描述:

第一行一个 n 代表排列长度

接下来一行 n 个数，即 pi

输出描述:

一个数，表示合法的区间个数

示例1

输入

5
1 2 3 4 5

输出

15

说明

所有的区间都合法

备注:

对于 100% 的数据，n≤10^6

思路一：异或

考虑一段合法的fair区间[l, r]，当且仅当[l, r]中的每一个数都从p[l] ~ p[r]中出现过，才会有[l, r]中区间的最大值为r, 最小值为l，因此可以将[l, r]中的每个数赋一个随机数，即 l 对应 a ， l + 1 对应 b ， l + 2 对应 c ……，序列中 l 出现的位置也对应a，l + 1出现的位置对应b，l + 2出现的位置对应c ……

把[l, r]中每个数对应的随机数和p[l] ~ p[r]每个数对应的随机数异或起来，如果异或和为0，说明[l, r]中的每个数都在p[l] ~ p[r]中出现过了，即p[l] ~ p[r]中的最小值为 l， 最大值为r

get到一个生成64位随机数的方法：mt19937_64 rng(time(0)); ll tmp = rng();

接下来求异或前缀和，寻找异或和为0的子段，累加起来。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;
int p[N];
ll b[N];
mt19937_64 rng(time(0));
unordered_map<ll, int>mp;

int main() {
    int n;
    scanf("%d", &n);
    mp.clear();
    memset(b, 0, sizeof(b));
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &p[i]);
        ll tmp = rng();
        b[p[i]] ^= tmp;
        b[i] ^= tmp;
    }
    for(int i = 0; i <= n; ++i) b[i] ^= b[i - 1];
    ll ans = 0;
    for(int i = 0; i <= n; ++i) {
        ans += mp[b[i]];
        mp[b[i]]++;
    }
    printf("%lld\n", ans);
    return 0;
}

思路二：单调栈 + 扫描线+ 树状数组

目前没懂 贴个大佬的题解 https://blog.nowcoder.net/n/444e51564a6442a6ae884329aad9e737