题解：P10798 「CZOI-R1」消除威胁

猜你想要：更好的阅读体验。

题目大意:

给出一个有 $n$（$1 \le n \le 5 \times 10^5$）个整数的序列 $A$，我们可以对他进行任意次将 $A_i$ 变成 $-A_i$ 的操作，求最少的区间 $[l,r]$ 满足 $A_l=A_r$ 且 $A_l$（或者说 $A_r$）是区间 $[l,r]$ 中最大的。

比赛时 AC 过程：

骗分思路（10 pts）：

读完题后，暂时没有什么思路。看到数据范围，突然发现：Subtask #4 中 $|A_i|$ 均相等！这不妥妥的给我们骗分用的。

推导：

假设现有一个满足 $|A_i|$ 均相等的序列 $A$。

如果 $A_i$ 均为正数（或负数），那么具有”威胁“的区间的数量是 $\sum_{i = 1}^{n} i$（或者说是 $\frac{n(n+1)}{2}$）。

那么我们可以很容易地想到对于 $A$ 来说，想要得到最少具有"威胁“的区间,我们需要让 $\frac{n}{2}$ 个数字变成正数，让剩下的数变成负数。

寻找规律：

假设 $k=|A_i|$。

1. 当 $n=1$ 时，由于题目规定了 $l<r$ 所以”威胁“总数为 $0$。
2. 当 $n=2$ 时，根据上面推导的方法，将 $A$ 变为 ${k,-k}$，”威胁“总数为 $0$。
3. 当 $n=3$ 时，将 $A$ 变为 ${k,k,-k}$，”威胁“总数为 $1$。
4. 以此类推，当 $n=4$ 时，”威胁“总数为 $2$；当 $n=5$ 时，”威胁“总数为 $3$；当 $n=6$ 时，”威胁“总数为 $6$；当 $n=7$ 时，”威胁“总数为 $9$；当 $n=8$ 时，”威胁“总数为 $12$。

将上面得出的”威胁“总数放在序列 $F$ 中，得 ${0,0,1,2,4,6,9,12}$。把每两项之间的差值求出，得 ${0,1,1,2,2,3,3}$，规律这不就来了吗。根据规律我们可以列出递推式：$F_i=F_{i-1}+\frac{i-1}{2}$。

骗分代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500860;
int n,t; //t表示 (i-1)/2 的值 
long long f[N];
int main(){
	cin>>n;
	for(int i=3;i<=n;i++){
		if(i&1) t++; //当i为奇数（也就是 (i-1)/2 的值会增加时）t++
		f[i]=f[i-1]+t; //上面推导的 f[i]=f[i-1]+(i-1)/2 
	}
	cout<<f[n]; 
	return 0;
}

未优化的正解思路（40 pts）：

1. 根据上面骗分总结出的序列 $F$ 的思路可以发现，$F_i$ 并不只适用于 $|A_i|$ 均相等的情况，还适用于在具有”威胁“的区间 $[l,r]$ 中所有数的绝对值中与 $|A_l|$ 相等的总数。因此，对于一个数 $A_i$，我们只需用变量 $cnt$ 记录以 $i$ 为起点到最后一个绝对值与 $|A_i|$ 相等的区间中的所有绝对值与 $|A_i|$ 相等的总数，再让答案加上 $F_{cnt}$，最后就得出了最终答案。
2. 考虑到题目说 $|A_l|$ 必须是区间 $[l,r]$ 中最大的，所以当遇到 $|A_i|>|A_l|$ 时，我们需要停止寻找后面绝对值与 $|A_l|$ 相等的数字。
3. 由于我们可以进行任意次的将 $A_i$ 变成 $-A_i$，并且为了方便后面的比大小，所以我们统一将 $A_i$ 变成 $|A_i|$。

未优化的正解代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500860;
int n,t,a[N];
long long ans,f[N];
bool v[N]; //v用来标记已用过的 a[i] 防止重复计算。
int main(){
	cin>>n;
	for(int i=3;i<=n;i++){
		if(i&1) t++;
		f[i]=f[i-1]+t;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		a[i]=abs(a[i]); //如上面第 3 点所说。
	}
	for(int i=1;i<=n;i++){
		if(!v[i]){
			int cnt=1;
			for(int j=i+1;j<=n;j++){
				if(a[j]>a[i]) break; //如上面第 2 点所说。
				if(a[i]==a[j]) cnt++,v[j]=1;
			}
			ans+=f[cnt];
		}
	}
	cout<<ans;
	return 0;
}

优化的正解思路（AC）：

序言（可跳过）：

本来写完上面未优化的正解 （我比赛时不知到这是正解） 正准备关闭 luogu，打开 steam，享受美好人生的。但看到这个记录详情只 TLE 了两个点,并且还分别是最后两组时，我心中突然涌现出一股力量，这股力量告诉我，这道题我可以 AC！

优化方法：

1. 我们可以用一个数组储存与 $A_i$ 相同的下一个数字的位置，这样就可以省去遍历一遍序列 $A$ 的时间。
2. 因为我们不再遍历序列 $A$，所以我们需要快速求出区间 $[l,r]$ 中的最大值，以便我们判断 $A_l$ 是否是$[l,r]$ 中的最大值。这里我推荐用 st 表来求。

屏幕前的洛友不会 st 表？讲解 $+$ 模板题迅速入门！

比赛 AC 代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=500860;
unordered_map<int,vector<int> > m; //m[a[i]] 用来记录与 a[i] 相同的下一个数字的位置。
unordered_map<int,int> l; //记录 m[a[i]] 用到哪了，与之前 v 的作用相似。
//不开 unordered_map 会炸(MLE 或 TLE)。
int n,t,a[N],s[N][20]; //log2(500000)大约是19。
LL ans,f[N];
inline int qy(int l,int r){ //查询区间 [l,r] 的最大值。
	int t=log2(r-l+1);
	return max(s[l][t],s[r-(1<<t)+1][t]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		a[i]=abs(a[i]);
		m[a[i]].push_back(i); //记录 m[a[i]] 的位置。
	}
	for(int j=0;j<20;j++) //st 表预处理。
		for(int i=1;i+(1<<j)-1<=n;i++)
			if(!j) s[i][j]=a[i];
			else s[i][j]=max(s[i][j-1],s[i+(1<<j-1)][j-1]);
	for(int i=3;i<=n;i++){
		if(i&1) t++;
		f[i]=f[i-1]+t;
	}
	for(int i=1;i<=n;i++){
		int cnt=0,j=l[a[i]]; //j 记录 m[a[i]] 用到哪了。
		for(;j<m[a[i]].size();j++){
			if(qy(i,m[a[i]][j])>a[i]) break; //判断 a[i] 是否是最大的。
			else cnt++;
		}
		l[a[i]]=j; //记录 m[a[i]] 用到的位置。
		ans+=f[cnt];
	}
	cout<<ans;
	return 0;
}

AC 喽ヾ(≧▽≦*)o，完结撒花。

本题的 AC 过程：

序言（还是可跳过）：

第二天起来一看，这道题进题库了，真的太好了，打比赛还送 AC 率。一交上去，WA 了两个点,仅仅 90pts？一看题目，改了一个设定，即规定了 $0=-0$（昨天规定 $0\ne-0$），又被背刺了啊(っ °Д °;)っ。

处理 $0$ 的情况：

因为 $0=-0$，所以以 $0$ 为左右端点的区间中具有”威胁“的区间的数量是 $\sum_{i = 1}^{n} i$（或者说是 $\frac{n(n+1)}{2}$），其递推式为 $F2_i=F2_{i-1}+i-1$。

本题 AC 代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=500860;
unordered_map<int,vector<int> > m;
unordered_map<int,int> l;
int n,t,a[N],s[N][20];
LL ans,f[N],f2[N]; //f2 专门用来处理 0 的情况。
inline int qy(int l,int r){
	int t=log2(r-l+1);
	return max(s[l][t],s[r-(1<<t)+1][t]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		a[i]=abs(a[i]);
		m[a[i]].push_back(i);
	}
	for(int i=3;i<=n;i++){
		if(i&1) t++;
		f[i]=f[i-1]+t;
	}
	for(int i=2;i<=n;i++)
		f2[i]=f2[i-1]+i-1; //如题推导的左右端点为 0 的情况。
	for(int j=0;j<20;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			if(!j) s[i][j]=a[i];
			else s[i][j]=max(s[i][j-1],s[i+(1<<j-1)][j-1]);
	for(int i=1;i<=n;i++){
		int cnt=0,j=l[a[i]];
		for(;j<m[a[i]].size();j++){
			if(qy(i,m[a[i]][j])>a[i]) break;
			else cnt++;
		}
		l[a[i]]=j;
		if(!a[i]) ans+=f2[cnt]; //特殊情况特殊对待ψ(｀∇´)ψ。
		else ans+=f[cnt];
	}
	cout<<ans;
	return 0;
}

后序：题解有界，帮助无限，希望这篇题解可以帮助屏幕前的你ヾ(≧▽≦*)o。