题解：P5012 水の数列

题目分析

给定一个长度为

N(N\le10^6)

，值域为

[1, 10^6]

的整数数列

Num_1, Num_2, Num_3, \dots, Num_N

。

定义区间数

\text{cnt}(x)

与分数

\text{score}(x)

：

将 $Num$ 中所有 $\le x$ 的数标记后，连续标记的区间的数量（ $\text{cnt}(x)$ ）与这些区间的长度的平方和（ $\text{score}(x)$ ）。

下文称这样的区间为标记连续段。

有

T

次强制在线的询问，每次询问给出

[l, r](1\le l\le r\le n)

，你需要选择

x

，使得

\text{cnt}(x)\in[l,r]

，同时最大化

\frac{\text{score}(x)}{x}

，依次输出

\text{score}(x), x

，如果无解输出 -1 -1。

解题思路

我们发现

\frac{\text{score}(x)}{x}

与

\text{cnt}(x)

无关，我们可以对所有

\text{cnt}(x)=i

，初始化求出最优的

\text{score}(x), x

，于是询问就变成了 RMQ 问题，但本题需要特殊处理无解的情况且内存限制较严，在后文会给出具体做法。

那么如何对所有

\text{cnt}(x)=i

，求出最优的

\text{score}(x), x

呢？
显然考虑满足

\text{cnt}(x)=i

的

x

是困难的，我们不妨枚举可能的

x

，然后去更新

\text{cnt}(x)=i

的最优解。

初始化

由于

N\le10^6, Num_i\le10^6

，因此我们不能暴力

O(N\times Num_{max})

初始化，注意到标记是单调变化的，随着

x

的增大，一个位置一定是从非标记到有标记之后不变的，因此枚举较大的

x

时可以复用较小的

x

的状态。

考虑当前从

x_1

递推到

x_2(x_1<x_2)

，那么所有

Num_i\in (x_1, x_2]

都要被打上标记，其它部分不变，考虑如何更新

\text{cnt}(x), \text{score}(x)

。
由于标记没有先后顺序之分，我们先考虑只给某个

Num_i

打标记，分以下情况讨论：

$Num_{i-1}, Num_{i+1}$ 均未被标记，那么 $\text{cnt}(x), \text{score}(x)$ 均增大 $1$ 。
$Num_{i-1}, Num_{i+1}$ 有一个被标记，那么 $Num_i$ 需要与它合并为一个标记连续段，显然 $\text{cnt}(x)$ 不变，设合并的标记连续段大小为 $S$ ，可得：
- 原 $\text{score}(x)=\dots+S^2$
- 新 $\text{score}(x)=\dots+(S+1)^2=\dots+S^2+(1+2\times S)$
$Num_{i-1}, Num_{i+1}$ 均被标记，那么 $Num_i$ 需要与它们一起合并为一个标记连续段，显然 $\text{cnt}(x)$ 减少 $1$ ，设 $Num_{i-1}$ 对应的标记连续段的大小为 $S_1$ ， $Num_{i+1}$ 对应的标记连续段的大小为 $S_2$ ，可得：
- 原 $\text{score}(x)=\dots+{S_1}^2+{S_2}^2$
- 新 $\text{score}(x)=\dots+(S_1+1+S_2)^2=\text{score}(x)=\dots+{S_1}^2+{S_2}^2+(1+2\times S_1+2\times (S_1+1)\times S_2)$

不失一般性，我们可以将上述过程理解为以下等价步骤：

在 $Num_i$ 处新建一个长度为 $1$ 的标记连续段， $\text{cnt}(x), \text{score}(x)$ 均增大 $1$ 。
将 $Num_{i-1}$ 所在的标记连续段（如果存在）与 $Num_i$ 所在的标记连续段合并。
将 $Num_{i+1}$ 所在的标记连续段（如果存在）与 $Num_i$ 所在的标记连续段合并。

每次合并两个长度分别为

S_1, S_2

的标记连续段时，

\text{cnt}(x)

均减小

1

，

\text{score}(x)

增大

2\times S_1\times S_2

，这实际上就是完全平方公式的应用。

上述算法需要快速查询某个位置所在标记连续段的大小，并合并两个标记连续端，这实际上就是一个加权并查集的操作，而且大小

S

只需要在根上维护即可。

根据题意可知，所有对答案有贡献的

x

必然出现在

Num

中，如若不然，设

x

在

Num

中的前驱为

x'

，则

\text{score}(x')=\text{score}(x)

，

\frac{\text{score}(x')}{x'}>\frac{\text{score}(x)}{x}

，因此我们直接按

Num

中的数从小到大递推即可。

当然，也需要快速知道

Num_i\in (x_1, x_2]

，由于我们的递推顺序是按

Num

中的数从小到大，那么不存在

Num_i\in(x_1,x_2)

，我们只需要知道

Num_i=x_2

即可。

定义二元组

(i, Num_i)

数组

B

，然后按第二元素

Num_i

升序排序，递推时按排序后的

B

的第二元素

Num_i

顺序枚举

x

，根据第一元素

i

得到

Num_i=x_2

的位置

i

，然后用并查集更新

\text{cnt}(x), \text{score}(x)

。
需要注意可能有多个

i

满足

Num_i=x_2

，使用双指针来统一更新。

枚举到某个

x

时，将其与

\text{score}(x)

写入

\text{cnt}(x)

更新最优解，完成后我们对所有有解的

\text{cnt}

都得到了最优的

\text{score}(x), x

。

处理询问

有多种方式可以处理本题的 RMQ 询问，这里以 ST 算法为例说明。

设上面的预处理得到了

A_0, A_1, A_2, \dots

，其中

A[i]

表示区间长度为

i

时的最优解

\text{score}(x), x

。
注意，一个长度为

N

的数列最多有

\lceil\frac{N}{2}\rceil

个连续段，因此只需要定义

A[0\sim500000]

。

定义

dp[i][k]

表示

\text{cnt}(x)\in[i, i+2^k)

时的最优解，每次询问

[l, r]

时可以拆分为两个

dp[\ ][k]

，取最优的那一个即可，这和标准 ST 算法没什么差别。

但是本题目空间限制较严，有以下方式可以减少空间使用：

极限化 $dp$ 的长度。
前面提到 $A$ 的可能下标范围为 $[0, 500000]$ ，因此 $dp$ 第一维长度只需要定义 $500001$ 。
因为 $2^{18}=262144, 2\times262144=524288>500000$ ，因此第二维的可能下标为 $[0, 18]$ ，第二维长度只需要定义 $19$ 。
$dp$ 值存映射。
如果我们直接存 $\text{score}(x), x$ ，前者需要一个 $\text{int32}$ ，后者需要一个 $\text{int64}$ ，总计需要 $12B$ 的大小，但是我们可以只存最优解的映射，例如在 $A$ 中的下标（显然最优解必然存在于 $A$ 中），那么只需要 $4B$ 的大小即可。上面对 $B$ 排序也可以采用同样的方法优化。

注意询问区间可能越界，前面提到

1\le l\le r\le n

，这意味着

r

可能超过

500000

，因为不可能有大于

500000

个连续段，我们可以

r\leftarrow min(r,500000)

，如果这样后发现有

l>r

，意味着

l>500000

，显然无解。

下面的代码维护了一个 max_set，表示可能的最多标记连续段数

S_{max}

，查询时

r\leftarrow min(r,S_{max})

无解对应的状态应该严格小于任何有效解，一种方法是定义无解为

x>0, \text{score}=0

，其有效性基于上面初始化时写入的

\text{score}

全为正数，这样输出答案时可以通过

[\text{score}=0]

判断是否无解。

比较问题

题目中说"如果有多解则输出选择的数最大的一组"，但是测试数据似乎并没有体现这一点，严谨起见我们考虑这一点，以下是关于这一点的 hack 数据：

输入

PLAIN

3 1
1 4 9
0 0 1 1

答案

PLAIN

4 4
1 1 0

比较的第一关键词为

\frac{\text{score}(x)}{x}

，第二关键词为

x

。

比较第一关键词时，有以下比较方法：

直接用浮点数存储分数结果，注意引入 $\text{eps}$ 来正确判断浮点数相等。
将除法比较转换为乘法比较，例如 $[\frac{\text{score}(x)}{x}<\frac{\text{score}(x')}{x'}]=[\text{score(x)}\times x'<\text{score}(x)\times x]$ 。

注意运算过程中是否需要强制类型转换，例如计算浮点数除法结果时，需要先转为浮点数。
注意第一关键词相等时要比较第二关键词。

题目特色

我们已经完成了题目的主要问题，但是接下来的题目特色部分坑点较多，这里展开阐述。

CPP

l = (a * lastans + x - 1) % n + 1;
r = (b * lastans + y - 1) % n + 1;
if (l > r) swap(l, r);

其中

lastans

表示上一次询问的最大分数(原始得分)和得到这个最大的分数的

x

的乘积，即

lastans=\text{score}(x)\times x

。

其中

\max\{\text{score}(x)\}=(10^6)^2=10^{12}

，

\max\{x\}=10^6

，

\max\{lastans\}=\max\{\text{score}(x)\}\times\max\{x\}=10^{12}\times10^6=10^{18}

，接近

\text{int64}

的上限，上面的 a * lastans, b * lastans 可能超出

\text{int64}

的范围，下面给出三种解决方案：

用 $\text{int128}$ （__int128）存储这一步的中间结果。
根据模运算的性质，计算时先对 $lastans$ 取模 $N$ 。
在更新 $lastans$ 时，直接对 $lastans$ 取模 $N$ ，即 $lastans=(\text{score}(x)\times x)\mod N$ ，这样做在输出 $lastans \mod N$ 时就可以直接输出 $lastans$ 。

代码

AC 记录

云剪贴板存档

CPP

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long int64;
constexpr int MAX_N = 1000000;
constexpr int MAX_NUM = 1000000;
constexpr int MAX_STSIZE = 18;

int n, T, Num[MAX_N+1];

struct stu1{
	int x;
	int64 score;
	// 无解情况，即默认的 score/x 需要小于 1/MAX_NUM
	// 这里令 score 的默认值为 0 表示无解状态 
	inline stu1(int x_ = 1, int64 score_ = 0) : x(x_), score(score_){};
	inline friend bool operator<(const stu1& a, const stu1& b){
		int64 tmp1 = a.score*b.x, tmp2 = b.score*a.x;
		// 如果有多解则输出选择的数最大的一组
		return (tmp1==tmp2 && a.x<b.x) || tmp1<tmp2;
	};
	inline void update(const stu1& other){ if(*this<other) *this = other; };
	inline bool valid()const{ return score>0; };
} A[(MAX_N+1)/2+1];
int max_set;                         // 最多标记连续端数，用于对 r 剪枝 
int Log2[(MAX_N+1)/2];               // 用于 O(1) ST 查询 
int dp[(MAX_N+1)/2+1][MAX_STSIZE+1]; // ST 表，存对应的 A[] 下标

// 并查集，注意初始状态为 fa[x]=0，表示 x 暂未被标记，不属于任何一个标记连续段
int fa[MAX_N+1], size[MAX_N+1];
int find_set(int x){ return fa[x]==x?x:fa[x]=find_set(fa[x]); }
inline void merge(int x, int y, int& set_cnt, int64& score){ // 注意引用 & 
	x = find_set(x);
	y = find_set(y);
	--set_cnt;
	score += 2ll*size[x]*size[y];
	size[y] += size[x]; // 只需要更新根的 size 
	fa[x] = y;
}
// B[i] = (i, Num[i]) 只存储 i 
int Num_map[MAX_N];
inline bool cmp_Num_map(int a, int b){
	return Num[a]<Num[b];
}
void init(){
	for(int i=1; i<=n; ++i) Num_map[i-1] = i;
	sort(Num_map, Num_map+n, cmp_Num_map);
	
	max_set = 0;
	int set_cnt = 0; // 标记连续段数 cnt(x)
	int64 score = 0; // 分数 score(x)
	for(int i=0, j=0; i<n; i=j){
		int x = Num[Num_map[i]];
		while(j<n && Num[Num_map[j]]==x) ++j; // 用双指针维护，统一处理所有相等值 
		for(int k=i; k<j; ++k){
			int id = Num_map[k];
			// 以自己的编号为集合的编号创建新集合 
			fa[id] = id;
			size[id] = 1;
			++set_cnt;
			++score;
			// 与左边的连续段合并
			// id-1>=1 可省略，因为 fa[0] 始终为 0 
			if(id-1>=1 && fa[id-1]) merge(id, id-1, set_cnt, score);
			// 与右边的连续段合并
			// 如果 fa[] 开到 1000002 也可省略 id+1<=n
			if(id+1<=n && fa[id+1]) merge(id, id+1, set_cnt, score);
		}
		max_set = max(max_set, set_cnt);
		A[set_cnt].update(stu1(x, score));
	}
	
	// Log2[] 最多用到 max_set-1 
	Log2[0] = Log2[1] = 0;
	for(int i=2; i<max_set; ++i) Log2[i] = Log2[i>>1]+1;
	
	for(int i=1; i<=max_set; ++i) dp[i][0] = i;
	int maxk = Log2[max_set-1];
	for(int k=1; k<=maxk; ++k){
		int maxi = max_set-(1<<k)+1;
		for(int i=1; i<=maxi; ++i){
			int l = dp[i][k-1], r = dp[i+(1<<(k-1))][k-1];
			dp[i][k] = (A[l]<A[r] ? r : l);
		}
	}
}

const stu1& query(int l, int r){
	r = min(r, max_set); // 对 r 剪枝 
	if(l>r) return A[0]; // 说明 l>max_set，无解，A[0] 表示一个无解状态
	
	// ST 查询
	int k = Log2[r-l];
	int a = dp[l][k], b = dp[r-(1<<k)+1][k];
	return A[a]<A[b] ? A[b] : A[a]; 
}

int main(){
	scanf("%d%d", &n, &T);
	for(int i=1; i<=n; ++i) scanf("%d", Num+i);
	init();
	
	int lastans = 0; // 实际上是 lastans%n，正确性由模运算性质保证 
	while(T--){
		int a, b, x, y;
		scanf("%d %d %d %d", &a, &b, &x, &y);
		int l = ((int64)a*lastans+x-1)%n+1;
		int r = ((int64)b*lastans+y-1)%n+1;
		if(l>r) swap(l, r);
		
		const stu1& ans = query(l, r);
		if(ans.valid()){
			printf("%lld %d\n%d %d %d\n", ans.score, ans.x, l, r, lastans);
			lastans = ans.score*ans.x % n;
		}else{
			printf("-1 -1\n%d %d %d\n", l, r, lastans);
			lastans = 1;
		}
	}
	return 0;
}

题解：P5012 水の数列

文章操作

题目分析

解题思路

初始化

处理询问

比较问题

输入

答案

题目特色

代码

相关推荐

评论

题解：P5012 水の数列