4 条题解

  • 2
    @ 2026-9-28 9:00:06

    20分

    依据题意模拟即可

    30分

    考虑转化:将 >p>p 的数置为 11,<p<p 的置为 −1-1,计算所有和>=0 的非空区间数量即可,用前缀和可以优化为 O(N2)O(N^2)

    80分

    类比这道题,做完前缀和后,对于每个数,求其前面所有的小于等于这个数的数的个数,可以用树状数组优化至 O(Nlog⁡N)O(N\log N)

    90分

    我们注意到做完前缀和后,相邻两项之间只能差 11 或 −1-1(因为对于每个处理后的数只能是 11 或 −1-1 ),因此很容易证明对于位置 ii,所有严格小于当前 sumsum 的位置都可以用上一个等于 sum−1sum-1 的位置去匹配(或是与上一个等于 sum−1sum-1 的位置去匹配),也可以用所有等于 sumsum 的位置来匹配,我们可以定义两个数组(或umap) bb 和 cc 来分别记录上一个前缀和的数出现的位置及这个数出现的个数,这样就能写出 a[i]=a[b[sum+X-1]]+1+c[sum+X],其中 XX 为偏移量(防止下标为负数)。时间复杂度为 O(N)O(N),空间复杂度为 O(N)O(N) = 230MiB 左右,最后求 ∑i=1nai\sum _{i=1}^na_i 即可

    100分

    N=2e7N=2e7 记得加快读!

    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;
    }
    

    AC记录,当然我们也能进一步优化到 350ms 左右

    信息

    ID
    78
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    (无)
    递交数
    133
    已通过
    20
    上传者