鱼 3 / Fish 3 JOIST 2024

[JOIST 2024] 鱼 3 / Fish 3

[JOIST 2024] 鱼 3 / Fish 3。

定义一个序列 $a$ 的权值 $f(a)$ 为：

• 令 $p=0$。
• 重复执行以下操作，直到序列 $a$ 单调不降：
  • $p\leftarrow p+1$。
  • 选择一个 $1\le x\le n$，令 $a_x\leftarrow a_x-D$。
• 若 $p$ 有限，则 $f(a)=\min\{p\}$；否则，$f(a)=-1$。

给定序列 $a$，多次询问，每次给出一个 $l,r$，求 $f(a[l:r])$。

$n,m\le3\times10^5$；$a_i,D\le10^{12}$。

神秘性质题。

首先考虑只有一个询问时的做法。此时我们有一个简单的贪心思路：$a_i$ 的操作次数应该为：

$$\max\{0,\lceil\frac{a_i-\min_{j>i}\{a_j\}}{D}\rceil\}$$

这样我们就可以 $\mathcal{O}(n^2)$ 的解决多次询问。

接下来如果你考虑数据结构，那么大概率很麻烦。

有一个简单的小性质：如果相邻的两个数 $x,y$ 满足 $0\le y-x< D$，那么在以后，新加入的数，如果影响到了 $y$ 使得 $y$ 下降了，则 $x$ 必然也会下降。正确性显然。

换句话说，$y-x$ 为定值。

考虑利用这个性质：什么情况下会有 $0\le y-x< D$？要么初始时已经这样，要么一开始 $x>y$，然后操作 $x$ 使得 $x\le y$（正确性可以由贪心证明，因为再下降 $x$ 不优）。

于是，我们得出结论：一起操作后的相邻的两个数以后必然差不变。

于是现在的问题就好解决了：我们只需要将所有询问离线下来扫描线，过程中维护一个栈，表示哪些相邻的数还没有一起操作过。那么每次操作栈顶时，只需要执行一个区间（栈顶到当前操作点）的减法即可。

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=300100;
int n,D,m,a[N],ans[N];
struct BIT{
    int c[N];
    void init(int n){for(int i=1;i<=n;i++)c[i]=0;}
    void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}
    int query(int x,int cnt=0){for(;x>=1;x-=x&-x)cnt+=c[x];return cnt;}
}A,B;
void add(int l,int r,int x){
    A.add(l,x),B.add(l,x*(l-1));
    if(r+1<=n)A.add(r+1,-x),B.add(r+1,-x*r);
}
int query(int l,int r){
    return r*A.query(r)-(l-1)*A.query(l-1)-B.query(r)+B.query(l-1);
}
int get(int x){return a[x]-query(x,x)*D;}
using pii=pair<int,int>;
vector<pii>v[N];
int s[N],top;
signed main(){
    scanf("%lld%lld",&n,&D);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    A.init(n),B.init(n);
    scanf("%lld",&m);
    for(int i=1,l,r;i<=m;i++){
        scanf("%lld%lld",&l,&r);
        v[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++){
        int r=i;
        while(top){
            int l=s[top],x=get(r-1),y=get(r);
            if(x<=y)break;
            add(l,r-1,(x-y+D-1)/D);
            r=l,--top;
        }
        s[++top]=r;
        for(pii u:v[i])
            ans[u.second]=get(u.first)<0?-1:query(u.first,i);
    }
    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
    return 0;
}

什么叫我发现了性质但是我却往大数据结构方面去想了。

::::