自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:03:04，当前版本为作者最后更新于2023-07-10 20:50:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P4732 题解

Problem Link

题目大意

给定一个变量 $x$，初始为 $0$，依次进行 $n$ 种操作，每次操作有一个优先级 $p_i$，操作有如下两种：

• 令 $x\gets v$，对于所有的赋值操作，$p_i=0$。
• 找到此前第一个未被撤销的操作 $j$ 满足 $p_j<p_i$，可以撤销某个撤销操作，此时重新加入被 $j$ 撤销的操作。

每次操作后输出 $x$。

数据范围 $n\le 3\times 10^5$。

思路分析

考虑前 $i-1$ 个操作中未被撤销的，注意到对于两个操作 $j,k$，若 $p_j>p_k,j<k$，则此次操作必然不可能直接撤销 $j$，因此所有可能被 $i$ 直接撤销的操作构成一个单调栈。

考虑撤销栈顶 $p_j$，然后考虑前 $i$ 个操作构成的单调栈，显然 $(j,i]$ 中不会有操作被加入这个单调栈中，因为这些操作都满足 $p_j\ge p_i$，因此新的单调栈和 $j-1$ 时刻的单调栈相同，只需要加入 $i$ 操作。

用主席树维护单调栈即可。

时间复杂度 $\mathcal O(n\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5,INF=1e9;
class SegmentTree {
    private:
        struct Node {
            int ls,rs,min;
            Node() { ls=0,rs=0,min=INF; }
        }    tr[MAXN*20];
        inline void pushup(int p) { tr[p].min=std::min(tr[tr[p].ls].min,tr[tr[p].rs].min); }
        int siz;
    public:
        inline void Insert(int u,int v,int l,int r,int q,int &p) {
            p=++siz;
            if(l==r) return tr[p].min=min(v,tr[q].min),void();
            int mid=(l+r)>>1;
            if(u<=mid) tr[p].rs=tr[q].rs,Insert(u,v,l,mid,tr[q].ls,tr[p].ls);
            else tr[p].ls=tr[q].ls,Insert(u,v,mid+1,r,tr[q].rs,tr[p].rs);
            pushup(p);
        }
        inline int Query(int u,int l,int r,int p) {
            if(l==r) return l;
            int mid=(l+r)>>1;
            if(tr[tr[p].rs].min<u) return Query(u,mid+1,r,tr[p].rs);
            return Query(u,l,mid,tr[p].ls);
        }
}    TR;
int a[MAXN],rt[MAXN],val[MAXN];
signed main() {
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&a[i]);
        if(a[i]>0) val[i]=a[i],TR.Insert(i,0,1,n,rt[i-1],rt[i]);
        else {
            int t=TR.Query(-a[i],1,n,rt[i-1]);
            TR.Insert(i,-a[i],1,n,rt[t-1],rt[i]);
            val[i]=val[t-1];
        }
        printf("%d\n",val[i]);
    }
    return 0;
}