题解：P12485 [集训队互测 2024] PM 大师

concert_B · 2025-07-17 16:23:08 · 题解

P12485 [集训队互测 2024] PM 大师题解

tip

date:2025/7/17,DAY11

本题是模拟赛 T4，Clonoth 也是直接把他集训队的题搬来了，不过神奇的是题解就一篇，提交人数达惊人的 10 个入。

本人迫不得已只能把官方题解改了一下搬来了。思路不是我的，希望 Clonoth 不会发现。

本题其实难在思考过程，如果真弄懂了代码其实不难，树状数组和线段树都比较板（特指黑题），但真的好难理解啊啊啊。存好大脑，开始了。

以下认为 n,q 同阶。

做法 1

考虑 O(n) 地由 a 生成出 b。

按照 i=1,2,\ldots,n 遍历数组 a，同时维护 vis_i 表示 i 是否已经在 b 中出现过。当 a_i\ne 0 时，vis_i \gets \text{true} ；当 a_i=0 时，b_i 初始设置为上一个 a_p=0 位置的 b_p，然后使 b_i \gets b_i + 1 直到 vis_{b_i} = \text{false} 。

时间复杂度 O(n^2)，可以通过子任务 1。

code

蒟蒻的考场代码。

while(q--){
    cin>>x>>k>>y; 
    a[x]=k;
    if(a[y]!=0){
        cout<<a[y]<<'\n';
        continue;
    }
    for(int j=1;j<=n;j++)
        fa[j]=j;
    for(int j=1;j<=n;j++){
        if(a[j]==-1)    continue;
        if(a[j]==0){
            int b=find(1);
            if(j==y){
                cout<<b<<'\n';
                break;
            }
            fa[find(b)]=find(b+1);
            continue;
        }
        fa[find(a[j])]=find(a[j]+1);
    }
}

并查集的作用就是 vis，已经出现过的和 1 合并，暴力的比 O(n^2) 优美一点悲。

做法 2

考虑解决子任务 2。

注意到存在集合 S\subseteq \{1,2,…,n\} 满足对于 a_i 中的第 i 个 a_x=0，满足 b_x 等于 S 中的第 i 小的数。

此时 x \in S 等价于不存在 a_i=x。

使用树状数组或平衡树等数据结构维护插入、删除、求 k 小值即可。 时间复杂度 O(n \log n)，可以通过子任务 2。

code

来自 HZ 巨佬的代码 orz：

void add(int x,int k){
    for(int i=x;i<=n;i+=i&-i)
        tr[i]+=k;
    return;
}
int qry(int x) {
    int res=0;
    while(x){
        res+=tr[x];
        x-=x&-x;
    }
    return res;
}
int K=n+1;
for(int i=1;i<=n;i++)
    if(a[i]==0){
        K=i;
        break;
    }
for(int i=1;i<=q;i++){
    if(a[x[i]]!=-1){
        cnt[a[x[i]]]--;
        if(!cnt[a[x[i]]])
            add(a[x[i]],-1);
    }
    if(k[i]!=-1){
        if(!cnt[k[i]])
            add(k[i],1);
        cnt[k[i]]++;
    }
    a[x[i]]=k[i];
    if(y[i]<K)  cout<<a[y[i]]<<'\n';
    else{
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if (mid-qry(mid)<y[i]-K+1)  l=mid+1;
            else    r=mid;
        }
        cout<<l<<'\n';
    }
}

做法 3

考虑解决子任务 5。 首先此时原问题等价于在初始全为 0 的序列 a 中任意插入正数。

不难注意到，满足做法 2 中所述性质的集合 S 在一般的情况下也存在，这启发我们动态的维护 S 而不是数组 b。

以下我们假设 a 中的正数互不相同，若存在相同仅保留第一个即可（标程的堆中 update 操作的意义）。由此，定义 pos_i 表示 i 出现的位置。

在任何时刻，对于 a_i，a_i \notin S 等价于 i 之前最近的 a_p=0 的 b_p<a_i。因此，只要维护了集合 S，在一次 a_x \gets k 的修改操作中，可以轻易得到是否需要将 k 从 S 中删除。

但在一次修改操作中，可能会引起需要往 S 中加入一些数（由将 k 从 S 中删除所引起的 b 的改变）。对于 j \notin S 定义 f_i=\sum_{x \in S} [x \le j]-c_{pos_j}，其中 c_i 表示 a 数组中 a_i 之前有多少个 0。容易发现 j \notin S 时 f_j \ge 0；而一旦出现 f_j < 0 则需要将 j 加入到 S 中。

那么每次修改对 f_j 的修改即为从 k 开始的一段前缀减 1，直到出现 f_j=0 为止。 使用线段树维护 f_j，时间复杂度 O(n\log n)，可以通过子任务 1,5。

tip

文中 pos 可以用堆维护，f 可以用线段树维护，维护插入、删除、求 k 小值与做法 2 类似，标程用树状数组。

code

inline void insert_check(int x){
    int k=a[x];
    if(pos[k].top()!=x)
        return;
    int u=b.kth(pre[x]);
    if(u<k){
        if(!in[k]){
            if(k<n){
                int i=f.find(1,1,n,k+1,n);
                if(i){
                    f.modify(1,1,n,i,inf);
                    g.modify(1,1,n,i,0);
                    b.add(i,1);
                    in[i]=false;
                    ++X;
                }
                else
                    i=n+1;
                if(i<=n)
                    Sum+=i-k;   
                if(k+1<i)
                    g.update(1,1,n,k+1,i-1,1);
            }
            b.add(k,-1);
            in[k]=1;
        }
        f.modify(1,1,n,k,b.ask(k)-pre[x]);
        g.modify(1,1,n,k,inf);
    }
    else{
        g.modify(1,1,n,k,pre[x]-b.ask(k));
        f.modify(1,1,n,k,inf);
    }
    return;
}

inline void insert(int x,int k){
    a[x]=k;
    if(k==-1)
        return;
    pos[k].insert(x);
    insert_check(x);
    return;
}

做法 4

首先原问题等价于在初始全为 0 的序列 a 中任意插入或删除正的数。

注意到在做法 3 中，每次操作对 S 的改变都是 O(1) 的，这启发我们使用类似的方式处理删除操作。

对称的，对于 j \in S 定义 g_i=c_{pos_j}-\sum_{}x \in S [x \le j]。此时也有 j \in S 时 g_j>0；而一旦出现 g_j<0 则需要将 j 从 S 中删除。

修改的形式也是类似的。但值得注意的是，在对 f_j（或 g_j）执行从 k 开始的一段前缀减 1 操作时，也需要在 f_j（或 g_j）中对这一段区间进行加 1 的操作。

使用线段树维护 f_j,g_j，时间复杂度 O(n \log n)，可以通过所有子任务。

code

inline void erase(int x){
    int k=a[x];
    if(k==-1)
        return;
    pos[k].erase(x);
    if(!pos[k].empty()&&pos[k].top()<x)
        return;
    if(in[k]){
        if(k<n){
            int i=g.find(1,1,n,k+1,n);
            if(i){
                f.modify(1,1,n,i,0);
                g.modify(1,1,n,i,inf);
                b.add(i,-1);
                in[i]=true;
                ++Y;
            }
            else
                i=n+1;
            if(i<=n)
                Sum+=i-k;
            if(k+1<i)
                f.update(1,1,n,k+1,i-1,1);
        }
        in[k]=false;
        b.add(k,1);
    }
    f.modify(1,1,n,k,inf);
    g.modify(1,1,n,k,inf);
    if(!pos[k].empty())
        insert_check(pos[k].top());
    return;
}

重构过的代码

封装好了，有需自取。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,inf=1e9;
int n,m;
int a[N],pre[N];
bool in[N];

struct heap{
    priority_queue<int,vector<int>,greater<int>> p,q;
    inline void insert(int x){
        p.push(x);
        return;
    }
    inline void erase(int x){
        q.push(x);
        return;
    }
    inline void update(){
        while(!p.empty()&&!q.empty()&&p.top()==q.top())
            p.pop(),q.pop();
        return;
    }
    inline bool empty(){
        update();
        return p.empty();
    }
    inline int top(){
        update();
        return p.top();
    }
    inline void clear(){
        while(!p.empty())
            p.pop();
        while(!q.empty())
            q.pop();
        return;
    }
}pos[N];

struct BIT{
    int bit[N];
    inline int lowbit(int x){
        return x&-x;
    }
    inline void add(int x,int k){
        for(int i=x;i<=n;i+=lowbit(i))
            bit[i]+=k;
        return;
    }
    inline int ask(int x){
        int ans=0;
        for(int i=x;i;i-=lowbit(i))
            ans+=bit[i];
        return ans;
    }
    inline int kth(int k){
        if(!k)  return 0;
        int i=0,s=0;
        for(int w=log2(n);w!=-1;--w){
            int j=i+(1<<w);
            if(j<=n&&s+bit[j]<k)
                s+=bit[j],i=j;
        }
        return i+1;
    }
}b;

struct segment_tree{
    static const int Size=(1<<21)+10;
    int sum[Size],tag[Size];
    inline void push_up(int p){
        sum[p]=min(sum[p<<1],sum[p<<1|1]);
        return;
    }
    inline void push_down(int p){
        if(tag[p]){
            sum[p<<1]+=tag[p];
            sum[p<<1|1]+=tag[p];
            tag[p<<1]+=tag[p];
            tag[p<<1|1]+=tag[p];
            tag[p]=0;
        }
        return;
    }
    int find(int p,int l,int r,int x,int y){
        if(r<x||l>y)    return 0;
        if(x<=l&&r<=y&&sum[p]){
            sum[p]--;
            tag[p]--;
            return 0;
        }
        if(l==r)    return l;
        push_down(p);
        int mid=l+r>>1;
        int ans=0;
        ans+=find(p<<1,l,mid,x,y);
        if(ans) return ans;
        ans+=find(p<<1|1,mid+1,r,x,y);
        return ans;
    }
    void update(int p,int l,int r,int x,int y,int k){
        if(l>y||r<x)    return;
        if(x<=l&&r<=y){
            sum[p]+=k;
            tag[p]+=k;
            return;
        }
        push_down(p);
        int mid=l+r>>1;
        update(p<<1,l,mid,x,y,k);
        update(p<<1|1,mid+1,r,x,y,k);
        push_up(p);
        return;
    }
    void modify(int p,int l,int r,int x,int k){
        if(r<x||l>x)    return;
        if(l==r){
            sum[p]=k;
            return;
        }
        push_down(p);
        int mid=l+r>>1;
        modify(p<<1,l,mid,x,k);
        modify(p<<1|1,mid+1,r,x,k);
        push_up(p);
        return;
    }
    void build(int p,int l,int r){
        tag[p]=0;
        if(l==r){
            sum[p]=inf;
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        push_up(p);
        return;
    }
}f,g;
int X,Y;
long long Sum=0;

inline void insert_check(int x){
    int k=a[x];
    if(pos[k].top()!=x)
        return;
    int u=b.kth(pre[x]);
    if(u<k){
        if(!in[k]){
            if(k<n){
                int i=f.find(1,1,n,k+1,n);
                if(i){
                    f.modify(1,1,n,i,inf);
                    g.modify(1,1,n,i,0);
                    b.add(i,1);
                    in[i]=0;
                    ++X;
                }
                else
                    i=n+1;
                if(i<=n)
                    Sum+=i-k;   
                if(k+1<i)
                    g.update(1,1,n,k+1,i-1,1);
            }
            b.add(k,-1);
            in[k]=1;
        }
        f.modify(1,1,n,k,b.ask(k)-pre[x]);
        g.modify(1,1,n,k,inf);
    }
    else{
        g.modify(1,1,n,k,pre[x]-b.ask(k));
        f.modify(1,1,n,k,inf);
    }
    return;
}

inline void insert(int x,int k){
    a[x]=k;
    if(k==-1)
        return;
    pos[k].insert(x);
    insert_check(x);
    return;
}

inline void erase(int x){
    int k=a[x];
    if(k==-1)
        return;
    pos[k].erase(x);
    if(!pos[k].empty()&&pos[k].top()<x)
        return;
    if(in[k]){
        if(k<n){
            int i=g.find(1,1,n,k+1,n);
            if(i){
                f.modify(1,1,n,i,0);
                g.modify(1,1,n,i,inf);
                b.add(i,-1);
                in[i]=1;
                ++Y;
            }
            else
                i=n+1;
            if(i<=n)
                Sum+=i-k;
            if(k+1<i)
                f.update(1,1,n,k+1,i-1,1);
        }
        in[k]=0;
        b.add(k,1);
    }
    f.modify(1,1,n,k,inf);
    g.modify(1,1,n,k,inf);
    if(!pos[k].empty())
        insert_check(pos[k].top());
    return;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        pre[i]=pre[i-1]+!a[i];
    }
    f.build(1,1,n);
    g.build(1,1,n);
    for(int i=1;i<=n;++i)
        b.add(i,1);
    int x,k,y;
    while(m--){
        cin>>x>>k>>y;
        erase(x);
        insert(x,k);
        if(a[y]!=0) cout<<a[y]<<'\n';
        if(a[y]==0) cout<<b.kth(pre[y])<<'\n';
    }
#define _ 0
    return ~~(0^_^0);
}

完结散花！！！