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

· · 题解

苹果的选取只与其重量 w_i 与 k 有关，不妨将 w 进行排序。
后续对苹果的选取若无特殊说明，均为 w_i 单调递增的选取。

研究一维，即 b=0 时，并按 k 递增时 k− 完美的 (a,0) 的情况，发现添加新的苹果 i 过程中的转移可视作下述过程。

将 (x,0) 视作一条射线上的一点，当 (x,0) 为可到达对时视其为有色的点，有色的点组成一条或多条线段，则添加新的苹果 i 到篮子中的过程相当于把有色点向正方向平移 w_i 后与原来的有色点共存。

此时 k− 完美的对 (a,0) 即为满足 \forall i\in[0,a],(i,0) 为有色的点的二元组。
可以发现这些有色的点连成了从点 (0,0) 开始到点 (a,0) 的一条线段。
对于上述射线中，初始有色的点为 (0,0)，在转移过程中若 w_i 是单调递增的，会发现当 \exists j<w_{i},(j,0) 非可到达对时，从苹果 i 开始的转移再也覆盖不到这个点 (j,0)。
因此令 j_{min}=\min j（j<w_i，且 (j,0) 非可到达对），\forall i<j_{min},(i,0) 均是 k− 完美的，\forall i>=j_{min},(i,0) 均不是 k− 完美的。

回到我们二维的情况，我们继续将 (x,y) 视作一个平面上的点，(x,y) 为可到达对为有色的点，k− 完美的二元组 (a,b) 对应的图形是一个矩形。
苹果可以放在两个篮子里面，因此有色图形可以向两个方向平移。
当 w_i 较小时，使有色图形为一个内部没有无色的点的连通块时，有色图形呈现等腰直角三角形状，任意点 (a,b) 在图形中时 (a,b) 均为 k− 完美的。
当 w_i 较大时，使有色图形仍为连通块但内部有无色的点时有色图形时，若右上角点为 (a,b) 矩形包含无色的点时 (a,b) 非 k− 完美的。
不妨把 k− 完美的点 (a,b) 全部标记，发现标记的点组成了转移前的等腰三角形后在两个方向上延伸了若干梯形的图形。
当 w_i 大到使有色点分为两个及以上的连通块时， k− 完美的点 (a,b) 不再增加。

至此，我们将对于给定 k 的 k− 完美的点 (a,b) 组成的图形绘制出来，判断给定的点 (x,y) 是否在上面即可。

空间复杂度为 O(n)。
时间上排序复杂度为 O(n\log n)，处理图形 O(n)，查询单次为 O(\log n)，总的时间复杂度为 O(n\log n+q\log n)。

代码如下。 

#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=3e5+10;
int n,q,z,pw,ptr;
long long w[MAXN],trlen[MAXN],tilen[MAXN],v;
int main(){
    scanf("%d%d",&n,&q);
    pw=n;
    for(int i=1;i<=n;++i){
        scanf("%lld",&w[i]);
    }
    sort(w+1,w+n+1);
    for(int i=1;i<=n;++i){
        if((w[i]<=(trlen[i-1]>>1)+1)&&tilen[i-1]==0){
            trlen[i]=trlen[i-1]+w[i];
            tilen[i]=0;
            ptr=i;
        }else if(trlen[i-1]+tilen[i-1]+1>=w[i]){
            trlen[i]=min(trlen[i-1],trlen[i-1]+tilen[i-1]+1-w[i]);
            tilen[i]=trlen[i-1]+tilen[i-1]+w[i]-trlen[i];
        }else{
            pw=i-1;
            break;
        }
    }
    scanf("%d",&z);
    for(int i=1;i<=q;++i){
        long long k,a,b;
        scanf("%lld%lld%lld",&k,&a,&b);
        k-=1ll*v*z;a-=1ll*v*z;b-=1ll*v*z;
        int p=upper_bound(w+1,w+pw+1,k)-(w+1);//可用的物品 w[1]~w[p] 
        if(a>b)swap(a,b);//保证a<=b
        if(p<=ptr){
            if(a+b<=trlen[p]){
                v+=i;
                puts("Yes");
            }else puts("No");
        }else{
            //lower_bound升序，在降序的数组中不可直接使用 
            int pp,l=ptr,r=p;
            while(l<r){
                #define mid ((l+r+1)>>1)
                if(trlen[mid]>=a){
                    l=mid;
                }else r=mid-1;
            }
            pp=l;
            if(trlen[pp]>=a&&a+b<=tilen[pp]+trlen[pp]){
                v+=i;
                puts("Yes");
            }else puts("No");
        }
    }
    return 0;
}