P4732 题解

· · 题解

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;
}