题解：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)

的复杂度。

Code

CPP

#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

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

文章操作

相关推荐

评论

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