牛客练习赛69 E 子串

子串

前言

没想到这道题存在奇巧淫技

分析

假设区间 [ L , R ] 符合条件，满足的是

但是为了保证最大值和最小值等于区间左右端点，故换一种方式，设

那么

代码

#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

#include<bits/stdc++.h>

#define ll long long
#define ull unsigned ll

using namespace std;

const int N=1e6+10;
const ull P=31;

int n;
ull a[N],h[N]={1};

unordered_map<ull,ull>k;

int main()
{
    for (int i=1;i<N;i++) h[i]=h[i-1]*P;

    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lu",&a[i]);

    ull ans=0,now=0;k[0]=1;
    for (int i=1;i<=n;i++)
    {
        now=now+h[a[i]]-h[i];
        ans+=k[now];
        k[now]++;
    }

    printf("%lu\n",ans);

    return 0;
}