前言
没想到这道题存在奇巧淫技
分析
假设区间 [ 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; }