4 条题解

  • 16
    @ 2025-3-15 9:48:38

    首先我们把所有的 aia_i 看如果 ≥p≥p 那么变成 11,否则我变成 −1-1

    然后判断区间和是否 ≥0≥0 个数

    我们设 dpidp_i 表示从 11 到 ii 有多少个比 sumisum_i 大的

    首先 dpi=dpi−1dp_i=dp_{i-1} ,设 lst=dpi−1,now=dpilst=dp_{i-1},now=dp_i

    如果 lst<nowlst<now 那么我们把从 lst nowlst~now 的所有数出现过的次数减去

    反之亦然

    mp[n]=1;
    		for(int i=1;i<=n;i++){
    			a[i]=reads();
    			sum[i][0]=sum[i-1][0],sum[i][1]=sum[i-1][1];
    			if(a[i]>=p) sum[i][0]++;
    			else sum[i][1]++;
    			int now=sum[i][0]-sum[i][1]+n,lst=sum[i-1][0]-sum[i-1][1]+n;
    			dp[i]=dp[i-1];
    			if(now>lst) for(int j=lst+1;j<=now;j++) dp[i]-=mp[j];
    			else for(int j=now+1;j<=lst;j++) dp[i]+=mp[j];
    			ans+=i-dp[i];
    			mp[now]++;
    		}
    
  • 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 左右

    • 1
      @ 2025-3-15 11:11:47

      题意

      给定一个长度为n的数组a

      问有多少个区间满足中位数大于等于p

      本题中当 n 为偶数时,定义中位数为第 n/2 和第 n/2 + 1 个数的较大的那个,而非取二者的平均数。

      做法

      我们将大于等于p的赋为1,小于的为-1

      原题就等价于有多少个序列区间和大于等于0

      然后就等价于我们枚举右端点 前缀和数组有多少个点满足a[r] >= a[l]

      1e5可以用树状数组维护

      1e7可以注意到前缀和之间的差值为1

      我们可以维护每个数的出现次数

      然后就可以维护O(1)大于a[i]的数的个数了

      要开long long

      code

      #include <bits/stdc++.h>
      using namespace std;
      
      const int N = 2e7 + 10;
      
      int n, a[N], b[N];
      
      long long p;
      
      void read(){
      	cin >> n >> p;
      	for(int i = 1;i <= n; i++){
      		cin >> a[i];
      		a[i] = a[i] >= p ? 1 : -1;
      		a[i] += a[i-1];
      	}
      	return ;
      }
      
      void compute(){
      	long long ans = 0;
      	long long t = 0;
      	b[n] = 1;
      	for(int i = 1;i <= n; i++){
      		if(a[i] > a[i-1]) t = t + b[a[i]+n] + 1;
      		else t = t - b[a[i-1]+n] + 1;
      		ans += t;
      		b[a[i]+n]++;
      	}
      	cout << ans;
      	return ;
      }
      
      int main(){
      	ios::sync_with_stdio(0);
      	cin.tie(0), cout.tie(0);
      	read(); compute();
      	return 0;
      }
      
      
      
      • -22
        @ 2025-3-14 13:23:39

        因为中位数和具体值没有关系,只是与相对大小有关系,所以我们不妨把大于等于p的设为1,剩下的设为0,这样只需要找0的个数不多于len/2的段就行了。

        但是这样太麻烦了,我们可以进一步把0变成-1,然后求非负子段个数。

        求子段的话,我们考虑前缀和,只要找到前缀和数组每位之前的比当前前缀和小的有多少位就行了。

        比如,若这一位是1,就要算有多少i满足sum[i]=1、0、-1...。

        由于一个数也算,所以特判。

        于是:80分做法有了。

        树状数组

        signed C[200010];
        void add(int x,int k) {
        	while(x<=n+100000) C[x]+=k,x+=lb(x);
        }
        int ask(int x) {
        	int ans=0;
        	while(x) ans+=C[x],x-=lb(x);
        	return ans;
        }
        signed main() {
        	R(n),R(p);
        	if(n<=100000) {
        		for(int i=1; i<=n; ++i) {
        			int R(x);
        			if(x>=p)++s;
        			else --s;
        			if(s>=0)++ans;
        			ans+=ask(s+100000);
        			add(s+100000,1);
        		}
        		cout<<ans<<"\n";
        		return 0;
        	}
        }
        

        100分做法

        根据kkksc03测试,优化掉一个log只能快0.3s,所以他索性卡长:

        #define MYBUF (1 << 20)
        char buf[MYBUF], *p1, *p2;
        #define getchar()                                                               \
          (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MYBUF, stdin), p1 == p2)   \
               ? EOF                                                               \
               : *p1++)
        

        把这个写在快读上面,就过了。


        但是,我不会这个。

        链状数组

        柱E到,Δsum=1。而树状数组每次更新就要遍历到n,太多了,我们可以打懒标记,每次只更新下一个的懒标记和自己,用到他的时候,把懒标记加到C上,再把懒标记给后边的,自己的清空。

        #include<bits/stdc++.h>
        #define int long long 
        #define R(x) x=read()
        using namespace std;
        inline int read() {
        	int x=0,y=1;
        	char e=getchar();
        	while(e<'0'||e>'9') {
        		if(e=='-')y=-1;
        		e=getchar();
        	}
        	while(e>='0'&&e<='9') {
        		x=(x<<1)+(x<<3)+(e-'0');
        		e=getchar();
        	}
        	return x*y;
        }
        
        int n,p,s,ans;
        signed C[20000010],laz[20000010];
        const signed CCF=10000000;
        signed main() {
        	R(n),R(p);
        	for(int i=1; i<=n; ++i) {
        		int R(x);
        		if(x>=p)++s;
        		else --s;
        		if(s>=0)++ans;
        		C[s+CCF]+=laz[s+CCF];
        		laz[s+CCF+1]+=laz[s+CCF];
        		laz[s+CCF]=0;
        		ans+=C[s+CCF];
        		C[s+CCF]++;
        		laz[s+CCF+1]++;
        	}
        	cout<<ans<<"\n";
        	return 0;
        }
        
        • 1

        信息

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