牛客练习赛69 E 子串

子串

https://ac.nowcoder.com/acm/contest/7329/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;
}
比赛题解 文章被收录于专栏

牛客IOI周赛,团队赛,练习赛,挑战赛,各种模拟赛的部分题解

全部评论

相关推荐

迟缓的斜杠青年巴比Q了:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务