【每日一题】[CQOI2009]中位数图

题目

题目描述：
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

输入描述：

第一行为两个正整数n和b ，第二行为1~n 的排列。
对于 30% 的数据中，满足 n≤100；
对于 60% 的数据中，满足 n≤1000；
对于 1100% 的数据中，满足n≤100000,1≤b≤n。

输出描述：

输出一个整数，即中位数为b的连续子序列个数。

思路：

1.子串中大于等于中位数的个数比小于中位数的个数多1。
2.通常的做法是把大于K的数赋值为1，小于K的数赋值为-1。
3.如果把等于K的数赋值为0，做法就是找到题目要求的K的位置，然后记录左边的后缀和，接着累加右边的前缀和的相反数在左边出现的次数，即前缀和+后缀和=0的个数，意思就是大于K的个数和小于K的个数相等，即K为中位数。
如果在算前缀和和后缀和的时候出现0值，也就是说0某一边大于K的个数和小于K的个数相等，即K为中位数。
4.如果把等于K的数赋值为1，判断区间[L+1,R]里的中位数是K的条件是（假设数组t记录的是每个数的新值，a记录的是前缀和）即：a[R]-a[L]=1。
所以在没找到K时，记录K左边的前缀和，当K出现且右端点是a[R]时，符合K为中位数的区间个数就是就是符合条件的左端点个数，而符合条件的左端点就是a[L]=a[R]-1，符合条件的左端点个数就是a[L]的个数。

Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn = 100010;
int qian[maxn<<1],sum,a[maxn],n,k,pos;
int main() {
    js; cin>>n>>k;
    qian[n]=1;    ll ans=0;
    for(ll i=1;i<=n;++i) {
        cin>>a[i];
        if(a[i]==k)    pos=i;
        if(a[i]>=k)    ++sum;
        else --sum;
        if(!pos) ++qian[sum+n];
        else ans+=qian[sum+n-1];
    }
    cout<<ans<<endl;
    return 0;
}