题解：P9910 [COCI 2023/2024 #2] Dizalo

· · 题解

题解 ： P9910 Dizalo

自认为比较详细。

题目大意

给定一个 1\sim n 的排列，按照数值依次进行操作，设当前值的位置为 pos，则令队伍中 1\sim pos 的人暂时离开队伍，并且你可以任意重排 1\sim pos-1 的顺序，求离开队伍人数之和的最小值。

题目分析

先不考虑动态问题，观察到重排的策略必然是顺序排序，这样显然不劣，考虑如何刻画。

当进行到值为 i 时，发现 1\sim i-1 已经离开，显然不会对答案造成贡献。那么此时，假如 i 被重排过，则他必然位于第一个位置，否则在他前面的人都必须离开。

贡献计算是这样的：每个人都必须离开一次，总贡献是 n。其次是他离开时对其他人影响。若 \exists j>i,a_j<a_i，则其被重排过，位于第一位，否则贡献为 \sum [j<i \land a_j>a_i]，即在他前面且比他大的元素个数。

这里停一下，发现我们对原问题的转化已经是足够的了，已经可以拿到非平凡部分分了，随便用树状数组这类东西来维护这样的偏序关系就能做到 O(qn\log n)。现在考虑如何去动态维护这样的东西。

~模拟赛场上本蒟蒻写了个分块加二分的写法，不幸没调出来。~

考虑第一个条件的否定 \forall j>i,a_j>a_i，发现等价于 i 是后缀最小值，但这个东西去做删点不好维护，故考虑一个经典的 trick，考虑倒序操作做加点操作。

考虑维护所有后缀最小值的位置，你把所有后缀最小值拎出来类似单调栈，每个元素只会至多被加入或删除 1 次，所以暴力更新的复杂度就是对的。

首先肯定不能每次加完点后都去对每个后缀最小值去求一遍其权值，复杂度肯定不对，考虑去维护增量。

首先就是加入一个点后它本身可能成为后缀最小值，那怎么求它的权值呢？你发现 \sum [j<i\land a_j>a_i] 这个东西加上时间序是一个三维偏序问题，很难维护。但是~我认为~最巧妙的观察来了，对于后缀最小值来说，其等价于 \sum [a_j>a_i] - \sum [j>i]。这个东西用两个树状数组分别维护权值和位置信息就可以了。

其次你会发现，加入这个点可能让它前面的一些点不再是后缀最小值，前面分析发现暴力做复杂度都是对的，你用 set 一类的东西能做到删除单个元素 O(\log n)，我直接用树状数组加二分实现了非常 naive 的 O(\log^2 n) 做法。那么应该去掉它们的贡献，它们的贡献怎么去掉呢？和上面那个是完全一样的。

最后，对于一些已经是后缀最小值的点，其权值可能有变化，还是那个式子，你考虑维护一个增量，就是有多少后缀最小值的权值会改变，同样把所有后缀最小值的权值和位置分别开树状数组来维护这个增量。

总复杂度 O(n\log^2 n)，瓶颈在树状数组二分，这个东西改改就成 O(n\log n) 了，但懒得改。

:::info[CODE]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) ((x)&(-(x)))
inline int read(){}
inline void write(int x){}
const int N=1e5+100;
int n,a[N],op[N],del[N],m,res[N],ans;
struct BIT{
    //树状数组 
}s,pos,val,mipos,mival;
bool check(int p){
    int cnt=s.qry(n)-s.qry(p);
    if(!cnt) return 1;
    int l=p+1,r=n,mid;
    while(l<r){
        mid=l+r>>1;
        if(s.qry(p)+1<=s.qry(mid)) r=mid;
        else l=mid+1;
    }
    if(a[p]<a[l]) return 1;
    else return 0;
}
inline void add(int p){
    ans++;
    int tot=s.qry(p-1);
    while(tot){
        int l=1,r=p-1,mid;
        while(l<r){
            mid=l+r>>1;
            if(s.qry(mid)==tot) r=mid;
            else l=mid+1;
        }
        if(a[l]>a[p]){
            ans-=val.qry(n)-val.qry(a[l])-pos.qry(n)+pos.qry(l);
            s.add(l,-1);
            mipos.add(l,-1);
            mival.add(a[l],-1);
            tot--;
        }else{
            break;
        }
    }
    if(check(p)){
        s.add(p,1);
        mipos.add(p,1);
        mival.add(a[p],1);
        ans+=val.qry(n)-val.qry(a[p])-pos.qry(n)+pos.qry(p);
    }
    val.add(a[p],1);
    pos.add(p,1);
    ans+=mival.qry(a[p]-1);
    ans-=mipos.qry(p-1);
}
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++){
        op[i]=read();del[op[i]]=1;
    } 
    for(int i=1;i<=n;i++){
        if(!del[i]) add(i);
    }
    res[m]=ans;
    for(int i=m;i>=1;i--){
        add(op[i]);
        res[i-1]=ans;
    }
    for(int i=0;i<=m;i++){
        write(res[i]);putchar(' ');
    }

  return 0;
}

:::