题解 | #[CQOI2009]中位数图#

下面是对中位数序列的题解

using namespace std;
int n , b ,cnt[100100], num[110000];
int main(){
    cin >> n >> b;
    int pos = 0 , ans = 1;
    for(int i = 1 ; i<= n ; i ++ ){
        int m;
        cin >> m;
        if(m < b) {
            cnt[i] = -1;
        }
        else if(m > b){
            cnt[i] = 1;
        }
        else{
            cnt[i] = 0;
            pos = i;
            //cout << pos << endl;
        }//将原来的数据处理成与中位数比较后的结果，维护成一个表示相对关系的数组cnt。
    }
        int sum = 0;
        for(int i = pos - 1; i >= 1; i -- ){
            sum += cnt[i];
            if(sum == 0) ans ++ ;
            num[n - sum] ++ ;//再开一个数组num来存储中位数两边都有序列的情况，这里的意思是（例如当sum = 1时，也就是比中位数大的数比比中位数小的数多一个时，记录[n - 1]上的值自加， 这样当后续遍历中位数右边数组的时候sum = -1时可以直接累加情况数，这样的意思是左边数组比中位数大的数多一个，而右边数组中比中位数小的数多一个，那两边序列正好就是满足条件的序列）。然后，当只取中位数一边的序列时，比中位数大的和小的数量相等时直接累加情况（++）。
        }
        sum = 0;
        for(int i = pos + 1; i <= n ; i ++ ){
            sum += cnt[i];
            if(sum == 0) ans ++ ;
            ans += num[n + sum];
        }
    cout << ans << endl;
    return 0;
}