题意：给出一个长度为 n ( n &lt; = 100000 ) n(n&lt;=100000) n(n<=100000)的序列，有 m ( m &lt; = 5 ) m(m&lt;=5) m(m<=5)次询问，每次询问有多少个长度 ∈ [ l 2 , r 2 ] ∈[l2,r2] ∈[l2,r2]的区间，中位数大小 ∈ [ l 1 , r 1 ] ∈[l1,r1] ∈[l1,r1]

Solution

O ( n m l o g n ) O(nmlogn) O(nmlogn)：把 &lt; = x &lt;=x <=x的记为 1 1 1， &gt; x &gt;x >x的记为 − 1 -1 −1，计算区间和 &gt; = 0 &gt;=0 >=0的区间数
O ( n m ) O(nm) O(nm)：灵活差分

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100001;
int a[N],b[N],c[N<<1],n,m,i,l1,r1,l2,r2;
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
ll ask(int x,int y){
	memset(c,0,(2*n+1)<<2);
	b[0]=n;
	int s=0;ll ans=0;
	for (int i=1;i<=n;i++){
		if (a[i]<=x) b[i]=b[i-1]+1,s+=c[b[i]];
		else s-=c[b[i-1]],b[i]=b[i-1]-1;
		if (i>=y) c[b[i-y]]++,s+=(b[i]>=b[i-y]);
		ans+=s;
	}
	return ans;
}
int main(){
	n=rd();
	for (i=1;i<=n;i++) a[i]=rd();
	for (m=rd();m--;){
		l1=rd(),r1=rd(),l2=rd(),r2=rd();
		printf("%lld\n",ask(r1,l2)-ask(l1-1,l2)-ask(r1,r2+1)+ask(l1-1,r2+1));
	}
}