51 nod 1682 中位数计数

n数据是8000，O(n^2)复杂度就能过。
因为中位数是按从小到大排序后的中间数。所以对一个区间a[l]到a[r]我们只需要小于a[i]和大于a[i]的个数相等就行。所以在查询每个a[i]的时候我们在遍历1-i的时候如果a[i]<a[j]就cnt++,a[i]>a[j]就cnt--,为啥需要cnt--呢，因为这样我们就可以知道左边的区间中小于a[i]的比大于a[i]的有多少，我们在查询右边的时候只需要找到右边大于a[i]的比小于a[i]有多少就行,这样复杂度就是O(n).
补充一下:对于偶数个的时候不用特殊去求，因为我们是求得中位数，不管奇偶只要满足上述要求就是符合条件的。

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef double dl;
using namespace std;

const int maxn=8000;
const int N=1e5;
const ll M=1e9+7;
const int INF=0x3f3f3f3f;
int a[N];
int num[N];
int n,m;
int ans[N];
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        memset(num,0,sizeof(num));
        int cnt=0;
        for(int j=i;j>=1;j--)
        {
            if(a[i]>a[j]) cnt++;
            else if(a[i]<a[j]) cnt--;
            num[maxn+cnt]++;
        }
        cnt=0;
        for(int j=i;j<=n;j++)
        {
            if(a[i]<a[j]) cnt++;
            else if(a[i]>a[j]) cnt--;
            ans[i]+=num[maxn+cnt];
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",ans[i]);
    }


}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    //int T; scanf("%d",&T)
    //for(int i=1;i<=T;i++)
        solve();
}