题解：P16370 [OOI 2026] Monsters and Swords

dyc2022 · 2026-10-15 17:10:14 · 题解

更好的阅读体验

来讲一个非常自然的 O(n \log^2 n) 做法，跑得几乎和单 \log 一样快。冥想了一节文化课就想明白了！

考虑转为一个最优化问题：如果我能求出整个过程中至少花费的钱数 t，那么判定是容易的：只需要判断 x + \sum r_i 是否 \ge t 即可，其中前者是我们全过程的收益。

那么这题本质上是要把所有怪物分段，每一段用一把剑来消灭。假设该段内怪物的 h_i 的最大值为 mx，那么显然我们会选择一把攻击力 \ge mx 且价格最低的剑。假设攻击力 \ge j 且价格最低的剑价格为 v(j)，sum_i 表示 r 数组的前缀和。由此考虑一个 dp：f_i 表示消灭 1 \sim i 的怪物最少花费多少钱。则有转移

\begin{gather} f_i = \max_{\substack{i - j \le k \\ x + sum_j - f_j \ge \operatorname{cost}(i, j)}} \{f_j + \operatorname{cost}(i, j)\} \nonumber \\ \operatorname{cost}(i, j) = v\left(\max_{x = j+1}^i h_x\right) \nonumber \end{gather}

简单解释一下 x + sum_j - f_j \ge \operatorname{cost}(i, j) 是什么意思：当我们消灭完前 j 个怪物的时候我们收益为 x + sum_j，并会损失 f_j，此外还要额外损失 \operatorname{cost}(i, j) 来购买一个剑处理 (j, i] 的区间。因此需要保证 x+sum_j - f_j - \operatorname{cost}(i, j) \ge 0，因为我们任何时刻手中的钱数都要求非负。至此可以做到 O(n^2)。

接下来我们优化这个 dp。发现我们的 dp 转移的 j 需要满足的条件和转移方程中都有 \operatorname{cost}(i, j) 这一项，而 \operatorname{cost}(i, j) 是仅和 (j, i] 区间内 h 的最大值有关的，这启发我们在笛卡尔树上考虑，换言之，考虑极值分治。

现在假设考虑区间 [l, r]，区间最大值的位置为 mid，我们希望完成所有 l \le j+1 \le mid \le i \le r 的 i, j 的转移。

但是极值分治并没有和直接按照中点分治那样优良的性质，因为极值分治的分治树可能很高，如果每一次都付出 O(r-l) 的代价那么最坏情况下就是 O(n^2)，单调递增的序列就可以卡到这个上界。但是如果我们每次枚举量是 O(\min(r-mid, mid-l))，那么总枚举量就是 O(n \log n)，因为考虑序列上的某个位置，如果它在分治树上的某个节点被枚举到了，说明从这个节点往上走一步，其父亲的区间长度相较于当前节点会翻倍，因此每个节点至多被枚举 O(\log n) 次。这也是启发式合并在二叉树上的特殊情形。

因此只需要对 r - mid 和 mid - l 的大小关系分类讨论。注意由于我们处理的转移全部跨过 mid，因此下文中 \operatorname{cost}(i, j) 全部当做定值处理。

若 r - mid < mid - l，则我们直接枚举 i，查询最优的 j 来更新 f_i。

那么我们需要查询满足 i - j \le k 且 x + sum_j - f_j \ge \operatorname{cost}(i, j) 的最小的 f_j。容易发现 f 单调不降，因此查询出满足上式的最小 j 即可。我们维护一个线段树，在 j 位置存储 x + sum_j - f_j 的值，线段树上二分出第一个 \ge \operatorname{cost}(i, j) 的位置即可。
若 r - mid \ge mid - l，则我们枚举 j，处理每个 j 对一段区间内的 f_i 的贡献。

那么首先这个 j 也要满足 x + sum_j - f_j \ge \operatorname{cost}(i, j)。在此基础上，这个 j 会对所有 i \isin [mid, r]，且 i - j \le k 的 i 产生贡献，贡献显然是 f_j + \operatorname{cost}(i, j)。则维护一个支持区间取 \min 单点查询的数据结构即可，在我的实现中选用了线段树。

至此问题得到解决，复杂度为分治的一只 \log 乘上数据结构的一只 \log，即 O(n \log^2 n)。实测分治的 \log 常数极小，可以轻松通过。

#include<bits/stdc++.h>
#define endl '\n'
#define N 500006
using namespace std;
using i64=long long;
constexpr i64 INF=2e15;
template <class T1,class T2> inline void chkmin(T1 &x,T2 y) {x=x<y?x:y;}
template <class T1,class T2> inline void chkmax(T1 &x,T2 y) {x=x<y?y:x;}
int n,m,k,x,maxn,a[N],b[N],suf[N],cost[N];
int tp,ch[N][2],stk[N],val[N];
i64 f[N],sb[N];
pair<int,int> c[N];
struct Segtree1 { // 单点修改，区间查 min
  i64 tree[N<<2];
  void build(int p,int l,int r)
  {
    tree[p]=-INF; if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
  }
  void update(int p,int l,int r,int k,i64 x)
  {
    if(l==r)return tree[p]=x,(void)0;
    int mid=l+r>>1;
    k<=mid?update(p<<1,l,mid,k,x):update(p<<1|1,mid+1,r,k,x);
    tree[p]=max(tree[p<<1],tree[p<<1|1]);
  }
  int find(int p,int l,int r,i64 x)
  {
    if(l==r)return l;
    int mid=l+r>>1;
    return tree[p<<1]<x?find(p<<1|1,mid+1,r,x):find(p<<1,l,mid,x);
  }
  void find(int p,int l,int r,int L,int R,i64 x,int &res)
  {
    if(res!=-1)return;
    if(L<=l&&r<=R)
    {
      if(tree[p]>=x)res=find(p,l,r,x);
      return;
    }
    int mid=l+r>>1;
    if(L<=mid)find(p<<1,l,mid,L,R,x,res);
    if(R>mid)find(p<<1|1,mid+1,r,L,R,x,res);
  }
} T1;
struct Segtree2 { // 区间 chkmin，单点查询
  i64 tree[N<<2];
  void build(int p,int l,int r)
  {
    tree[p]=INF; if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
  }
  void update(int p,int l,int r,int L,int R,i64 x)
  {
    if(L<=l&&r<=R)return chkmin(tree[p],x);
    int mid=l+r>>1;
    if(L<=mid)update(p<<1,l,mid,L,R,x);
    if(R>mid)update(p<<1|1,mid+1,r,L,R,x);
  }
  i64 query(int p,int l,int r,int k,i64 x)
  {
    chkmin(x,tree[p]); if(l==r)return x;
    int mid=l+r>>1;
    return k<=mid?query(p<<1,l,mid,k,x):query(p<<1|1,mid+1,r,k,x);
  }
} T2;
void solve(int mid,int l,int r)
{
  if(l>r)return;
  solve(ch[mid][0],l,mid-1);
  if(r-mid<mid-l)
    for(int i=mid;i<=r;i++)
    {
      int lb=max({0,l-1,i-k}); if(lb>=mid)break;
      int p=-1; T1.find(1,0,n,lb,mid-1,cost[mid],p);
      if(p!=-1)chkmin(f[i],f[p]+cost[mid]);
    }
  else for(int i=max(0,l-1);i<=mid-1;i++)
    {
      if(i+k<mid||x+sb[i]-f[i]<cost[mid])continue;
      T2.update(1,0,n,mid,min(i+k,r),f[i]+cost[mid]);
    }
  chkmin(f[mid],T2.query(1,0,n,mid,INF));
  T1.update(1,0,n,mid,x+sb[mid]-f[mid]);
  solve(ch[mid][1],mid+1,r);
}
main()
{
  scanf("%d%d%d%d",&n,&m,&k,&x);
  for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i],&b[i]),chkmax(maxn,a[i]),sb[i]=sb[i-1]+b[i];
  for(int i=1;i<=m;i++)scanf("%d%d",&c[i].first,&c[i].second);
  sort(c+1,c+1+m),suf[m+1]=2e9;
  if(maxn>c[m].first)return printf("No\n"),0;
  for(int i=m;i;i--)suf[i]=min(suf[i+1],c[i].second);
  for(int i=1;i<=n;i++)
  {
    cost[i]=suf[lower_bound(c+1,c+1+m,make_pair(a[i],0))-c];
    while(tp&&a[i]>val[tp])ch[i][0]=stk[tp--];
    if(tp)ch[stk[tp]][1]=i;
    stk[++tp]=i,val[tp]=a[i];
  }
  for(int i=0;i<=n;i++)f[i]=INF;
  T1.build(1,0,n),T2.build(1,0,n),f[0]=0,solve(stk[1],0,n);
  printf(f[n]<=x+sb[n]?"Yes\n":"No\n");
  return 0;
}