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

· · 题解

P9910 Dizalo

对于没有出电梯重排的操作，答案很显然是全序列逆序对数 + 序列长度，但是现在存在重排的操作，不难发现所有出去的人全部按照 a_i 升序排序一定是最优的，这样可以让已经出去过的人不再产生使其他人出去的贡献，那么现在还会产生让其他人出去的贡献的人一定是某个以自己为开头的后缀的序列最小值，记为位置 i，产生的贡献为 \sum_{j<i} { [a_j>a_i]}，又因为 i 本身是后缀最小值，所以 \forall i<j,a_i<a_j，定义 U 为全集，所以贡献转化为 k,j \in U ,i<j,\sum {[a_k>a_i] - \sum [j]}。可以树状数组维护全局后缀最小值位置，后缀最小值 a，全局位置集合，全局 a 集合。以及某个数成为全局最小值的时间，在时间序列上做扫描线 总时间复杂度 O(n \log n)。

Code:

#include<bits/stdc++.h>
#define ll long long
#define N 100010
#define il inline
#define hsh_mod 2147483647
using namespace std;
il int read(){
    int x=0,f=0;
    char c=getchar();
    while(!isdigit(c)){
        f|=c=='-';
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-48;
        c=getchar();
    }
    return f?-x:x;
}
int n,q,a[N];
struct BIT{
    int c[N];
    void add(int i,int v){
        for(;i<=n+1;i+=i&-i) c[i]+=v;
    }
    int query(int i){
        int res=0;
        for(;i;i-=i&-i) res+=c[i];
        return res;
    }
}setS,posS,setA,posA;
ll ans;
struct BITMX{
    int c[N];
    void add(int i,int v){
        for(;i<=n+1;i+=i&-i) c[i]=max(c[i],v);
    }
    int query(int i){
        int res=0;
        for(;i;i-=i&-i) res=max(res,c[i]);
        return res;
    }
}bitmx;
int del[N],X[N];
vector<pair<int,int>> G[N];
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0),cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        del[i]=q+1;
    }
    for(int i=1,x;i<=q;i++){
        cin>>x;
        X[i]=x;
        del[x]=i;
    }
    for(int i=n;i>=1;i--){
        int r=del[i],l=bitmx.query(a[i]-1)+1;
        if(l<=r){
            G[l].emplace_back(i,1);
            G[r+1].emplace_back(i,-1);
        }
        bitmx.add(a[i],del[i]);
    }
    for(int i=1;i<=n;i++){
        setA.add(a[i],1);
        posA.add(i,1);
    }
    for(int t=1;t<=q+1;t++){
        if(t>1){
            int p=X[t-1];
            ans-=(setS.query(a[p]-1)-posS.query(p-1));
            setA.add(a[p],-1);
            posA.add(p,-1);
        }
        for(auto ppp:G[t]){
            int x,id;
            tie(x,id)=ppp;
            if(id==1){
                ans+=setA.query(n)-setA.query(a[x]);
                ans-=posA.query(n)-posA.query(x);
                setS.add(a[x], 1);
                posS.add(x, 1);
            }else {
                ans-=setA.query(n)-setA.query(a[x]);
                ans+=posA.query(n)-posA.query(x);
                setS.add(a[x],-1);
                posS.add(x,-1);
            }
        }
        cout<<ans+n-t+1<<' ';
    }
}