25.CF992E Nastya and King-Shamans 转化+线段树二分

25.CF992E Nastya and King-Shamans 转化+线段树二分

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，要求支持单点修改，查询序列中 a [ i ] = s [ i − 1 ] a[i] = s[i - 1] a[i]=s[i−1] 的点(SPJ)

线段树维护 a i − s i − 1 a_i - s_{i - 1} ai​−si−1​的区间最大值，然后树上二分查询即可

洛谷传送门：CF992E Nastya and King-Shamans - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：E. Nastya and King-Shamans (codeforces.com)

题目分析

首先考虑暴力解决：每次暴力检查所有的 a [ i ] a[i] a[i]，需要检查 n n n个数字。

发现对于所有的 i i i，满足条件的一定不超过 log ⁡ s n \log s_n logsn​个：

• 因为对于满足条件的 i , a i − s i − 1 ≥ 0 i,a_i - s_{i - 1}≥0 i,ai​−si−1​≥0, 因此 s i ≥ 2 s i − 1 s_i ≥ 2s_{i - 1} si​≥2si−1​

• 故每有一个满足条件的 i i i， s s s就会翻倍。因此总共满足条件的不超过 log ⁡ s n \log s_n logsn​个

用线段树维护 a i − s i − 1 a_i - s_{i - 1} ai​−si−1​的区间最大值，由于查询的叶子节点不会超过 log ⁡ s n \log s_n logsn​故复杂度正确

• 单点修改操作等同于对前缀和后缀序列的区间修改及对原序列的单点修改，线段树支持区间修改即可

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e6 + 10, MOD = 1e9 + 7;

namespace ffastIO {
	const int bufl = 1