P12665 [KOI 2023 Round 2] ZigZag 题解
刘梓轩2010
·
·
题解
题传
题意
给你 n 和 n 的一个排列，\forall 1\le i\le n 求出排列的所有区间里，由大小不超过 i 的数构成的最长的“之字形”子序列的长度之和是多少。
其中，一个长为 k 的序列是“之字形”序列，当且仅当对于所有满足 1\le i \le k-2 的 i，满足以下条件之一：
- 如果 S_i < S_{i+1}，那么 S_{i+1} < S_{i+2}；
- 如果 S_i > S_{i+1}，那么 S_{i+1} > S_{i+2}。
## 思路
首先，我们可以想到，枚举限制（最大值），然后 dp 求出每个区间中不超过最大值的数所构成的最长的之字形子序列的长度是多少。枚举最大值是 $O(n)$ 的，枚举区间，做 dp 可以一起，总复杂度 $O(n^3)$。不能接受，但是可以过 40 分。
[提交记录](https://www.luogu.com.cn/record/234020420)
我们可以观察到，如果我们需要做 dp，那么一次至少需要 $O(n)$ 的复杂度，难以优化，所以我们需要考虑能否在不 dp 的情况下求出满足要求的子序列的长度。
我们发现，对于某一个区间来说，如果它是单调的，那么只有区间的两个端点对于答案是有贡献的，中间的不影响答案。由于整个序列就是由若干个极长的单调区间组成的，所以我们发现，我们可以将贡献拆到每个数上去，一个数只有在区间中作为开头、结尾或者是一个“转折点”（两边都比他大或者两边都比他小）时才会有贡献，我们可以对于几种情况分类讨论。
我们发现，每个数贡献到的区间数就是它的贡献。
考虑固定最大值（也就是说有一些位置可能为空，以下的 $i$，$l$，$r$ 均不是空位置）。我们令当前的位置为 $i$，它左边的位置为 $l$，右边的位置为 $r$，那么有以下讨论：
- 作为一个数单独出现（区间里只有这一个数），一共有 $(i-l)\times(r-i)$ 个区间；
- 作为一个开头，一共有 $(i-l)\times(n-r+1)$ 个区间；
- 作为一个结尾，一共有 $l\times(r-i)$ 个区间；
- 作为一个转折点，要满足 $a_l<a_i,a_r<a_i$ 或者 $a_l>a_i,a_r>a_i$，一共有 $l\times(n-r+1)$ 个区间。
于是我们就可以从小到大加入每个数，计算新加入的贡献，重算左右两边的贡献，其他的不用管（因为 $l$，$r$ 没有变）。可以用 set 维护已经加入的点，复杂度 $O(n \log n)$，可以通过。
## Code
```c++
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n;
int a[N];
int p[N];
int ans;
set<int> st;
void upd(int pos,int x)
{
int l=-1,r=-1,sum=0;
auto it=st.lower_bound(pos);
it++;
if(it!=st.end()) r=*it;
it--;
if(it!=st.begin()) it--,l=*it;
if(l==-1||r==-1) sum+=pos*(n-pos+1);
else
{
sum+=(pos-l)*(r-pos);
sum+=(pos-l)*(n-r+1);
sum+=(r-pos)*l;
if((a[l]<a[pos])==(a[r]<a[pos])) sum+=l*(n-r+1);
}
ans+=x*sum;
}
void ins(int pos)
{
int l=-1,r=-1;
auto it=st.lower_bound(pos);
if(it!=st.end()) upd(*it,-1),r=*it;
if(it!=st.begin()) it--,upd(*it,-1),l=*it;
st.insert(pos);
upd(pos,1);
if(l!=-1) upd(l,1);
if(r!=-1) upd(r,1);
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],p[a[i]]=i;
for(int i=1;i<=n;i++)
{
ins(p[i]);
cout<<ans<<endl;
}
return 0;
}
```