[ROI 2018] Robomarathon 题解

_lbw_ · 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 减少。

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

右边同理。

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

答案不略，如下：

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;
}