[JOISC 2024 Day1] 鱼 3 题解

· · 题解

观察性质题。下称“投喂 A 饲料”为“执行 A 操作”，B 饲料同理。

考虑暴力怎么做。显然一个 A 操作等价于令某个 C_i\leftarrow C_i-D，而最后能通过 B 操作完成的序列 C 必然单调不降（因为每次可以给一个后缀 +1，所以前面的数永远不会大于后面的）。

考虑另一种“暴力”，就是将询问离线，按 R 从小到大排序然后扫一遍过去，每次扫到一个新的 R，如果 C_{R-1}>C_R 就暴力往前更新，直到满足条件。

上面的这种暴力看起来很能找性质进行优化。观察到如果我们更新过了一对相邻的数，那么接下来不管怎么更新，它们的差不变！证明：每次更新都是对一个 C_i 进行 -D，考虑 \bmod D 的剩余系即可。于是考虑用一个栈维护还没有更新的位置（因为如果右边的不用更新左边的也不用更新），所以每次从栈顶开始暴力往下查有没有冲突，如果有直接更新中间一段的值，然后把栈顶删掉……均摊一下这种操作最多做 N 次。区间加区间和可以用线段树维护。于是做完了，时间复杂度 O(N\log N)。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
inline int ceil_div(int x,int y){
  return x/y+!!(x%y);
}
class segtree{
  private:
    int n;
    vector<pii> B;
    vector<int> S,T;
  public:
    inline void pushup(int u){
      S[u]=S[u<<1]+S[u<<1|1];
    }
    inline int size(int u){
      return B[u].second-B[u].first+1;
    }
    inline void pushdown(int u){
      S[u<<1]+=T[u]*size(u<<1),S[u<<1|1]+=T[u]*size(u<<1|1);
      T[u<<1]+=T[u],T[u<<1|1]+=T[u],T[u]=0;
    }
    segtree(int N){
      n=N,B.resize(n<<2),S.resize(n<<2),T.resize(N<<2);
      function<void(int,int,int)> build=[&](int u,int l,int r){
        if(B[u]=make_pair(l,r);l==r)return;
        int m=l+r>>1;
        build(u<<1,l,m),build(u<<1|1,m+1,r);
      };
      build(1,0,n-1);
    }
    inline void update(int u,int l,int r,int x){
      if(B[u].first>r||B[u].second<l)return;
      if(l<=B[u].first&&B[u].second<=r){
        T[u]+=x,S[u]+=x*size(u); return;
      }
      pushdown(u);
      update(u<<1,l,r,x),update(u<<1|1,l,r,x);
      pushup(u);
    }
    inline int query(int u,int l,int r){
      if(B[u].first>r||B[u].second<l)return 0;
      if(l<=B[u].first&&B[u].second<=r)return S[u];
      pushdown(u);
      return query(u<<1,l,r)+query(u<<1|1,l,r);
    }
}; // 线段树
main(){
  ios::sync_with_stdio(false);
  int n,d; cin>>n>>d;
  vector<int> c(n);
  for(auto &i:c)cin>>i;
  int q; cin>>q;
  vector<vector<pii> > Q(n);
  vector<int> R(q);
  for(int i=0;i<q;i++){
    int l,r; cin>>l>>r;
    Q[r-1].emplace_back(l-1,i);
  } // 把询问离线下来
  segtree t(n);
  auto get=[&](int p){return c[p]-t.query(1,p,p)*d;};
  stack<int> s;
  for(int i=0;i<n;i++){
    int r=i;
    while(!s.empty()){
      int l=s.top(),x=get(r-1),y=get(r);
      if(x<=y)break;
      t.update(1,l,r-1,ceil_div(x-y,d));
      r=l,s.pop();
    } // 弹栈顶，均摊 N 次
    s.emplace(r);
    for(auto [l,w]:Q[i])
      R[w]=(get(l)<0?-1:t.query(1,l,i));
  }
  for(int i:R)cout<<i<<'\n';
  return 0;
}