专栏文章

题解：P12646 [KOI 2024 Round 1] 升序 & P12642 [KOI 2024 Round 1] 加倍

yylch
P12646题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mio8iyam
此快照首次捕获于
2025/12/02 15:06
3 个月前
此快照最后确认于
2025/12/02 15:06
3 个月前
查看原文
首先先来看一下这道题的弱化版：P12642 [KOI 2024 Round 1] 加倍。
考虑对于每个 ai>ai+1a_i>a_{i+1} 预处理出一个 cic_{i} 数组，表示最小的 cic_{i} 使得：ai+1×2ci≥aia_{i+1} \times 2^{c_i} \ge a_i。
我们发现这个 cic_i 是可以继承的，即对于某个（另一个）aj>aj+1a_j>a_{j+1}，在预处理出最小的 xx 使得 aj+1×2x≥aja_{j+1} \times 2^x \ge a_j 后，cjc_j 应该等于 cj−1+xc_{j-1}+x。这是因为之前 cj−1c_{j-1} 乘的影响也会作用于此。
所以我们要对 cic_i 处理一个前缀和。
但还没完，我们会发现一个问题：对于原本就符合条件的 ai≤ai+1a_i \le a_{i+1}，如果 ai+1a_{i+1} 足够大，大到 ai×2ci≤ai+1a_i \times 2^{c_i} \le a_{i+1}，那么我们之前的修改前缀和相当于是“多了”。
所以我们还要考虑处理出一个大小为负的 ci+1c_{i+1} 用于抵消之前并不必要的影响。具体地，找到最大的 xx 满足 ai×2x≤ai+1a_i \times 2^x \le a_{i+1}，则 ci=−xc_i=-x。
然后考虑如何求答案，我们要先用前缀和“还原”cc 数组（因为之前说过 cc 数组的影响是顺延的）：si=∑k=1icks_i = \sum_{k=1}^i c_k。然后再对 ss 数组求和：ans=∑i=1nsians=\sum_{i=1}^n s_i。
还有一个细节：可能会出现某个 si<0s_i<0，这属于没有贡献的情况，不能胡乱计入。所以前缀和应该再和 00 取 max⁡\max：si=max⁡{0,si−1+ci}s_i=\max\{0, s_{i-1}+c_i\}。
CPP
void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	for(int i = 1; i <= n - 1; i ++){
		if(a[i] > a[i + 1]){
			int t = a[i + 1];
			while(a[i] > t) t *= 2, c[i] ++;
		}
		else{
            int x = 0, t = a[i];
            while(t * 2 <= a[i + 1]){
              t *= 2, x ++;
            }
            c[i] = -x;
		}
		s[i] = max(0LL, s[i - 1] + c[i]);
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++){
		ans += s[i];
	}
	cout << ans << '\n';
}
下面是加强版（本题）。
还是接着弱化版思路中的 cc 数组考虑。对于区间 [l,r][l,r]，我们最终的答案是这样的：
∑i=lrmax⁡{(∑j=licj),0}\sum\limits_{i=l}^{r} \max\left\{ \bigg(\sum\limits_{j=l}^i c_j \bigg), 0 \right\}
或
∑i=lrmax⁡(si−sl−1,0)\sum_{i=l}^{r} \max(s_i - s_{l-1}, 0)
和 00 取 max⁡\max 其实很烦人。这里先考虑如果没有这一层取 max⁡\max 的话应该怎么算，可以交换求和符号并结合前缀和进行化简：
∑i=lr∑j=licj=∑j=lr∑i=jrcj=∑j=lr(r−j+1)cj=∑i=lr(r−i+1)ci=∑i=lr((r+1)⋅ci−i⋅ci)=(r+1)×∑i=lrci−∑i=lri⋅ci\begin{align*} \sum_{i=l}^{r} \sum_{j=l}^i c_j &= \sum_{j=l}^{r} \sum_{i=j}^{r} c_j \\ &= \sum_{j=l}^{r} (r-j+1)c_j \\ &= \sum_{i=l}^{r} (r-i+1)c_i \\ &= \sum_{i=l}^{r} \big((r+1) \cdot c_i - i \cdot c_i \big) \\ &= (r+1) \times \sum_{i=l}^{r} c_i - \sum_{i=l}^{r} i \cdot c_i \end{align*}
解释一下第一步：根据初始公式可知 i≥ji \ge j 且 i≤ri \le r，把 jj 挪到外面后内层 ii 的求和范围就出来了。
显然只要预处理出 cic_i 的前缀和与 i⋅cii \cdot c_i 的前缀和就能做到 O(1)O(1) 求。
注：在计算时请搞清楚左右端点的包含关系，以及我们当前的计算公式的针对情况、当前算的 cc 数组的下标范围等边界情况。在我的代码里会注明。
然后看正常情况。我们的瓶颈就在于和 00 取 max⁡\max 实际上会导致求和中断一段（这一段里的前缀和都小于等于 00），然后再接着求。所以我们会很自然地想到能否把非零段都提取出来，然后用上面说的方法快速计算。
考虑预处理出对于所有的 i∈[1,n]i \in [1,n] 右边第一个会求和中断的位置 pip_i，这样就能从有值的位置跳到距离最近的断点（最后一个前缀和不为 00 的位置），就能做了。这其实是一个类似“跳表”的结构。
但时间复杂度呢？或者说， 对于每个询问的 [l,r][l,r] 最多能跳多少次？感觉像是 log⁡\log 的，实际也的确如此。考虑什么时候会出现 si<0s_i<0，一定是前一个数比后一个数大了至少两倍，这样才会出现 cc 是负数用来抵消的情况。而 aa 数组的值域是 10910^9，也就是说我们最多只会跳 log⁡2109\log_2 10^9 次。
时间复杂度 O(n+qlog⁡w)O(n + q \log w)，ww 是 aia_i 的值域。
CPP
#include <bits/stdc++.h>
#define int long long // ll！！！
using namespace std;
const int maxn = 3e5 + 7;

int n, q, a[maxn], c[maxn], p[maxn], s[maxn], s2[maxn];
stack<int> st;

void solve()
{
	cin >> n >> q;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	
	// 统计c数组
	for(int i = 1; i <= n - 1; i ++){
		if(a[i] > a[i + 1]){
			int t = a[i + 1];
			while(a[i] > t) t *= 2, c[i] ++;
		}
		else{
			int x = 0, t = a[i];
			while(t * 2 <= a[i + 1]){
				t *= 2, x ++;
			}
			c[i] = -x;
		}
	}
	
	// 预处理前缀和
	for(int i = 1; i <= n; i ++){
		s[i] = s[i - 1] + c[i];
		s2[i] = s2[i - 1] + i * c[i];
	}
	
	// 预处理p[i]
	for(int i = n; i >= 0; i --){
		while(!st.empty() && s[st.top()] >= s[i]) st.pop(); // 找右边第一个小于s[i]的元素
		p[i] = !st.empty()? st.top() : n + 1; // 如果没有，就赋值n+1
		st.push(i);
	}
	
	auto sum = [&](int l, int r){ // 快速计算非零的区间前缀和
		return (r + 1) * (s[r] - s[l - 1]) - (s2[r] - s2[l - 1]);
	};
	
	while(q --){
		int l, r; cin >> l >> r;
		if(l == r){
			cout << 0 << '\n'; continue;
		}
		int ans = 0;
		int i = l - 1; // 我们默认i是前缀和<0的位置，也就是i+1才是前缀和非0的位置。所以注意i从l-1开始。
		while(i <= r - 1){ // 有效的范围应该是l ~ r-1，因为c[r]指的是位置r对r+1的操作次数，不计入在内
			ans += sum(i + 1, min(p[i] - 1, r - 1));
			i = p[i];
		}
		cout << ans << '\n';
	}
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...