题解 | #[CQOI2009]中位数图# 数组的前缀、后缀和

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main() {
        int n, b;
        scanf("%d %d", &n, &b);
        int data[100100];//将序列元素和指定中位数对比，分类大于的是1，小于的是-1，等于是0；
        int pos;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            if (x > b) data[i] = 1;
            else if (x < b) data[i] = -1;
            else {
                data[i] = 0;
                pos = i;
            }
//             cout<<data[i]<<" ";
        }
//         cout<<endl;
        // 2 2 2 0 1 1 1
        //-3 -2 -1 0 1 2 3
        int acc = 0;
        int l_sum[100100];//l_sum[i]表示中位数左边第i个位置大于、小于中位数的数字总和；
        int r_sum[100100];//同理这个表示右边
    
        for (int i = pos; i >= 1; i--) {
            static int x=0;
            x += data[i];
            l_sum[i] = x;
            
        }
//         for(int i=1;i<=pos;i++)
//             cout<<l_sum[i]<<" ";
        for (int i = pos+1; i <= n; i++) {
           static int x = 0;
            x += data[i];
            r_sum[i] = x;
//             cout << x << " ";
        }
//         cout << endl;
        for (int i = pos; i <= n; i++) {
            for (int j = 1; j <= pos; j++) {
                if (l_sum[j] + r_sum[i] == 0) {
                //左边大于、小于中位数的的数字总数等于右边大于、大于小于中位数的的数字总和；+为大于中  的数字总和，-为小于中  的数字总和
                    acc++;
//                     cout<<i<<" "<<j<<" "<<endl;    
                }
            }
        }
            cout << acc;
            //1 1 -1 0 -1 -1 1
    
            //  1  0 -1  0 -1 -2 -1
    //               1  1  0  1 self(1);
            
            //  0 -1 1 1 -1
    
            // -1 1 0 1 -1
    
            // 1 -1 1 -1 0
            return 0;
        }