CF878E Numbers on the blackboard 题解
Links
Description
给出 \(n\) 个数字，每次询问一个区间 \([l,r]\)，对这个区间内部的点进行如下操作。
- 每次操作可以合并相邻两个数 \(x,y\)，用 \(x+2y\) 替换它们。
对于每次询问，输出当最后只剩下一个数字时，这个数字的最大值。询问互相独立，答案对 \(10^9 + 7\) 取模。
Solution
我们考虑把整个区间从右向左依次合并答案是什么样的。
- 第一次合并 \(nums_{r - 1} + 2 \times nums_{r}\)。
- 第二次合并 \(nums_{r - 2} + 2 \times \left (nums_{r - 1} + 2 \times nums_{r} \right)\)。
- \(\cdots\)
- 最后一次 \(nums_{l} + 2 \times \left (nums_{l + 1} + 2\times ( nums_{l + 2} + \cdots )\right)\)
可以看出，对于每一个 \(nums_{i}\)，对答案的贡献都是 \(2^{k} (k \geq 0)\)，并且 \(\forall i \in [1,n-1]\)，\(k_{i + 1} = k_{i} + 1\)。
那么如果我们不是这样合并的是否还有这样的性质呢？考虑把合并的区间分成从右向左按顺序合并的若干段，易证每段仍符合该性质。合并两段的时候会发生什么呢，可以想到是将右侧一段的贡献整个乘以 \(2\)，也就是将右侧段的 \(k\) 全部加一。
因此，无论我们如何合并，最终对于整个区间每个数所乘的系数是一定的，系数变化如下（括号表示不一定存在）。即一个从 \(0\) 开始的串和一些从 \(1\) 开始的串。
\[0,1,\cdots,1,(2),\cdots,1,(2),\cdots \]想让最终结果尽可能大，可以考虑贪心。
假设当前决策到第 \(i\) 个数，\(i - 1\) 所在的块长度为 \(len\)。
- 若 \(nums_{i} < 0\)，选择不合并，单独开出来一个块，系数为 \(2^{0} = 1\)。
- 若 \(nums_{i} \ge 0\)，选择合并，系数为 \(2^{len}\)。
- 若合并后使得该块变为正的，代表后面的可以抵消中间负数的影响，继续向前合并。
可以看出上面的过程存储每一个块类似于栈，因此我们用栈来模拟这个过程。直接实现复杂度为 \(\Omicron(nq)\)，我们可以离线操作，将操作按照 \(r\) 排序，再利用二分查找 \(l\) 右侧的第一个块，单独减去 \(l\) 左侧多出来的贡献即可。时间复杂度变为 \(O(n \log n)\)。合并过程中，如果遇到极大的块，不能直接继续合并，否则轻松炸 long long，特判这种情况，将这个块设为极大值即可。
Codes
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 410101
#define mo 1000000007
void read(int &p)
{
int k = 1;
p = 0;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')
{
k = -1;
}
c = getchar();
}
while(c >='0' && c <= '9')
{
p = p * 10 + c - '0';
c = getchar();
}
p *= k;
return ;
}
void write_(int x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9)
{
write_(x / 10);
}
putchar(x % 10 + '0');
}
void writesp(int x)
{
write_(x);
putchar(' ');
}
void writeln(int x)
{
write_(x);
puts("");
}
int n,m;
int lg2[max_n],nums[max_n],sum[max_n];
struct Query
{
int l,r,id;
bool operator<(Query q2)
const {
if(this->r != q2.r)
{
return this->r < q2.r;
}
else
{
return this->l > q2.l;
}
}
}querys[max_n];
int sum2[max_n],ans[max_n],pow_2[max_n],st[max_n],ans_sum[max_n],inv[max_n];
signed main()
{
read(n),read(m);
pow_2[0] = inv[0] = 1;
for(int i = 1;i <= n;i++)
{
read(nums[i]);
pow_2[i] = (pow_2[i - 1] << 1LL) % mo;
inv[i] = inv[i - 1] * 500000004 % mo; // 预处理逆元
ans_sum[i] = (ans_sum[i - 1] + pow_2[i] * nums[i]) % mo; // 预处理不分块贡献
}
for(int i = 1;i <= m;i++)
{
read(querys[i].l);
read(querys[i].r);
querys[i].id = i;
}
stable_sort(querys + 1,querys + m + 1);// 按照右区间排序
for(int i = 1,j = 1,l,r;i <= m;i++)
{
l = querys[i].l,r = querys[i].r;
for(;j <= r;j++)
{
st[++st[0]] = j;
sum[st[0]] = nums[j];
// 存在多余的块且当前块大于 0
while(st[0] > 1 && sum[st[0]] > 0)
{
// 为了避免爆炸的数字大小，特殊处理一些情况
if(st[st[0]] - st[st[0] - 1] >= 40 || (1LL << (st[st[0]] - st[st[0] - 1])) > (0x7fffff7f - sum[st[0] - 1])/ sum[st[0]])
{
sum[st[0] - 1] = 0x7fffff7f;
}
else
{
sum[st[0] - 1] += (1LL << (st[st[0]] - st[st[0] - 1])) * sum[st[0]];
}
--st[0];
}
if(sum[st[0]] < 0x7fffff7f)
{
sum2[st[0]] = (sum2[st[0] - 1] + sum[st[0]]) % mo;
}
else
{
sum2[st[0]] = ans_sum[j];
}
}
// 末尾标记
st[st[0] + 1] = r + 1;
// l 区间右侧的块
int pos = upper_bound(st + 1,st + st[0] + 2,l) - st;
// 单独处理左侧答案
(ans[querys[i].id] = ((sum2[st[0]] - sum2[pos - 1]) * 2 + ((ans_sum[st[pos] - 1] - ans_sum[l - 1]) * inv[l]) % mo ) % mo+ mo) %= mo;
}
for(int i = 1;i <= m;i++)
{
writeln(ans[i]);
}
return 0;
}