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

题目链接

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

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

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

算法思想：
1.由于是求中位数是b的连续子序列，那么我们只要找到一串连续的数，里面包含数b，且大于b的数的数目与小于b的数的数目相等，才是我们要找的序列。
2.由于数据范围给的比较大，我们可以简化一下，把比b大的数直接赋值为1，小的就赋值为-1.
同时，我们再用一个sum来求和，sum往一边统计的时候，当sum==0的时候说明大于b的数的数目与小于b的数的数目相等，也就是我们找到了一个序列。
3.那么两边都有的情况怎么考虑呢？我们可以往一边记录，用一个num数组来记录sum的加减情况。
我们可以来看一下题目的样例：
{5，7，2，4，3，1，6}->{1，1，-1，4，-1，-1，1}
往左遍历：
1.sum+=-1-->sum==-1,可以这样，num[n+sum]+=1,也就是左边有一个比b小的情况加一。
2.sum+=1->sum==0,num[n+sum]+=1，左边刚好找到一个成功的序列。ans++.
3.sum+=1-->sum==1,num[n+sum]+=1,左边有一个比b大的情况加一。
现在往右遍历：
先初始化sum=0.
1.sum+=-1->sum==-1,右边找到了一个比b小的数，而num[n+1]表示左边有一个比b小的情况的数目，也就是num[n-sum],我们可以用ans+=num[n-sum]。
后面同理，最后ans==4.（ans初始值为1，因为自己本身也是一个序列）
代码如下：

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e5 + 7;
const ll maxn =1e5+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll num[maxn<<1],a[maxn];
int main(){
   ll n=read(),b=read(),pos;
   for(int i=1;i<=n;i++){
       a[i]=read();
   }
   for(int i=1;i<=n;i++){
       if(a[i]>b) a[i]=1;
       else if(a[i]<b) a[i]=-1;
       else pos=i;//标记中位数得位置
   }
   ll sum=0,ans=1;//自己一个也算
   for(int i=pos-1;i>=1;i--){
        sum+=a[i];
        num[n+sum]++;//记录左边和为sum的数量
        if(!sum) ans++;//sum为零就说明小于b的数的数量于大于b的数量相同
   }
   sum=0;//再往右遍历，同时与左边比较
   for(int i=pos+1;i<=n;i++){
       sum+=a[i];
       ans+=num[n-sum];//加上左边与其互补的数量
       if(!sum) ans++;
   }
   cout<<ans<<endl;
}