【线段树】P8539 「Wdoi-2」来自地上的支援|普及+

P8539 「Wdoi-2」来自地上的支援

题目背景

波光粼粼的山顶湖与庄严神圣的神社之下，是一座复合型活火山。
沿幻想风穴而下，便能到达火山之下，废弃已久的地狱原址。

在旧地狱中，有一座大都市。那里是旧地狱还是地狱的时候在那工作的众鬼们居住的地方，只有那里亡者们是无法踏入去的。后来地狱体制改革，机构搬离了这个地方。
因为这个缘故这块地狱变成了废墟，但却有一部分看上了那里的妖怪擅作主张占领了那里，于是就成了如今的旧地狱了。
这里比地上更没有秩序可言。悍匪恶霸，特别是惹人类讨厌的家伙都喜欢搬到这边定居下来。

自旧地狱喷泻而出的间歇泉，给妖怪之山带来了优良的温泉，也喷出了大量的怨灵。

为了解决这次异变，乐园的巫女和普通的魔法使结伴而行，在来自地上的支援下，自幻想风穴直冲地底。

先后结（bao）识（da）了黑暗洞窟中的明亮之网、地壳下的嫉妒心、人们所谈论的怪力乱神后，二人来到了遗址中心的洋馆，地灵殿。

受这里主人的指引，二人来到了位于深处的间歇泉地下中心。

题目描述

简要题意

给定正整数 $n$、$v$ 和长度为 $n$ 的数组 { A i } \{A_i\} {Ai​}。

有一个长度为 $n$ 的数组 $B$，初始值与 $A$ 相同。
执行 $n$ 次操作，第 $i$ 次操作在 $[1,i]$ 中按如下规则选取一个正整数 $j$，然后把 $B_j$ 变成 $B_j+v$：

• 选取 $B_j$ 最大的 $j$。
• $B_j$ 相同时选择 $A_j$ 最大的 $j$。
• $A_j,B_j$ 均相同，选择较小的 $j$。

我们称这是选中了一次 $j$。

有 $m$ 次询问，每次询问给定 $x_i,k_i$。表示求最小的 $s$，使得若将 $A_{x_i}$ 的初始值改为 $s$（注意此时 $B_{x_i}$ 的初始值也会跟着改变），$x_i$ 至少被选中 $k_i$ 次，或报告不存在（结果为 $0$）。请注意，$s$ 不存在最小值时也是报告不存在（结果为 $0$）。

询问之间互相独立，也就是每次询问不会对 $A_{x_i}$ 和 $B_{x_i}$ 产生实质性更改。

原始题意

到达控制中心之后，主角组和灵乌路空进行了激烈的狗斗大赛。负责技术维护的河童需要接受荷取来自地上指挥部的指令，保障生产安全。

具体地，有 $n$ 个核反应机组依次排开，第 $i$ 个机组的活动强度为 $A_i$。为了维护平衡，控制系统依次操作 $n$ 次，第 $i$ 次操作会在前 $i$ 个机组中找到一个当前活动度最高的机组，进行一次调节平衡操作，并将其活动度增加 $v$。倘若有多个机组活动度最高，就应当选择初始活动度最大的，若还是无法比较，则取编号最小。

为了在自动控制系统的基础上调节平衡，荷取会发出 $m$ 条指令，形如她每次会给出两个整数 $x_i,k_i$，表示她会修改第 $x_i$ 个机组的初始活动度。她希望通过修改（必须改成一个非负整数 $s$）后，$x_i$ 号机组至少被平衡 $k_i$ 次。如果无论如何都无法达到要求，那么结果就是 $0$；否则请求出满足条件的最小的 $s$。

输入格式

• 第一行有三个整数 $n,m,v$。
• 接下来一行，有 $n$ 个整数，描述 $a_i$。
• 接下来 $m$ 行，每行有两个整数 $x_i,k_i$，描述一次询问。

输出格式

• 一行，输出两个整数，表示所有结果的异或和与加法和。

输入输出样例 #1

输入 #1

7 2 3
1 4 1 5 4 1 1
3 3
6 4

输出 #1

7 7

输入输出样例 #2

输入 #2

10 10 9
14 91 84 13 97 92 23 64 31 10 
5 2
5 5
9 1
2 6
9 1
5 4
3 5
2 8
8 2
5 4

输出 #2

245 1177

说明/提示

样例 1 解释

对于第一次询问，我们将 $A_3$ 修改为 $7$。

• 第一次操作选择了位置 $1$，于是 $B_1$ 变为 $4$。
• 第二次操作选择了位置 $2$，于是 $B_2$ 变为 $7$。虽然操作前 $B_1=B_2$，但是 $A_2>A_1$，因此选择位置 $2$。
• 第三次操作选择了位置 $3$，于是 $B_3$ 变为 $10$。
• 第四次操作选择了位置 $3$，于是 $B_3$ 变为 $13$。
• 第五次操作选择了位置 $3$，于是 $B_3$ 变为 $16$。
• 第六次操作选择了位置 $3$，于是 $B_3$ 变为 $19$。
• 第七次操作选择了位置 $3$，于是 $B_3$ 变为 $22$。

于是位置 $3$ 一共被选择了 $5$ 次，满足题意。可以证明，如果把 $A_3$ 的初始值设为 $6$，无法达成要求。于是该询问结果为 $7$。

对于第二个询问，容易发现不可能有 $4$ 次以上操作选择位置 $6$。因此该询问结果为 $0$。

$7\oplus 0=7$，$7+0=7$，因此输出 $7,7$。

数据范围

$$\begin{array}{ccccc}\text{Subtask}& \mathbf{n},\mathbf{m}\le & {\mathbf{a}}_{\mathbf{i}}\le & \mathbf{v}\le & \text{分值}\\ 1& 10& 100& 10& 10\\ 2& 100& 5\times 10^3& 50& 20\\ 3& 10^3& 10^9& 100& 10\\ 4& 10^5& 10^9& 100& 25\\ 5& 2\times 10^6& 10^9& 100& 35\end{array}$$

对于全部数据，满足 $1\le n,m\le 2\times 10^6$，$1\le v\le 100$，$1\le a_i\le 10^9$，$1\le x,k\le n$。

本题 IO 量较大，请选择合适的输入方式。

树状数组（或线段树）

性质一：执行到第i步（i >=xi）时，如果没有选择xi，则永远不会选择xi。令本次选择的是j1，则xi永远劣于j1。
结论：i$\in$[xi,xi+ki-1]时，必须选择xi。
具体分为两部分：
一，c[j]= 执行完1到j步后，b[1…j]的最大值。贴别的是b[0]=0。s >= c[xi-1]。
二，$\forall$i $\in$ [xi+1,xi+k-1] s >max(a[i]-v*(i-xi))
单个查询时间复杂度：O(logn)，总时间复杂度：O((n+m)logn)
每个查询的结果在int范围中，但其和在long long范围中。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}	~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 12 * 1'000'000>
class CInBuff
{
public:inline CInBuff() {int readCnt = fread(buffer, 1, N, stdin);buffer[readCnt] = 0;}inline int Read() {int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);return f ? -x : x;}
private:char buffer[N] , * S = buffer;
};template<class T = int, T def = INT_MIN>
class CTreeArrMax
{
public:CTreeArrMax(int iEleSize) :m_iMax(iEleSize) {m_aMax.assign(iEleSize + 1, def);m_aRangMax.assign(iEleSize + 1, def);}void Modify(int indexBase0, T value){indexBase0++;if (value <= m_aMax[indexBase0]){return;}m_aMax[indexBase0] = value;while (indexBase0 <= m_iMax){m_aRangMax[indexBase0] = max(m_aRangMax[indexBase0], value);indexBase0 += BitLower(indexBase0);}}T Query(int leftBas0, int rBase0){leftBas0++;rBase0++;leftBas0 = max(1, leftBas0);rBase0 = min(m_iMax, rBase0);T iMax = def;while (rBase0 >= leftBas0){const int pre = rBase0 - BitLower(rBase0);if (pre + 1 >= leftBas0){iMax = max(iMax, m_aRangMax[rBase0]);rBase0 = pre;}else{iMax = max(iMax, m_aMax[rBase0]);rBase0--;}}return iMax;}
protected:int BitLower(int x){return x & (-x);}const int m_iMax;vector<T> m_aMax, m_aRangMax;
};class Solution {
public:pair<int, long long> Ans(const int V, const vector<int>& a, const vector<pair<int, int>>& xk) {const int N = a.size();vector<int> c(N + 1);{vector<int> tmp(1);tmp.insert(tmp.end(), a.begin(), a.end());int pre = 0;for (int i = 1; i <= N; i++) {if (tmp[i] >= tmp[pre]) {pre = i;}tmp[pre] += V;c[i] = tmp[pre];}}CTreeArrMax treeArr(N + 1);{for (int i = 1; i <= N; i++) {treeArr.Modify(i, a[i - 1] - i * V);}}int ans1 = 0;long long ans2 = 0;for (const auto& [x, k] : xk) {if (N - x + 1 < k) { continue; }int s = c[x - 1];int r = treeArr.Query(x + 1, x + k - 1) + V * x;if (r + 1 > s) {s = r + 1;}ans1 ^= s;ans2 += s;}return { ans1,ans2 };}
};int main() {	
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	int n,m,V;CInBuff<12*2000'010*3> ib;n = ib.Read();m = ib.Read();V = ib.Read();vector<int> a(n);for (int i = 0; i < n; i++) {a[i] = ib.Read();}vector<pair<int, int>> xk(m);for (int i = 0; i < m; i++) {xk[i].first = ib.Read();xk[i].second = ib.Read();}auto res = Solution().Ans(V,a,xk);
#ifdef _DEBUG		/*printf("T=%d,", T);*/Out(a, "a=");Out(xk, "xk=");/*Out(que, "que=");*/
#endif // DEBUG	cout << res.first << " " << res.second << endl;return 0;
}

单元测试

	vector<int> a;vector<pair<int, int>> xk;TEST_METHOD(TestMethod11){a = { 1,4,1,5,4,1,1 }, xk = { {3,3},{6,4} };auto res = Solution().Ans(3,a,xk);AssertEx({ 7,7LL}, res);}TEST_METHOD(TestMethod12) {a = { 14,91,84,13,97,92,23,64,31,10 }, xk = { {5,2},{5,5},{9,1},{2,6},{9,1},{5,4},{3,5},{2,8},{8,2},{5,4} };			auto res = Solution().Ans(9, a, xk);AssertEx({ 245,1177LL }, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。