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

· · 题解

无脑树套树做法

考试时只会一个树套树的做法。

首先一个人下去之后回来时肯定贪心地将 a_i 小的放前面。

乍一看很像 P3157 [CQOI2011] 动态逆序对，但发现有些人的贡献不能算（一个人 i 的贡献为满足 j<i 且 a_j > a_i 的 j 的数量）。

如果人 i 的后面存在一个人 k 使得 a_k < a_i，那么人 i 的贡献就不能算了，因为前面所有人会在 k 下去时排好序。

那么我们对每一个人记录他后面所有比他小的人的离开时间的最大值（树状数组简单维护），就可以知道每个人从什么时刻可以开始算贡献。如果把树状数组换成线段树在线维护可以做到在线，但没必要。

剩下的就是动态逆序对了，开两棵树套树。一棵维护当前存在的人数，一棵维护存在的可以算贡献的人数。

我写的树状数组套线段树，时空复杂度 O(n\log^2n)，可以通过（很慢就是了）。

Code:

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
        while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x*=f;
    }
    const int BUF=1<<21;
    char buf[BUF],tp,st[32];
    int plen;
    #define flush() fwrite(buf,1,plen,stdout),plen=0
    inline void pc(char c){
        buf[plen++]=c;
        if(plen==BUF) flush();
    }
    template<typename T>inline void print(T x){
        if(!x){pc(48);return;}
        if(x<0) x=~x+1,pc('-');
        while(x) st[++tp]=48^x%10,x/=10;
        while(tp) pc(st[tp--]);
    }
}
using namespace IO;
const int N=1e5+5;
int n,q,a[N],b[N],tot,ti[N];
struct Tree{
    int ls,rs,cnt;
}t[N*360];
#define mid ((l+r)>>1)
void change(int &p,int l,int r,int x,int y){
    if(!p) p=++tot;
    t[p].cnt+=y;
    if(l<r){
        if(x<=mid) change(t[p].ls,l,mid,x,y);
        else change(t[p].rs,mid+1,r,x,y); 
    }
}
int query_(int p,int l,int r,int lt,int rt){
    if(!p) return 0;
    if(lt<=l&&r<=rt) return t[p].cnt;
    int ans=0;
    if(lt<=mid) ans=query_(t[p].ls,l,mid,lt,rt);
    if(mid<rt) ans+=query_(t[p].rs,mid+1,r,lt,rt);
    return ans;
}
struct Tree_in_Tree{
    int root[N];
    inline void add(int x,int y,int v){for(;x<=n;x+=x&-x) change(root[x],1,n,y,v);}
    inline int query(int x,int y,int l,int r){
        if(x>y||l>r) return 0;
        int ans=0;
        for(--x;x;x-=x&-x) ans-=query_(root[x],1,n,l,r);
        for(;y;y-=y&-y) ans+=query_(root[y],1,n,l,r);
        return ans;
    }
}C,T;
struct Bit_tree{
    int mx[N];
    inline void add(int x,int y){for(;x<=n&&mx[x]<y;x+=x&-x) mx[x]=y;}
    inline int query(int x){
        int ans=0;
        for(;x;x-=x&-x) ans=max(ans,mx[x]);
        return ans;
    }
}B;
vector<int> P[N];
long long ans;
bool vis[N];
int main(){
    read(n),read(q);
    for(int i=1;i<=n;++i){
        read(a[i]);
        C.add(i,a[i],1);
        ti[i]=n+1;
    }
    for(int i=1;i<=q;++i) read(b[i]),ti[b[i]]=i;
    for(int i=n;i;--i){
        int qq=B.query(a[i]);
        if(qq<=q&&qq<=ti[i]) P[qq].push_back(i);
        B.add(a[i],ti[i]);
    }
    for(int j:P[0]){
        ans+=C.query(1,j-1,a[j]+1,n);
        T.add(j,a[j],1);
        vis[j]=1;
    }
    ans+=n;
    print(ans),pc(' ');
    for(int t=1;t<=q;++t){
        C.add(b[t],a[b[t]],-1);
        ans-=T.query(b[t]+1,n,1,a[b[t]]-1);
        if(vis[b[t]]){
            ans-=C.query(1,b[t]-1,a[b[t]]+1,n);
            T.add(b[t],a[b[t]],-1);
        }
        for(int j:P[t]){
            ans+=C.query(1,j-1,a[j]+1,n);
            T.add(j,a[j],1);
            vis[j]=1;
        }
        print(--ans),pc(' ');
    }
    flush();
    return 0;
}