4 条题解
-
2
20分
依据题意模拟即可
30分
考虑转化:将 的数置为 , 的置为 ,计算所有和>=0 的非空区间数量即可,用前缀和可以优化为
80分
类比这道题,做完前缀和后,对于每个数,求其前面所有的小于等于这个数的数的个数,可以用树状数组优化至
90分
我们注意到做完前缀和后,相邻两项之间只能差 或 (因为对于每个处理后的数只能是 或 ),因此很容易证明对于位置 ,所有严格小于当前 的位置都可以用上一个等于 的位置去匹配(或是与上一个等于 的位置去匹配),也可以用所有等于 的位置来匹配,我们可以定义两个数组(或umap) 和 来分别记录上一个前缀和的数出现的位置及这个数出现的个数,这样就能写出
a[i]=a[b[sum+X-1]]+1+c[sum+X],其中 为偏移量(防止下标为负数)。时间复杂度为 ,空间复杂度为 = 230MiB 左右,最后求 即可100分
记得加快读!
code:
#include<bits/stdc++.h> using namespace std; const int N=2e7+5,X=2e7+1,M=N*2; int n,a[N],b[M],c[M],p,sum; long long ans; inline int read(){ int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x; } signed main(){ n=read(); p=read(); memset(b,-1,sizeof(b)); b[X]=0; c[X]++; for(int i=1;i<=n;i++){ int x=read(); if(x>=p) sum++; else sum--; a[i]+=c[sum+X]; if(b[sum-1+X]!=-1) a[i]+=a[b[sum-1+X]]+1; b[sum+X]=i; c[sum+X]++; ans+=a[i]; } cout<<ans; return 0; }
信息
- ID
- 78
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 133
- 已通过
- 20
- 上传者