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

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

A 掉这道题才发现自己是第 9 个 A 的，抓紧来发篇题解。

题目传送门

https://www.luogu.com.cn/problem/P12646https://www.luogu.com.cn/problem/P12646

题意理解

一看到这道题，我发现其实就是 [KOI 2024 Round 1] 加倍的加强版，多了一个区间查询。

题意：给你一个长度为 $M$ 的正整数序列 $X_1,X_2, \dots,X_M$，给你 $l,r$，每次操作可以把 $X_i$ 乘 $2$，求出让 $X_l, X_{l+1}, \dots, X_r$ 变为升序的最小操作次数。

解题思路

简化一下，对于 $\forall i，X_i \leq X_{i+1} \times 2^{c_i}$，我们可以把每个 $c_i$ 存下来，如果 $X_i$ 乘了 $1$ 次，那么后面的 $X_j$ 都会多乘 $1$ 次，所以前面的会对后面的产生影响，那么就要计算前缀和，它们的前缀和加起来就是答案————————吗？

举个例子，序列 $3,1,5,1,5$ ，其对应的 $c_i$ 分别为 $2,0,3,0$，前缀和就是 $2,2,5,5$，结果为 $14$，很明显是不对的。

思考一下，发现需要计算每个 $X_i$ 可以抵消掉后面的次数，那么这个 $c_i$ 就分别是 $2,-2,3,-2$，前缀和加起来就是 $6$，这才是正确的。

But，序列 $1,10,5$，$c_i$ 为 $-3,1$，但是前缀和加起来就是 $-5$，很明显的错误，所以如果前缀和变成了负数，要令其变为 $0$。

综上，我们可以归纳出，$c_i$ 是 $X_i$ 和 $X_{i+1}$ 之间的变化，前缀和 $S_i = \max(0, S_{i-1}+c_i)$，对于区间 $l,r$，答案就是 $\sum_{i=l}^r S_i$，如果每次跑一遍累加一下，复杂度是 $O(MQ)$，只能得到 12pts。

考虑优化，将 $\sum_{i=l}^r S_i$ 拆开，得到 $\sum^r_{i=l} \sum^i_{j=l} c_j$，交换两个求和符号得 $\sum^r_{j=l} \sum^r_{i=j} c_j$，再化简一下是 $\sum^r_{j=l}(r-j+1)c_j$，将 $(r+1)$ 提出来得 $(r+1)\sum^r_{j=l} c_j-\sum^r_{j=l}j\times c_j$，所以这就是答案的式子，可以用两个前缀和维护，就可以实现 $O(1)$ 查询，但是由于 $S_i = \max(0, S_{i-1}+c_i)$，设 $R_i=R_{i-1}+c_i$，所以这个式子只能用于 $R_i ≥ 0$ 的区间。

对于 $R_i < 0$ 的情况，可以考虑分段，将连续的 $R_i(R_i ≥ 0)$ 分为一段，由于这一段 $R_i ≥ 0$，所以就可以用 $(r+1)\sum^r_{j=l} c_j-\sum^r_{j=l}j\times c_j$ 算出每一段的答案，再拼成 $l,r$ 的区间。

如何实现呢？我们知道，如果 $R_j<R_i (j>i)$，那么这一段就是 $<0$ 的，所以需要找到第一个比 $R_i$ 小的 $R_j$，可以用单调栈维护，存入 $nxt_i$ 表示第一个比 $R_i$ 小的 $R_j$ 的 $j$。

代码实现

复杂度大约是 $O(Q)$，注意开 long long

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=3e5+10;
int n,q,a[N],c[N],sum,cnt,s[N],ss[N],nxt[N];
stack<int> st;
int getsum(int l,int r){
	return (r+1)*(s[r]-s[l-1])-(ss[r]-ss[l-1]);
}
void zj(){
	//预处理nxt[i]
	for(int i=n;i>=0;i--){
		while(!st.empty()&&s[st.top()]>=s[i]) st.pop();
		if(!st.empty()) nxt[i]=st.top();
		else nxt[i]=n+1;
		st.push(i);
	}
	while(q--){
		int l,r,ans=0;
		cin>>l>>r;
		if(l==r){
			cout<<0<<endl;
			continue;
		}
		int i=l-1;
		while(i<r){
			ans+=getsum(i+1,min(nxt[i]-1,r-1));//计算每一段的和
			i=nxt[i];//跳到下一段
		}
		cout<<ans<<endl;
	}
}
signed main(){
	cin.tie(0)->ios::sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
    //计算 c[i]
	for(int i=1;i<n;i++){
		if(a[i+1]>a[i]){
			int x=a[i];
			while(x*2<=a[i+1]){
				x*=2;
				c[i]--;
			}
		}else{
			int x=a[i+1];
			while(x<a[i]){
				x*=2;
				c[i]++;
			}
		}
	}
	for(int i=1;i<=n;i++) s[i]=s[i-1]+c[i];//s[i]就是题解中的R[i]
	for(int i=1;i<=n;i++) ss[i]=ss[i-1]+c[i]*i;
	zj();
	return 0;
}

本文由AirTouch编写，采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。