题解：P11110 [ROI 2023] 陶陶装苹果 (Day 2)

· · 题解

考察选手对于复杂问题的刻画。

考虑对于固定的 k，可用的 w_i 是从小到大排序后，w 的一个前缀。则模拟挨个 append w_i 的过程。

将“(x,y) 是 k 可达到的”描述为“(x,y) 是黑点”，“(x,y) 不是 k 可达到的”描述为 “(x,y) 是红点”。初始有且只有 (0,0) 为黑点。

每次对于当前黑点集合 S：

  1. 设 T_1 为 S 向上平移 w_i 个单位长度。
  2. 设 T_2 为 S 向右平移 w_i 个单位长度。

则最终询问等价于“查询 (0,0)-(a,b) 矩形内整点（含边界）是否全黑”。

考虑初始的 (0,0) 染色给 (w_1,0),(0,w_1)。容易发现，由于 w_1<w_2<\cdots，在 y=-x+w_1 直线下方的点都不可能再被染黑。

如图，红点都不可能被染黑。

那这个时候 k- 完美的 (a,b) 就只有 (0,0) 了。

唯一可能继续的情况就是 w_1=1，如图。

将这样连续的黑点描述为“等腰直角三角形”。

如果 w_2 有贡献，那必然要保证 T_1,T_2 和 S 各自有交（否则归约到图 1 中，红点不可能被染黑，实际有贡献的仍然是 (0,0) 所在连通黑点集）。

这就是说 w_i \le \sum\limits_{j=1}^{i-1} w_j+1 才会产生新贡献，考虑如何刻画贡献。

将图形彻底抽象化后，考虑：

一个红色的等腰直角三角形在操作后，由于图中“红、绿部分的并”不完全是大号等腰直角三角形（中间有空部分），所以新的图案是紫色部分，大体描述为等腰直角三角形和两个平行四边形的并。

读者不妨自己动手画一画，发现最终图案只有可能是：

  1. 等腰直角三角形
  2. 等腰直角三角形+若干平行四边形（下图）

（红运动到蓝是最后一步，得到紫色）

不难发现 append 一个 w 只会添加/修改 \mathcal O(1) 个平行四边形，那暴力更改就行。

复杂度是单 \log，因为查询需要二分，而图形处理为线性。

然后你会发现你根本不会处理这个图形。

实际上，设 w_{1 \sim i} 对应的图形是 G_i，我们有 G_j \subseteq G_i 对于任意 j<i。而我们把图形沿 y=x 裁剪，取右下部分，发现每次操作只有两种：

  1. 扩大原有等腰直角三角形
  2. 增加一个平行四边形

第一类操作可以随便维护，第二类由于每回只增加一个平行四边形，用数组存一下新平行四边形角的高度即可（它的右下角必定是 (\sum\limits_{i=1}^n w_i,0)）。

具体看代码吧（别的题解代码好诡异/kel），感觉就是很神秘吧。

我的代码实现能力怎么这么弱。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=300005;
int n,q,z,w[N],tri[N],y[N],sum[N];
/*
tri[i] 表示图形 G_i 等腰直角三角形的腰长
tri[i-1] <= tri[i]
y[i] 表示 (G_i \ G_{i-1}) 平行四边形的高度
如果 G_{i-1} = G_i 则 y[i]=y[i-1]
y[i-1] >= y[i]
*/

bool chk(int a,int b,int p){
    if(a+b<=tri[p])return 1; // 在等腰直角三角形内
    int l=1,r=p,c=-1;
    // 考虑平四的纵坐标递减
    // 所以找到刚好 sum(w)>=a+b 的那个位置
    // 平四是理论最大的
    while(l<=r){
        int mid=l+r>>1;
        if(sum[mid]>=a+b)c=mid,r=mid-1;
        else l=mid+1;
    }
    if(!~c)return 0;
    if(a<b)swap(a,b);
    // x=a 与 x+y=sum[c] 的交点 (a,sum[c]-a)
    // 但 sum[c]-a 要对 y[c] 取 min
    if(min(y[c],sum[c]-a)>=b)return 1;
    return 0;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>w[i];
    sort(w+1,w+n+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+w[i];
        if(w[i]<=tri[i-1]/2+1&&tri[i-1]==y[i-1]) // T1,T2,S 交集是等腰直角三角形
            tri[i]=y[i]=sum[i]; // 新的等腰直角三角形
        else if(w[i]<=sum[i-1]+1){ // 有交
            tri[i]=tri[i-1];
            // 考虑平移后 x=w[i] 与 x+y=sum[i-1] 的交点 (w[i],sum[i-1]-w[i])
            // 如果没有更矮的平四诞生，延长原平四，否则考虑交点纵
            y[i]=min(y[i-1],sum[i-1]-w[i]+1);
        }else{ // T1,T2 各自与 S 无交，再无贡献
            for(int j=i;j<=n;j++){
                tri[j]=tri[i-1];
                y[j]=y[i-1];
                sum[j]=sum[j-1];
            }
            break;
        }
    }
    cin>>z;
    for(int i=1,v=0,j,k,a,b,c,d;i<=q;i++){
        cin>>j>>c>>d;
        k=j-v*z,a=c-v*z,b=d-v*z;
        if(k<w[1]){
            if(!a&&!b){cout<<"Yes\n";v+=i;}
            else cout<<"No\n";
            continue;
        }
        int l=1,r=n,pos=1;
        while(l<=r){
            int mid=l+r>>1;
            if(w[mid]<=k)pos=mid,l=mid+1;
            else r=mid-1;
        }
        if(chk(a,b,pos)){cout<<"Yes\n";v+=i;}
        else cout<<"No\n";
    }
}