P11157 【MX-X6-T3】さよならワンダーランド 题解

P11157 【MX-X6-T3】さよならワンダーランド

神秘思维题。

考虑到转化式子，拆成 j\ge a_i 和 j\le a_{i+j}。前一个不等式是容易满足的，我们只需要在 [\max\{1,i+a_i\},n] 中选择 i+j 即可。

第二个不等式可化为 a_{i+j}-j\ge 0，因此我们在[i+a_i,n] 中选择 a_{i+j}-j 的最大值。如果最大值在位置 k，则有 a_k-(k-i)\le 0。注意到 i 相同时大小关系只与 a_k-k 有关，所以同一个 i 内最大值取到哪与 i 无关，按照 a_k-k 预处理一下即可。

我们枚举每一个 i，直接判断预处理出的最大值位置是否合法，就解决了这个问题。

#include <bits/stdc++.h>
using namespace std;
long long t,n,a[500000],b[500000],p[500000];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i]-i,p[i]=i;
    for(int i=n-1;i>=1;i--)
        if(b[p[i]]<b[p[i+1]])p[i]=p[i+1];
    for(int i=1;i<=n;i++)
        {
        long long t=max(1ll,i+a[i]);
        if(t>n)printf("0\n");
        else if(p[t]-i<=a[p[t]])printf("1 %lld\n",p[t]-i);
        else printf("0\n");
        }
    return 0;
}