[DS记录]P7476 苦涩

**题意** ： 维护 $n$ 个多重集 $S_{1\sim n}$ ，初始时均为空集。 支持下列操作 ： - 向 $S_{l\sim r}$ 中加入 $x$ - 记 $x=\max_{i\in[l,r]}\max S_i$ ，对于 $k\in [l,r]$ ，若 $\max S_k=x$ ，则从 $S_k$ 中删去一个 $x$。 - 查询 $\max_{i\in[l,r]}\max S_i$ ，或指出 $S_{l\sim r}$ 均为空。 $n,m\leq 2\times10^5$ ，时限$\texttt{1s}$。 ------------ 使用标记永久化，在每个节点用一个堆维护标记。 进行操作 $2$ 时，假设修改的是 $[L,R]$ ，先查询出 $x$ 的值，然后尝试删除。 下放区间 $[l,r]$ 的标记时，若堆顶为 $x$ （由于此时 $[l,r]$ 和 $[L,R]$ 必然有交，堆顶不可能 $>x$ ），则弹出，并将 $x$ 重新加入到区间 $[l,L),(R,r]$ 中（相当于两个 $1$ 操作）。 某次上述操作执行成功后，直接返回，因为 $x$ 只会被删除一个。 此外，若区间 $\max<x$ ，也无需操作。 其余情况，暴力递归。 下面证明复杂度。 我们发现，暴力递归的复杂度不会大于标记深度和，于是只考虑插入标记的操作，并统计其深度和。 每次 $1$ 操作新建的标记的深度和显然为 $O(\log^2n)$。 在 $2$ 操作中，只有与 $[L,R]$ 部分相交的两个线段树节点可能产生 $1$ 操作。增加的标记的深度和也是 $O(\log^2n)$。 复杂度均摊正确， 为 $O((n+m)\log^2n)$。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define MaxN 200500 using namespace std; struct Node{ int x; priority_queue<int> q; }a[1<<19|500]; inline void up(int u) {a[u].x=max(a[u].q.top(),max(a[u<<1].x,a[u<<1|1].x));} void build(int l,int r,int u) { a[u].q.push(-1);a[u].x=-1; if (l==r)return ; int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(u); } int wfl,wfr,wfc; void add(int l,int r,int u) { if (wfl<=l&&r<=wfr){ a[u].q.push(wfc); a[u].x=max(a[u].x,wfc); return ; }int mid=(l+r)>>1; if (wfl<=mid)add(l,mid,u<<1); if (mid<wfr)add(mid+1,r,u<<1|1); up(u); } int n,sl[5],sr[5],tn; void del(int l,int r,int u) { if (a[u].x<wfc)return ; if (a[u].q.top()==wfc){ a[u].q.pop(); if (l==r)a[u].x=a[u].q.top(); else up(u); sl[++tn]=l;sr[tn]=min(wfl-1,r); if (sl[tn]>sr[tn])tn--; sl[++tn]=max(wfr+1,l);sr[tn]=r; if (sl[tn]>sr[tn])tn--; return ; }int mid=(l+r)>>1; if (wfl<=mid)del(l,mid,u<<1); if (mid<wfr)del(mid+1,r,u<<1|1); up(u); } int ret; void qry(int l,int r,int u) { ret=max(ret,a[u].q.top()); if (wfl<=l&&r<=wfr){ret=max(ret,a[u].x);return ;} int mid=(l+r)>>1; if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } int m; int main() { scanf("%d%d",&n,&m); build(1,n,1); for (int i=1,op;i<=m;i++){ scanf("%d%d%d",&op,&wfl,&wfr); if (op==1){scanf("%d",&wfc);add(1,n,1);} if (op==2){ ret=-1;qry(1,n,1); wfc=ret;tn=0;del(1,n,1); for (int j=1;j<=tn;j++) {wfl=sl[j];wfr=sr[j];add(1,n,1);} } if (op==3){ ret=-1;qry(1,n,1); printf("%d\n",ret); } }return 0; } ```