首先我们把所有的 $a_i$ 看如果 $≥p$ 那么变成 $1$，否则我变成 $-1$

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

我们设 $dp_i$ 表示从 $1$ 到 $i$ 有多少个比 $sum_i$ 大的

首先 $dp_i=dp_{i-1}$ ，设 $lst=dp_{i-1},now=dp_i$

如果 $lst<now$ 那么我们把从 $lst~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]++;
		}

题意

给定一个长度为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;
}

因为中位数和具体值没有关系，只是与相对大小有关系，所以我们不妨把大于等于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;
}