P11110 解题报告

· · 题解

前言

好玩题好玩题好玩题好玩题好玩题好玩题好玩题好玩题好玩题好玩题好玩题好玩题，你去和 P11051 [IOI 2024] 树上代价坐一桌吧。

思路分析

这题也太难了，就算 a,b 中有一个是 0，剩下的也是个背包，貌似没啥能做的。

不妨先想的简单点考虑下 b=0。

此时他就是一个背包。

但这题有一个比较强的限制就是说 \forall x\in[0,a]，都需要可以取到。

考虑下我们的背包，大致就像这样：

1,1,1,0,0,0,0,0,0,0

其中 1 代表能取到，0 代表取不到。

然后根据经典背包转移，加入一个新的物品就是平移若干位然后或在一起：

1,1,1,0,0,1,1,1,0,0

类似于这样。

那我们现在需要的就是维护第一段连续 1 的末尾。

比较自然的想法是将物品按照重量从小到大加进来，这样可以维护一个单调性。

比如这个例子：

1,1,0,0,0,0

加入 w=3 的物品就会变成：

1,1,0,1,1,0

然后他中间就断开了。

但如果你这个时候再加入 w=2 的物品，你就会发现他中间已经断开的 0 又连上了，非常不好。

所以我们按照 w 从小到大加入物品。

那我们注意到，当某一个时刻出现 0 断开的时候（例如上面那个 w=3 加入），会有什么？

会有第一段连续 1 长度 l<w。

此时后面的物品重量 w' 必然满足 w'\ge w>l，也就是不可能把这个 0 的位置填上，也就是他永远断开了。

所以我们只需要维护下每个物品加入的时候有没有断开，没断开当前的最右就可以可以取到的最大值，不然就是断开点为最大值。

预处理一遍，查询的时候找到对应的可用物品状态判定就可以了。

然后我们来考虑 b\not=0 的情况。

比较自然的，我们将刚刚那个一维的背包，拓展成二维的。

定义 f_{x,y} 为 a=x,b=y 在不相交的情况下能不能取到。

那么你怎么转移这个东西呢？

因为要求不相交，所以转移就是 f_{x,y}\leftarrow f_{x-w,y}\operatorname{or}f_{x,y-w}。

同样的，我们画图来刻画这个东西。

因为我们还是没用上这个题最强的限制：全部符合条件。

画成一个二维的图，我们会发现如果都符合条件，他大概会长成一个等腰三角形： 然后我们加入一个新的物品重量为 w。 就变成了这样一个东西。

在两个方向上的转移都可以看做是平移三角形，然后就会得到这样一个东西。

我们注意到其实我们只在意整点，所以只要 w\le \lfloor\frac{s}{2}\rfloor+1，就可以保证这个等腰三角形仍然是完整的。

现在我们需要考虑如果不完整会变成什么样？

首先最为简单的是 w\ge s+1，此时完全无交。

考虑一个取不到的点 x,y，即 f_{x,y}=0 对于整个状态的限制，就是 x,y 以及他右上角的点状态都为 0（因为每个点是考虑他到原点的一个子矩阵必须全是 1）。

那么我们发现这样的情况下，除了先前等腰三角形里的部分，剩下的部分状态全部为 0 了。

也就是不再会对答案有任何的影响了。

再接下来我们考虑 \lfloor\frac{s}{2}\rfloor+1<w<s+1 的情况。

画图，我们可以得到这样： 其中涂红的那个小三角就是取不到的部分。

考虑他的约束，其实就会成这样： 红色这一块都是取不到的。

这说明什么，这说明他再平移也不会新增新的限制了（对于这个小三角形而言）

就是说我们只需要考虑每个小三角形出来的时候产生的贡献就好了。

那这说明什么，说明最后的可行区域大概形如： 显然他肯定是关于 y=x 对称的，然后就是若干个 x+y=k 的图像拼在一起。

记录下断点和函数那个 k 就可以了。

查询的时候直接找到对应的函数状态二分下就好了。

具体的我们知道其中一个 x+y=k 对于物品 i 即以后的才会生效，然后你这样去二分就好了。

代码

不想自己写二分 be like。

#include<bits/stdc++.h>
namespace Hoks
{
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid ((l+r)>>1)
    #define int long long
    using namespace std;
    const int N=1e6+10,B=2010,M=21,V=1e6,mod=1e9+7,INF=3e18;
    int n,m,L,R,z,a[N];pair<int,int>b[N];
    namespace Fast_IO
    {
        static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
        #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
        inline int read()
        {
            int x(0),t(1);char fc(getchar());
            while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
            while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
            return x*t;
        }
        inline void flush(){fwrite(out,1,length,stdout);length=0;}
        inline void put(char c){if(length==9999999) flush();out[length++]=c;}
        inline void put(string s){for(char c:s) put(c);}
        inline void print(long long x)
        {
            if(x<0) put('-'),x=-x;
            if(x>9) print(x/10);
            put(x%10+'0');
        }
        inline bool chk(char c) { return !(c=='.'||c=='#'||c=='('||c==')'||c==':'||c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'); }
        inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
        inline void rd(char s[],int&n)
        {
            s[++n]=getchar();
            while(chk(s[n])) s[n]=getchar();
            while(ck(s[n])) s[++n]=getchar();
            n--;
        }
    }
    using namespace Fast_IO;
    inline void solve()
    {
        R=n=read(),m=read();
        for(int i=1;i<=n;i++) a[i]=read();
        z=read();sort(a+1,a+1+n);
        for(int i=1,x=0,y=0,w;i<=n;i++)
        {
            if(a[i]<=x/2+1&&!y) b[i]={x+a[i],0},L=i;
            else if(a[i]<=x+y+1) w=min(x,x+y+1-a[i]),b[i]={w,x+y+a[i]-w};
            else{R=i-1;break;}x=b[i].first,y=b[i].second;
        }for(int i=1;i<=n;i++) b[i].first*=-1;
        for(int i=1,k,x,y,v=0;i<=m;i++)
        {
            k=read()-v*z;x=read()-v*z;y=read()-v*z;
            if(x>y) swap(x,y);
            int cur=upper_bound(a+1,a+1+R,k)-a-1;
            if(cur<=L)
            {
                if(x+y<=-b[cur].first) v+=i,put("Yes\n");
                else put("No\n");continue;
            }auto p=upper_bound(b+L,b+cur+1,make_pair(-x,INF))-b-1;
            auto [w1,w2]=b[p];w1*=-1;
            if(w1>=x&&w1+w2>=x+y) v+=i,put("Yes\n");
            else put("No\n");
        }
    }
    inline void main()
    {
        int T=1;
        // T=read();
        while(T--) solve();
        genshin:;flush();
    }
}
signed main()
{
    Hoks::main();return 0;
}