(未完待续)
题目链接: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;
}
近期评论