前缀和求区间

题意：求x是区间第K小数的区间个数，就是找有k-1个数小于X的区间。
我们可以把小于等于x的值的位置由1代替，而大于x的值的位置为0.这样就变成一个 01 序列。

• 1 ：小于等于x
• 0 : 大于x

我们设 a[] 为一个前缀和数组，那么我们只需要找到 (区间里1的数量 == k && 该区间包含x) 前面我们定义 1 的意义为小于等于x ，所以在我们这里需要找区间含1数量为k

	这里我们可以想到一个比较直接的方法，找到满足的区间----O(n^2) 
    
    pos: x值的位置
    
	for(int i = 1; i<= pos ;i++ ){//枚举pos左侧
    
    	for(int j = pos;j<= n;j++){//枚举pos右侧
        	if( a[j] -a[i-1] == k) ans++;
        }
    }

显然，我们需要复杂度更低的方法

设 b[] 为 a[i] 对应的数量
后面就具体看代码

#include<bits/stdc++.h>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
using namespace std;
int main()
{
 	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 	
	int n,x,k;
	cin>>n>>x>>k;
	
	int a[n+2];
	ms(a,0);
	int pos = 0;
	for(int i = 1;i <= n ; i++){
		int w;
		cin>>w;
		if( w == x ) pos = i;
		a[i] = a[i-1] + (w <= x); //获得a[]数组
	}
	
	int ans = 0;
	
/*	
（O（n^2）)
	for(int i = 1;i<=pos ;i++){
		for(int j = pos;j<=n;j++){
			if(a[j] - a[i-1] == k) ans++;
		}
	}
*/	
	int b[2000005];
	ms(b,0);
	
	for(int i = pos ;i<=n;i++){
		b[a[i]]++;	             //只需要得到pos右边对应a[i]的数量
	}
	
	for(int i=1; i<=pos; i++){
		ans += b[a[i-1] + k];       // a[i-1] + k == a[]所对应的值，b[]存的就是对应a[]值的数量
	}

	
	cout<<ans<<endl;

}

很久之前做的题目，我看题解好像没写这种就写了一下，第一次写题解。