自动搬运

查看原文

来自洛谷，原作者为

	lbw 若有 笃信之物 莫忘厮守

搬运于2025-08-24 22:47:04，当前版本为作者最后更新于2024-02-22 22:10:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

同时易知每个人的排名为 $a_i+x_i$ 比它小的数量加 $1$。

$p=1$

考虑 $i$ 的答案，对于 $j\not=i$ 我们希望 $x_j-x_i$ 尽可能大，而这个数一定 $\leq|i-j|$。

容易发现在 $i$ 处发炮可以使所有 $\leq$ 取到等号。

只需 $\forall i$，求 $\sum[a_j+|i-j|<a_i]$，二维数点即可。

$p=2$

考虑 $i$ 的答案。

假设 $i$ 在序列中点的左边。

对于 $j\not=i$ 我们希望 $x_i-x_j$ 尽可能大，这个数依然 $\leq|i-j|$。

假设已知 $x_i$，则 $|i-j|\geq x_i$ 的 $j$ 全部应该发炮。

如果现在 $x_i<i-1$ 则使 $x_i$ 加一不会使任何 $x_i-x_j$ 减少。

如果现在 $x_i>i$ 且 $x_i<n-i$ 则使 $x_i$ 加一不会使任何 $x_i-x_j$ 减少。

于是我们知道只有两种情况：

• $n$ 发炮。

• $1$ 发炮且 $2i-1$ 及其之后全部发炮。

右边同理。

同样二维数点即可，细节留作习题。

答案不略，如下：

i64 n,a[maxn];
struct BIT{
	i64 c[maxn],ans;IV clr(){mem(c,0);}
	IV add(i64 p,i64 v){for(;p<=n;p+=p&-p)c[p]+=v;}
	i64 Q(i64 p){ans=0;for(;p;p-=p&-p)ans+=c[p];return ans;}
	i64 Q(i64 l,i64 r){return Q(r)-Q(l-1);}
};
namespace Subtask1{
	i64 b[maxn],c[maxn],ans[maxn];BIT bit;
	IV solve(){
		F(i,1,n)c[i]=b[i]=a[i]+i;
		sort(b+1,b+1+n);i64 cnt=unique(b+1,b+1+n)-b-1;
		F(i,1,n)c[i]=lower_bound(b+1,b+1+n,c[i])-b;
		D(i,n,1)ans[i]+=bit.Q(c[i]-1),bit.add(c[i],1);

		F(i,1,n)c[i]=b[i]=a[i]-i;bit.clr();
		sort(b+1,b+1+n);cnt=unique(b+1,b+1+n)-b-1;
		F(i,1,n)c[i]=lower_bound(b+1,b+1+n,c[i])-b;
		F(i,1,n)ans[i]+=bit.Q(c[i]-1),bit.add(c[i],1);

		F(i,1,n)printf("%d\n",ans[i]+1);
	}
} // namespace Subtask1

namespace Subtask2{
	i64 Mn[maxn],b[maxn];
	pair<i64,i64>pi[maxn];
	IV cmax(i64&x,i64 val){x<val?x=val,0:0;}
	IV get(){
		i64 sum=0;
		F(i,1,n)pi[i]=make_pair(b[i],i);
		sort(pi+1,pi+1+n);
		for(int l=1,r;l<=n;l=r+1){
			r=l;while(r<n&&pi[r+1].first==pi[r].first)r++;
			F(i,l,r)cmax(Mn[pi[i].second],l-1);
		}
	}
	i64 ed[maxn],tot;BIT bit;
	struct node{i64 l,r,v,id;}qwq[maxn*3];
	IV add(i64 l,i64 r,i64 v,i64 id){qwq[++tot]={l,r,v,id};}
	IV solve(){
		F(i,1,n)b[i]=a[i]+i;get();
		F(i,1,n)b[i]=a[i]-i;get();
		FL(i,1,n){
			i64 mn=min(i-1,n-i),pos=a[i]+mn,ans=0;
			// mn>=i-j
			// j>=i-mn
			i64 pl=i-mn,pr=i+mn;
			qwq[++tot]={1,pl-1,pos-1,i};
			qwq[++tot]={pr+1,n,pos-1,i};
		}
		F(i,1,n)qwq[++tot]={i,i,a[i],0};
		auto solve=[&](){
			bit.clr();
			sort(qwq+1,qwq+1+tot,[](node A,node B){
				return A.v==B.v?A.id<B.id:A.v<B.v;
			});
			F(i,1,tot){
				if(qwq[i].id)ed[qwq[i].id]+=bit.Q(qwq[i].l,qwq[i].r);
				else bit.add(qwq[i].l,1);
			}
			tot=0;
		};solve();
		F(i,1,n)add(i,i,a[i]+i,0);
		FL(i,1,n){
			i64 mn=min(i-1,n-i),pos=a[i]+mn,pl=i-mn,pr=i+mn;
			add(pl,i-1,a[i]+i-1,i);
		}solve();
		F(i,1,n)add(i,i,a[i]-i,0);
		FL(i,1,n){
			i64 mn=min(i-1,n-i),pos=a[i]+mn,pl=i-mn,pr=i+mn;
			add(i+1,pr,a[i]-i-1,i);
		}solve();		
		F(i,1,n)cmax(Mn[i],ed[i]);
		F(i,1,n)printf("%d\n",Mn[i]+1);
	}
} // namespace Subtask2

int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	n=read();i64 p=read();
	F(i,1,n)a[i]=read();
	if(p==1)return Subtask1::solve(),0;
	if(p==2)return Subtask2::solve(),0;
	return 0;
}