Lost Rivers
考虑倒序处理,最后一头牛的身高为$h[n]+1$,那么是不是意味着$h[n]+1$这个数(或高度、位置)已经有人了,无法对之后的牛产生贡献,那么是否有想到权值线段树,如果$i$被占用,就删去$i$这个位置的$1$。
可是按照蓝书上的思路,我选择打一种十分鬼畜的方法。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
using namespace std;
const int N=1e5+5;
inline void qr(int &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int c[N];int n;
void add(int x){for(;x<=n;x+=x&-x)--c[x];}
int p[21],a[N],h[N];
int main()
{
p[0]=1;
for(int i=1;i<20;i++)p[i]=p[i-1]<<1;
qr(n);int t=log(n)/log(2);
for(int i=1;i<=n;i++)
{
++c[i];
if(i+(i&-i)<=n)c[i+(i&-i)]+=c[i];
}
a[1]=1;
for(int i=2;i<=n;i++)qr(a[i]),++a[i];
for(int i=n;i;i--)
{
int ans=0,sum=0;
for(int j=t;~j;j--)
if((ans|p[j])<=n&&sum+c[ans|p[j]]<a[i])
{
sum+=c[ans|p[j]];
ans|=p[j];
}
add(h[i]=ans+1);
}
for(int i=1;i<=n;i++)qw(h[i]),puts("");
return 0;
}
最后一次更新于2019-10-11
0 条评论