本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 08:33:53

题解：P12665 [KOI 2023 Round 2] ZigZag

感谢

感谢@KSCD_大佬的讲解，他提供了本题的思路与优化方法。
感谢@Dtw_大佬，他提供了本题的部分代码。

题意

给定一个长度为 $n$ 的排列，定义函数 $f(x,y,z)$ 表示满足以下条件的最长子序列长度：

1. 子序列中的元素均选自原序列中下标处于区间 $[y, z]$ 的部分。
2. 子序列中所有的元素值都不超过 $x$。
3. 子序列必须是一个之字形序列（Zigzag）。

“之字形序列”$S$ 的定义为：

• 如果 $S_i < S_{i+1}$，则有 $S_{i+1} > S_{i+2}$；
• 如果 $S_i > S_{i+1}$，则有 $S_{i+1} < S_{i+2}$。

对于每个 $x$，你需要求出 $\sum_{y=1}^n \sum_{z=y}^n f(x,y,z)$。

思路

我们可以先考虑 $O(n)$ 计算单个 $f$ 的贡献。
定义有效点为区间内小于等于 $x$ 的点，那么我们选择的子序列中一定都是有效点（废话）。
贪心地想，我们在一个区间内，一定会选择最左端的有效点，最右端的有效点，和最顶端与最低端（结合图理解，这样一定不劣）的点。

但是由于要求 $f$ 函数的和，我们发现这样真的太慢了，于是考虑拆贡献。
定义“有效点”表示区间内小于等于 $x$ 的点。
对于一个点 $p$，令它左右的有效点位置分别为 $l,r$，那么有以下几种情况：

1. 当前区间内只有 $p$ 一个有效点，即左右端点满足大于 $l$ 且小于 $r$，即造成 $(i-l)\times (r-i)$ 的贡献；
2. $p$ 为区间左端点，满足区间左端点 $l<L\le i$，右端点 $r\le R\le n$，造成 $(i-l)\times (n-r+1)$ 的贡献；
3. $p$ 为区间右端点，与上条类似，造成 $l\times (r-i)$ 的贡献；
4. $p$ 为顶端或低端的数，即满足 $[a_p > a_l]=[a_p>a_r]$ 时，造成 $l \times (n-r+1)$ 的贡献。

我们意外地发现，当新出现或减少一个有效点时，仅会对它左右的有效点 $l,r$ 的贡献造成影响，我们便可以通过改变 $x$ 每次新增或减少一个有效点，$O(n)$ 便可做出（具体咋做看实现）。

实现

我们可以枚举 $x$，用一个 set 维护当前有效点，那么我们新增一个有效点后，便可以通过 set 更改左右点的贡献，并加入其本身的贡献，时间复杂度 $O(n \log n)$。
代码（代码选自@Dtw_大佬）：

#include <bits\/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;

int n, a[N], pa[N];
ll ans;
set<int> q;

void add(auto p)
{
	int l = *prev(p), r = *next(p), i = *p;
	ans += 1ll * (i - l) * (r - i);
	ans += 1ll * l * (r - i);
	ans += 1ll * (n - r + 1) * (i - l);
  	bool o1 = (a[l] < a[i]), o2 = (a[i] > a[r]);
 	bool ok = o1 ^ o2;
 	if (!ok && l != 0 && r != n + 1) ans += 1ll * l * (n - r + 1);
}

void del(auto p)
{
	int l = *prev(p), r = *next(p), i = *p;
	ans -= 1ll * (i - l) * (r - i);
	ans -= 1ll * l * (r - i);
	ans -= 1ll * (n - r + 1) * (i - l);
  	bool o1 = (a[l] < a[i]), o2 = (a[i] > a[r]);
 	bool ok = o1 ^ o2;
 	if (!ok && l != 0 && r != n + 1) ans -= 1ll * l * (n - r + 1);
}

int main()
{
	cin.tie(0)->ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], pa[i] = i;
	sort (pa + 1, pa + n + 1, [&](int x, int y) { return a[x] < a[y]; });
	set<int> q; q.insert(0), q.insert(n + 1);
	for (int i = 1; i <= n; i++) {
		auto p = q.upper_bound(pa[i]); p--;
		if (*p != n + 1) del(p);
		if (*next(p) != n + 1 && *p != n + 1) del(next(p));
		q.insert(pa[i]); p = q.find(pa[i]);
		if (*prev(p) != 0) add(prev(p));
		add(p);
		if (*next(p) != n + 1) add(next(p));
		cout << ans << "\n";
	}
	return 0;
}

别急，还有线性的做法。
我们可以先线性预处理出 $x=n$ 时的总贡献，然后用双向链表维护每个点的左右有效点，倒序枚举 $x$，然后删贡献（与上一做法类似），就可以省去 set 内二分的对数复杂度。
时间复杂度 $O(n)$。

代码（这份是我自己的，目前是最优解）：

#include<bits\/stdc++.h>
#include<set>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define F(i,l,r) for(int i=(l); i<=(r); i++)
using namespace std;
const int N = 2e5 + 50, M = 1e3 + 50;
const int INF=0x3f3f3f3f3f3f3f3f, mod=1e9+7;

int n,ans;
int res[N];
int a[N],pos[N];
int pre[N],nxt[N];

inline void change(int p,int f){
	int l=pre[p],r=nxt[p];
	int res=0;
	if(l==-1 || r==-1) res=p*(n-p+1);
	else{
		res = (p-l)*(r-p) + l*(r-p) + (p-l)*(n-r+1);
		if((a[p]>a[l])==(a[p]>a[r])) res += l*(n-r+1);
	}
	ans += f*res;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n;
	F(i,1,n) cin>>a[i];
	F(i,1,n){
		pos[a[i]]=i;
		pre[i]=i-1,nxt[i]=i+1;
		ans+=n;
		if(i!=1&&i!=n && (a[i]>a[i-1])==(a[i]>a[i+1])) ans+=(i-1)*(n-i);
	}
	pre[1]=nxt[n]=-1;
	res[n]=ans;
	for(int x=n-1; x; x--){
		int p=pos[x+1];
		int l=pre[p], r=nxt[p];
		
		if(l!=-1) change(l,-1);
		if(r!=-1) change(r,-1);
		
		if(l!=-1) nxt[l]=r;
		if(r!=-1) pre[r]=l;
		change(p,-1);
		
		if(l!=-1) change(l,1);
		if(r!=-1) change(r,1);
		
		res[x]=ans;
	}
	F(i,1,n) cout<<res[i]<<'\n';

	return 0;
}

好久没写题解了，希望审核大大 一遍 两遍过，拜谢了。