题解：P7405 [JOI 2021 Final] 雪玉

· · 题解

双倍经验

手玩样例，我们能发现一些特殊性质：

顺着这个思路往下想，就能想到对每一个雪球维护一个能延伸到的最远的端点值（前提条件是对它的质量有贡献），最终的答案就是 r_i-l_i。

怎么维护这个端点值呢？

解法一：

考虑枚举天数，根据每一天的风力强度 W_j 和上一次的坐标（设为 last）更新 i 的端点值，最后直接输出就行。

记得在更新端点值的时候比较相邻两个雪球的端点值（看是否对 i 产生贡献），判断是否能更新。

此时你有了一份 O(nq) 的代码，得分 33 分，记录详情。

signed main(){
    n=read();q=read();
    for (int i=1;i<=n;i++)
      last[i]=l[i]=r[i]=read();
    for (int i=1;i<=q;i++)
      w[i]=read();
    for (int i=1;i<=q;i++)//枚举天数 
        for (int j=1;j<=n;j++){//枚举雪球 
        last[j]+=w[i];
        if (last[j]<l[j]){//如果新的位置小于左端点->“尝试 ”更新 
            if (j==1) l[j]=last[j];
            else if (last[j]>=r[j-1]) //能更新 
              l[j]=last[j];
            else l[j]=r[j-1];//不能 
          }
        else if (last[j]>r[j]){//如果新的位置大于右端点 
            if (j==n) r[j]=last[j];
            else if (last[j]<=l[j+1])//同上 
              r[j]=last[j];
            else r[j]=l[j+1];//同上 
        }
      }
    for (int i=1;i<=n;i++)
      printf("%lld\n",r[i]-l[i]);
    return 0;
}

解法二：

考虑能不能优化上述方法，我们其实还能发现一些其它性质：

我们尝试将折线的几次沿这直线的运动（不折返）浓缩为一次，直到它折返。

但这只是我们对常数的小优化，实际复杂度还是 O(nq)，别对它报什么期望。得分 33 分，记录详情能看出确实比之前快了不少（还多过了两个点），但还是 T 了很多点_*( ￣皿￣)/#__。

//cnt 记录浓缩后的段数 
//tag的含义：1->此时正在处理>0的数，0->正在处理<=0的数 
signed main(){
    n=read();q=read();
    for (int i=1;i<=n;i++)
      last[i]=l[i]=r[i]=read();
    for (int i=1,x;i<=q;i++){
        x=read();
        if (i==1) {
            if (x>0) tag=1;
            else tag=0;
            tot+=x;
        }
        else if (x<=0){
            if (tag==1) 
              w[++cnt]=tot,tag=0,tot=x;
            else tot+=x;
          }
        else {
            if (tag==1) tot+=x;
            else w[++cnt]=tot,tag=1,tot=x;
        }
    }
    w[++cnt]=tot;
    for (int i=1;i<=cnt;i++)//这一部分与之前一样 
    {
        for (int j=1;j<=n;j++){
        last[j]+=w[i];
        if (last[j]<l[j]){
            if (j==1) l[j]=last[j];
            else if (last[j]>=r[j-1]) 
              l[j]=last[j];
            else l[j]=r[j-1];
          }
        else if (last[j]>r[j]){
            if (j==n) r[j]=last[j];
            else if (last[j]<=l[j+1])
              r[j]=last[j];
            else r[j]=l[j+1];
        }
      }
    }
    for (int i=1;i<=n;i++)
      printf("%lld\n",r[i]-l[i]);
    return 0;
}

解法三：

终于来到了正解，我们考虑能优化哪一维，最终输出答案时你肯定必须枚举雪球（怎么都甩不开），所以只能在 q 上下功夫。

观察数据范围 1\le N,Q \le 2\times 10^5，最终复杂度肯定是 O(n\log q) 的，说实话，看到 \log 你应该考虑考虑二分的。

我们来看看答案是否具有二分的性质：

有了这几个性质就万事大吉了，我们直接二分冲突时间 t 就行了，复杂度 O(n\log q)，得分 100 分，记录详情。

代码写得重复啰嗦，马蜂丑陋。

int last,q,n,a[maxn],ans1,ans2;
int L[maxn],R[maxn],w[maxn];
bool check1(int x,int i){
    if (a[i-1]+R[x]>a[i]+L[x]) return 0;
    return 1;
}
bool check2(int x,int i){
    if (a[i+1]+L[x]<a[i]+R[x]) return 0;
    return 1;
}
int solve(int i,int k1,int k2){
    int ans=0;
    ans+=R[k2]-L[k1];
    if (i==1) ans+=-L[q];
    else if (k1<q&&w[k1+1]<0)
      ans+=a[i]+L[k1]-a[i-1]-R[k1];
    if (i==n) ans+=R[q];
    else if (k2<q&&w[k2+1]>0)
      ans+=a[i+1]+L[k2]-a[i]-R[k2];
    return ans; 
}
signed main(){
    n=read();q=read();
    for (int i=1;i<=n;i++) 
      a[i]=read();
    for (int i=1;i<=q;i++){
        w[i]=read();last+=w[i];
        R[i]=R[i-1];L[i]=L[i-1];
        if (last>R[i]) R[i]=last;
        else if (last<L[i]) L[i]=last;
    }
    for (int i=1;i<=n;i++){
        ans1=ans2=0;
        if (i!=1){
            int l=1,r=q;
            while (l<=r){
                int mid=(l+r)>>1;
                if (check1(mid,i)) 
                  l=mid+1,ans1=mid;
                else r=mid-1;
            }
        }
        if (i!=n){
            int l=1,r=q;
            while (l<=r){
                int mid=(l+r)>>1;
                if (check2(mid,i))
                  l=mid+1,ans2=mid;
                else r=mid-1;
            }
        }
        printf("%lld\n",solve(i,ans1,ans2));
    }
    return 0;
}