题解：P12665 [KOI 2023 Round 2] ZigZag

· · 题解

题解：P12665 [KOI 2023 Round 2] ZigZag

感谢

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

题意

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

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

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

对于每个 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) 的贡献；

我们意外地发现，当新出现或减少一个有效点时，仅会对它左右的有效点 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;
}

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