5/22每日一题-[CQOI2009]中位数图 （区间和为0的区间个数）

题目描述
给出1-n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
输入描述:
第一行为两个正整数n和b ，第二行为1~n 的排列。
输出描述:
输出一个整数，即中位数为b的连续子序列个数。

解析：
当b为中位数的时候：
子序列中必然含有b，那么首先需要在序列中确定a[i]==b的位置(pos)在哪
然后当b为中位数的时候需要满足的第二个条件就是:
在pos的左边又m个大于b的数，在pos的右边有m个小于b的数，或者在pos的左边又m个小于b的数，在pos的右边有m个大于b的数，或者在b的一侧（当b为端点的时候）大于b小于b的数字的数量一样

让大于b的都为1小于b的都为-1 ，=b时=0，这样就是找包含pos点且区间和为0的区间个数

    for(int i=1; i<=n ; i++) {
        a[i]=read();
        if(a[i]==m) pos=i,a[i]=0;
        if(a[i]>m) a[i]=1;
        else if(a[i]<m) a[i]=-1;
    }

从pos点往左计算，统计个数
往右计算的时候如果在左边出现过就直接加在答案里就行了

0的时候特殊处理一下
完整代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include<bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset(x,a,sizeof(x))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const ll  inf2 =0x3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const ll mod = 998244353;
const int N =1e6+10;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,a[maxn],ans,z[maxn],f[maxn];
int UpMing() {
    n=read();
    m=read();
    ll pos;
    for(int i=1; i<=n ; i++) {
        a[i]=read();
        if(a[i]==m) pos=i,a[i]=0;
        if(a[i]>m) a[i]=1;
        else if(a[i]<m) a[i]=-1;
    }
    ll cnt=0,tot1=0,tot2=0;
    for(int i=pos-1 ; i>=1 ; i--) {
        cnt+=a[i];
        if(cnt>0) z[cnt]++;
        else if(cnt<0) f[-cnt]++;
        else ans++,tot1++;   // 从i 点到pos点的区间符合题意，直接加在ans里 
    }
    cnt=0;
    ans++;// 自己本身一个点 也符合题意
    for(int i= pos+1 ; i<=n ; i++) {
        cnt+=a[i];
        if(cnt>0) ans+=f[cnt];
        else if(cnt<0)ans+=z[-cnt];
        else ans+=tot1,ans++;  // 从pos点到i点符合题意， 再加上 i点到pos点之前的 
    }
    out(ans);
    Accept;
}
/*

*/