（未完待续）

题目链接：JZOJ 1386。

题目

本题有部分分解法（暴力，正解）。

题解

解法 A （直接模拟）

思路

代码

解法 B （正解）

思路

这里，我们考虑使用一种优秀的数据结构——树状数组，来解决我们的问题。

代码

渐进时间复杂度为 $\Theta(n\log _ 2n)$，预计得分 $100$ 分。

#include<cstdio>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=100000+5;
struct TreeArray{
    #define lowbit(x) ( (x) & ( - (x) ) )
    int n,unit[MAXN];
    void Update(int ID,int val){
        while(ID<=n){
            unit[ID]+=val;
            ID+=lowbit(ID);
        }
        return;
    }
    int Query(int ID){
        register int sum=0;
        while(ID){
            sum+=unit[ID];
            ID-=lowbit(ID);
        }
        return sum;
    }
    #undef lowbit
};
int n;
int p[MAXN];
TreeArray T;
int main(void){
    register int i;
    n=read();
    //scanf("%d",&n);
    T.n=n;
    for(i=1;i<=n;++i){
        static int a;
        a=read();
        //scanf("%d",&a);
        p[a]=i;
        T.Update(i,1);
    }
    for(i=1;i<=n;++i){
        if(i&1){
            printf("%d\n",T.Query(p[(i+1)>>1]-1));
            T.Update(p[(i+1)>>1],-1);
        }
        else{
            printf("%d\n",T.Query(n)-T.Query(p[n-(i>>1)+1]));
            T.Update(p[(n-(i>>1)+1)],-1);
        }
    }
    return 0;
}