题解：P12646 [KOI 2024 Round 1] 升序

· · 题解

注意到当给定序列 X 之后我们可以根据每个点的操作次数得到一个序列 Y。这个 Y 就是每个位置的修改次数的上限，那么考虑当已知 Y 的情况下如何快速求解每个询问。

对于询问区间 [l,r]，可以知道询问时的 y_l 一定是 0，可以知道，当一个点的 Y 减少 1，那么他后面的一段非零连续段都可以减少一次操作。现在是第 l 个位置少操作了 Y_l 次，那么其后面的一段大于等于 Y_l 的连续段都可以减少 Y_l。这样我们跳到 l 后面第一个位置 i 满足 Y_i>Y_l，这个时候由于有上述性质，那么最后询问的 y_i 也是 0，那么变成子问题 [i,r] 的答案。那么当我们使用单调栈维护右侧第一个小于当前点的位置即可做到 O(1) 移动指针。

考虑指针的移动次数是什么级别的。发现如果后面的位置 i 比前面位置 j 的 Y 值少 1，那么在原序列 X 中 X_i 至少是 X_j 的两倍，这样才能满足条件。这样可以知道指针的移动次数是 O(\log V) 级别的。

现在考虑如何得到序列 Y。这是不能直接暴力模拟的，不如 X 会很大。我们可以用 Y_{i-1} 来计算 Y_i。于是有如下式子：

X_{i-1}\times 2^{Y_{i-1}}\leq X_i\times 2^{Y_i}

讨论一下 X_{i-1} 和 X_{i} 的大小关系，若 X_{i-1}>X_{i}，可以得到 2^{Y_i-Y{i-1}}\leq \frac{X_{i-1}}{X_i}。这是很好计算的。另一种情况同理。

这样可以做到 O(n\log V+q\log V) 的复杂度。

::::info[Code]


#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define int long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf ((int)1e18+10)
#else
#define inf ((int)1e9+10)
#endif
#define mid ((l+r)>>1)
#define rs now<<1|1
#define ls now<<1
using namespace std;
bool Mst;
const int Max=2.5e5+10;
const int mod=998244353;
const double eps=1e-9;

int val[Max],sum[Max],n,q,a[Max],to[Max];
int solve(int l,int r){
    int ans=sum[r]-sum[l-1];
    int v=val[l],las=l;
    while(1){
        v=val[las];
        int pos=to[las];
        if(pos>r)pos=r+1;
        ans-=(pos-las)*v;
        las=pos;if(las==r+1)break;
    }
    return ans;
}

void init(){
    stack<int>sta;
    for(int i=1;i<=n;++i){
        while(!sta.empty()&&val[sta.top()]>val[i]){
            to[sta.top()]=i;sta.pop();
        }
        sta.push(i);
    }
    for(int i=1;i<=n;++i)if(!to[i])to[i]=n+1;
}

vector<pii>V;
bool Med;
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;++i)a[i]=read();
    V.pb(mk(1,0));int res=1;
    for(int i=1;i<=35;++i){res*=2;V.pb(mk(res,i));}
    for(int i=2;i<=n;++i){
        if(a[i]>a[i-1]){
            int res=1.0*a[i]/a[i-1];
            auto it=upper_bound(V.begin(),V.end(),mk(res,inf))-V.begin()-1;
            int num=V[it].se;
            val[i]=max(0ll,val[i-1]-num);
        }
        else{
            int res=ceil(1.0*a[i-1]/a[i]);
            auto it=lower_bound(V.begin(),V.end(),mk(res,0ll))-V.begin();
            int num=V[it].se;
            val[i]=val[i-1]+num;
        }
        sum[i]=sum[i-1]+val[i];
    }
    init();
    for(int i=1;i<=q;++i){
        int l,r;
        l=read();r=read();
        if(l==r){cout << "0\n";continue;}
        cout << solve(l,r) << '\n';
    }

    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*

*/
::::info