题解：P9870 [NOIP2023] 双序列拓展

· · 题解

突然发现本题的一个非 Ad-hoc 套路做法。

首先如果 x_1\le y_1 那么拓展后只有 y 全大于 x 是有可能的，反之亦然。这里我们只考虑 x_1 > y_1，并尝试在拓展后使得 x 全大于 y。

把 x，y 序列差分，然后视为你当前有一个 HP 为 x 对应位置的值减 y 对应位置的值，且你的 HP 始终不能小于等于 0，也就是你初始有 x_1-y_1 点 HP，把 x_{i-1} 拓展到 x_i 会获得 x_i-x_{i-1} 点 HP（如果值为负则改为消耗绝对值点 HP），对于 y 序列类似操作。

问题转化为：给定一棵树（形态为根节点下面挂着一条长度为 n-1 的链和一条长度为 m-1 的链），除根节点外每个点有一只怪兽，打败它需要先消耗 a_i 点 HP，再恢复 b_i 点 HP，求初始拥有给定量 HP 的情况下从根节点出发按照最优策略能否打败所有怪兽。

发现这个问题严格弱于 HDU 6326 Monster Hunter，直接按照那题的做法做即可，类似的题还有 P7011 [CERC2013] Escape、QOJ 7520 Monster Generator。

具体地，a\le b 的显然比 a>b 的优，然后同样 a\le b 的显然 a 越小越优。考虑把问题倒过来看，那么 a>b 的倒过来看就变成了 a\le b 的情况了，所以 b 越大越优。

然后考虑一个节点，如果其子节点比它优，那么选它之后肯定还会选那个子节点，那就合并它和它的子节点，最后直接贪即可，树上的话还得注意一下合并子节点的顺序，以及用堆维护贪心，时间复杂度单 \log。

但这个题只需要类似链表维护合并，然后直接二路归并即可，时间复杂度 O(q(n+m))。

还有一个问题，本题中两个序列可以同时推进一格。但考虑如果两个都是“减少 HP”或者“增加 HP”的事件的话是等价的，如果两个不同的话，先进行“增加”事件再进行“减少”事件一定不劣于同时进行，所以可以直接做。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
struct node{int a,b;}x[N],y[N];
inline bool operator < (node &x,node &y){
    if((x.a<=x.b)&&(y.a>y.b))return 0;
    if((y.a<=y.b)&&(x.a>x.b))return 1;
    if(x.a<=x.b)return(x.a>y.a);
    return(x.b<y.b);
}
inline node operator + (node x,node y){
    node res;
    res.a=max(x.a,x.a-x.b+y.a),res.b=x.b+y.b-x.a-y.a+res.a;
    return res;
}
int c,n,m,q,a[N],b[N],r[N],kx,ky,ta[N],tb[N];
bool solve(int a[],int n,int b[],int m){
    if(a[1]<=b[1])return 0;
    node res={0,a[1]-b[1]};
    for(int i=2;i<=n;i++){
        int t=a[i]-a[i-1];
        if(t>=0)x[i]={0,t};
        else x[i]={-t,0};
    }
    for(int i=2;i<=m;i++){
        int t=b[i]-b[i-1];
        if(t>=0)y[i]={t,0};
        else y[i]={0,-t};
    }
    iota(r+1,r+n,2),r[n]=0;
    for(int i=n-1;i;i--)while(r[i]&&(x[i]<x[r[i]]))x[i]=x[i]+x[r[i]],x[r[i]]={0,0},r[i]=r[r[i]];
    iota(r+1,r+m,2),r[m]=0;
    for(int i=m-1;i;i--)while(r[i]&&(y[i]<y[r[i]]))y[i]=y[i]+y[r[i]],y[r[i]]={0,0},r[i]=r[r[i]];
    int tx=1,ty=1;
    while((tx<=n)||(ty<=m)){
        if(ty>m)res=res+x[tx++];
        else if(tx>n)res=res+y[ty++];
        else{
            if(y[ty]<x[tx])res=res+x[tx++];
            else res=res+y[ty++];
        }
    }
    return(!res.a)&&(res.b>0);
}
inline void work(){
    if(solve(a,n,b,m)||solve(b,m,a,n))cout<<1;
    else cout<<0;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>c>>n>>m>>q;
    for(int i=1;i<=n;i++)cin>>a[i],ta[i]=a[i];
    for(int i=1;i<=m;i++)cin>>b[i],tb[i]=b[i];
    work();
    while(q--){
        cin>>kx>>ky,memcpy(a,ta,sizeof(ta)),memcpy(b,tb,sizeof(tb));
        for(int i=1,p,d;i<=kx;i++)cin>>p>>d,a[p]=d;
        for(int i=1,p,d;i<=ky;i++)cin>>p>>d,b[p]=d;
        work();
    }
    return 0;
}