题意是给定 n(<= 2e5) 个区间,然后给出 m(<= 2e5) 个操作,操作数为 p 表示把含有 p 这个数的区间都删去,且记录删除时的操作号码;最终输出每次操作删除的区间数,以及每个区间被删除时的操作号码。
这个题其实还能再难一点,每个操作给出 p,q 两个操作数,要求把与 [p,q] 相交的所有区间删去。(这道题就看成是 p=q 的特例吧)
对于一个区间 [l,r],与 [p,q] 相交,可以分两种情况讨论:
- 对于 l<= p 的:p <= r
- 对于 l>p 的:l<= q
我们建一棵 treap, 它是可以在 O(log n) 的复杂度进行合并和分割的平衡二叉树,把区间左端点为第一关键字,把区间右端点为第二关键字,都是从小到大排,操作时把 treap 按 [p,q] 分割成两棵,叫左半边和右半边吧,左半边有着情况 1 要的点,右半边有着情况 2 要的点。
观察1: 右半边关键字最小的点都不满足 l<= q 的话,整个右半边都不满足。
观察2: 对于左半边的点,我们维护它的子树的区间右界能达到的最大值 rmax, 如果不满足 p <= rmax ,那么整棵子树都不满足。
这个图可以作为一个例子(这个图是网上借来的) ,每个节点下面打粗体的就是 rmax ,比方说 p=42, 到了根节点一看,左孩子的 rmax 不够,左孩子那棵 3 个节点的子树统统不用考虑,直接看右孩子就行了。
值得注意的是这是一个摊还算法,应对每个操作的复杂度最好情况下是 O(log n),最坏情况下是 O(nlog n), 因为可能一次操作把所有区间都给删了,但是总体复杂度还是 O((n+m)log n)。
最后贴个代码。。
#include <cassert> #include <cstdio> #include <algorithm> #include <cstring> #include <tuple> using namespace std; typedef long long LL; const int mod=998244353; inline int addmod(int x, int y){ x+=y; return x>=mod?x-mod:x; } inline int mulmod(LL x, int y){ x*=y; return x>=mod?x%mod:x; } const int N=2e5+5, T=N; const int oo=mod<<1; #define left get<0> #define right get<1> #define index get<2> typedef tuple<int,int,int> P; int fix[T], lch[T], rch[T], siz[T]; P key[T]; int rmax[T], ans[N]; int tot, root; inline void reset() { rmax[0]=-oo, root=0; tot=1; } inline int newnode(P const& x){ int t=tot; ++tot; assert(tot<=T); lch[t]=rch[t]=0, siz[t]=1; fix[t]=rand()<<15|rand(); key[t]=x; rmax[t]=right(key[t]); return t; } inline void pushdown(int){} inline void update(int t){ siz[t]=siz[lch[t]]+1+siz[rch[t]]; rmax[t]=max(right(key[t]), max(rmax[lch[t]],rmax[rch[t]])); } void split(int t, int k, int &l, int &r){ if(!t){l=r=0; assert(k==1); return;} pushdown(t); int tk=siz[lch[t]]+1; if(k<=tk){ split(lch[t], k, l,lch[t]); r=t; }else{ split(rch[t], k-tk, rch[t],r); l=t; } update(t); } void join(int &t, int l, int r){ if(!l){t=r; return;} if(!r){t=l; return;} if(fix[l]>fix[r]){ pushdown(t=l); join(rch[l],rch[l],r); }else{ pushdown(t=r); join(lch[r],l,lch[r]); } update(t); } int order(int t, P x){ if(!t)return 1; pushdown(t); if(key[t]<x)return siz[lch[t]]+1+order(rch[t],x); return order(lch[t],x); } inline void insert(P const& x){ int l, r, k=order(root,x), t=newnode(x); split(root, k, l, r); join(r, t, r); join(root, l, r); } inline void erase(P const& x){ int l, r, t, k=order(root,x); split(root, k, l, r); split(r, 2, t, r); join(root, l, r); } int _checkrmax(int t, int p){ if(p <= right(key[t])) return t; if(p <= rmax[lch[t]]) return _checkrmax(lch[t], p); if(p <= rmax[rch[t]]) return _checkrmax(rch[t], p); abort(); } int _checkleft(int t, int q){ if(!t) return 0; if(left(key[t]) <= q) return t; return _checkleft(lch[t], q); } int intersect(P x){ int l, r, k=order(root,x); split(root, k, l,r); int res; if(left(x) <= rmax[l]){ res = _checkrmax(l, left(x)); }else{ res = _checkleft(r, right(x)); } join(root, l, r); return res; } int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL srand(19970518); int tac; scanf("%d",&tac); for(int tic=1; tic<=tac; ++tic){ printf("Case #%d:\n",tic); int n, zo; scanf("%d%d",&n,&zo); reset(); for(int i=1; i<=n; ++i){ int l, r; scanf("%d%d",&l,&r); insert(P(l,r,i)); ans[i] = 0; } int res=0; for(int ko=1; ko<=zo; ++ko){ int y; scanf("%d",&y); int x = res^y; res=1; int cnt=0, t; while((t=intersect(P(x,x,0)))){ ++cnt; int u = index(key[t]); res=mulmod(res,u); ans[u]=ko; erase(key[t]); } if(cnt==0)res=0; printf("%d\n",cnt); } for(int i=1; i<=n; ++i){ printf("%d%c",ans[i]," \n"[i==n]); } } return 0; }
全部评论
(1) 回帖