题解：P11695 [JRKSJ ExR] 昼寝
underthetime
·
·
题解
题意
给定 n,m，你需要维护一个 [1,n] 的数轴上区间的初始为空的可重集合，支持三种操作共 m 次：
- 插入一个区间 [l,r]。
- 删除之前插入的某个区间。
- 给出一个区间 [l,r]，判断当前可重集合中是否存在一个子集，使得子集中所有区间的并恰好是 [l,r]。
## 题解
第一步显然是把区间加删看成每个区间有一个时间区间 $[tl,tr]$。数轴上撒区间的一个经典模型是猫树分治，对数轴分治，把每个操作区间和询问区间存在从上往下第一个跨过分治中心的分治区间上，现在考虑在分治区间 $[l,r]$ 上的所有询问，且 $mid=\left\lfloor\frac{l+r}{2}\right\rfloor$。
可能对 $[l,r]$ 上的询问有用的区间只在 $[l,r]$ 及其对应猫树节点的子树里。那么进行分类讨论：
### 在 $\bold{[l,r]}$ 上的区间
设这些区间为 $[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$。由于都跨过了 $mid$，所以对于时刻 $t$ 的询问 $[ql,qr]$，只需分别找到被 $[ql,qr]$ 包含的区间中最小的左端点、最大的右端点就知道了这部分区间对 $[ql,qr]$ 的贡献。以找左端点为例，求的就是满足 $ql\le l_i,r_i\le qr,tl_i\le t\le tr_i$ 的 $i$ 中 $l_i$ 的最小值。比较直接的方法是把询问和操作按照右端点扫描线用树套树维护，复杂度双 $\log$，经过实践这种方法稳定超时。考虑按照时间维度扫描线，用 $n$ 个 set 对所有 $i\in[1,n]$ 维护 $cls_i$ 表示当前所有 $l_j=i$ 的区间中 $r_j$ 的最小值（若没有则 $cls_i=+\infty$），那么当扫到一个询问 $[ql,qr]$ 时相当于求最小的 $j$ 使得 $j\in[ql,mid]$ 且 $cls_r\le qr$，用线段树维护区间 $cls$ 最小值后线段树二分即可做到单 $\log$。
### 在 $\bold{[l,r]}$ 的子树里的区间
这些区间满足 $r_i\le mid$ 或 $l_i>mid$。在上一部分完成后每个询问未覆盖的区间分别在 $mid$ 的两侧。对于时刻 $t$ 的询问 $[ql,qr]$，以覆盖它的左侧为例，暴力的做法是：找到一个 $l_i=ql,tl_i\le t\le tr_i$ 的区间 $[l_i,r_i]$ 进行覆盖，再找到 $l_j\le r_i+1,tl_j\le t\le tr_j$ 的区间进行覆盖，直到找不到区间，此时检查这部分完成的覆盖是否能和上个部分接上。我们考虑对这一层所有询问一起进行这个过程，将询问和操作区间按照左端点排序，每扫到一个询问就说明在这之后的操作都可以对这个询问有贡献，每扫到一个操作就会对时间在某个区间中的、已经扫到的询问的覆盖到的位置进行 chkmax 的操作。假设当前考虑到左端点 $p$，在操作完所有左端点在 $p$ 的区间后覆盖位置仍 $\le p$ 的询问显然不能进一步覆盖了。于是我们开一个时间轴上的线段树维护区间中覆盖到的位置的最小值及其对应时刻，扫到一个询问时把它加到线段树上，扫到一个操作就区间 chkmax，每考虑完一个左端点后就暴力检查全局最小值是否 $\le p$，是的话就暴力删除。这样做每个询问至多被加入一次，每个操作至多被 $O(\log n)$ 个分治区间考虑，因此这部分时间复杂度 $O(m\log n\log m)=O(m\log^2n)$。
总时间复杂度 $O(m\log^2n)$。
## 代码
或许需要卡一大把常？
```cpp
#include<bits/stdc++.h>
bool MemoryST;using namespace std;
typedef long long ll;
constexpr int inf=0x3f3f3f3f;
template<typename T>void chkmax(T&x,T y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,T y){if(x>y)x=y;}
#define cost_space (abs(&MemoryST-&MemoryED)/1024.0/1024.0)<<"MB"
constexpr int maxn=1e6+5,maxm=5e5+5;
constexpr char*str="NY";
struct opr{int l,r,tl,tr;}opt[maxm];struct qry{int l,r,t;}que[maxm];
int n,Q,ocnt,qcnt,opt_id[maxm];
/*
省略快读快写
*/
vector<opr>seg[maxn<<2];vector<qry>ask[maxn<<2];// seg[rt]：存在编号为 rt 的分治区间上的操作区间，ask[rt] 存询问区间
bitset<maxm>ans;vector<opr>itv_lft[maxn<<2],itv_rgt[maxn<<2];// 分别存分治区间 rt 左子树、右子树的操作区间
void insopt(opr cur){
for(int l=1,r=n,rt=1;;){// 采用非递归实现
int mid=(l+r)>>1;if(l==r||cur.l<=mid&&mid<cur.r)[[unlikely]]{seg[rt].push_back(cur);return;}// 神秘冷热代码常数优化
if(cur.r<=mid)itv_lft[rt].push_back(cur),r=mid,rt<<=1;
else itv_rgt[rt].push_back(cur),l=mid+1,rt=rt<<1|1;
}
}void insque(qry cur){
for(int l=1,r=n,rt=1;;){
int mid=(l+r)>>1;if(l==r||cur.l<=mid&&mid<cur.r)[[unlikely]]{ask[rt].push_back(cur);return;}
if(cur.r<=mid)r=mid,rt<<=1;
else l=mid+1,rt=rt<<1|1;
}
}
pair<int,int>rng[maxm],rng2[maxm];// 分别表示仅用 [l,r] 上的区间能完成覆盖的部分，和用 [l,r] 子树的线段在两端覆盖到的位置
// 第一部分的线段树，lft 和 rgt 后缀分别代表左侧和右侧的信息
int cls_lft[maxn<<1],cls_rgt[maxn<<1],cnt;
multiset<int>rec_lft[maxn],rec_rgt[maxn];pair<int,pair<int,pair<int,int>>>evt[maxm<<1];
inline void update_lft(int rt){cls_lft[rt]=min(cls_lft[rt<<1],cls_lft[rt<<1|1]);}
inline void modify_lft(int l,int r,int rt,int now,int k){
while(l<r){int mid=(l+r)>>1;if(now<=mid)r=mid,rt<<=1;else l=mid+1,rt=rt<<1|1;}
cls_lft[rt]=k;for(rt>>=1;rt;rt>>=1)update_lft(rt);
}inline void update_rgt(int rt){cls_rgt[rt]=max(cls_rgt[rt<<1],cls_rgt[rt<<1|1]);}
inline void modify_rgt(int l,int r,int rt,int now,int k){
while(l<r){int mid=(l+r)>>1;if(now<=mid)r=mid,rt<<=1;else l=mid+1,rt=rt<<1|1;}
cls_rgt[rt]=k;for(rt>>=1;rt;rt>>=1)update_rgt(rt);
}inline void ins(int L,int R,int l,int r){
int mid=(L+R)>>1;
if(*rec_lft[l].begin()>r)modify_lft(L,mid,1,l,r);rec_lft[l].insert(r);
if(*rec_rgt[r].rbegin()<l)modify_rgt(mid+1,R,1,r,l);rec_rgt[r].insert(l);
}inline void del(int L,int R,int l,int r){
int mid=(L+R)>>1;rec_lft[l].erase(rec_lft[l].find(r)),rec_rgt[r].erase(rec_rgt[r].find(l));
int cur_l=*rec_lft[l].begin(),cur_r=*rec_rgt[r].rbegin();
if(cur_l>r)modify_lft(L,mid,1,l,cur_l);
if(cur_r<l)modify_rgt(mid+1,R,1,r,cur_r);
}int find_lft(int l,int r,int rt,int nowl,int nowr){
if(cls_lft[rt]>nowr)return -1;
if(nowl<=l){
while(l<r){
int mid=(l+r)>>1;
if(cls_lft[rt<<1]<=nowr)r=mid,rt<<=1;
else l=mid+1,rt=rt<<1|1;
}return l;
}int mid=(l+r)>>1;
if(nowl>mid)return find_lft(mid+1,r,rt<<1|1,nowl,nowr);
int res=find_lft(l,mid,rt<<1,nowl,nowr);
if(res==-1)return find_lft(mid+1,r,rt<<1|1,nowl,nowr);
else return res;
}int find_rgt(int l,int r,int rt,int nowl,int nowr){
if(cls_rgt[rt]<nowl)return -1;
if(r<=nowr){
while(l<r){
int mid=(l+r)>>1;
if(cls_rgt[rt<<1|1]>=nowl)l=mid+1,rt=rt<<1|1;
else r=mid,rt<<=1;
}return l;
}int mid=(l+r)>>1;
if(mid>=nowr)return find_rgt(l,mid,rt<<1,nowl,nowr);
int res=find_rgt(mid+1,r,rt<<1|1,nowl,nowr);
if(res==-1)return find_rgt(l,mid,rt<<1,nowl,nowr);
else return res;
}
// 第二部分的线段树，0/1 后缀表示左侧/右侧
pair<int,int>pos0[maxm<<2],pos1[maxm<<2];int cov0[maxm<<2],cov1[maxm<<2];
inline void update0(int rt){pos0[rt]=min(pos0[rt<<1],pos0[rt<<1|1]);}
inline void cvr0(int rt,int k){chkmax(pos0[rt].first,k),chkmax(cov0[rt],k);}
inline void pushcol0(int rt){
if(cov0[rt]!=-inf)cvr0(rt<<1,cov0[rt]),cvr0(rt<<1|1,cov0[rt]),cov0[rt]=-inf;
}void modify0(int l,int r,int rt,int nowl,int nowr,int k){
if(nowl<=l&&r<=nowr)return cvr0(rt,k);
int mid=(l+r)>>1;pushcol0(rt);
if(nowl<=mid)modify0(l,mid,rt<<1,nowl,nowr,k);
if(mid<nowr)modify0(mid+1,r,rt<<1|1,nowl,nowr,k);
update0(rt);
}inline void cover0(int now,pair<int,int>val){
int l=1,r=Q,rt=1;
while(l<r){int mid=(l+r)>>1;pushcol0(rt);if(now<=mid)r=mid,rt<<=1;else l=mid+1,rt=rt<<1|1;}
pos0[rt]=val;for(rt>>=1;rt;rt>>=1)update0(rt);
}
inline void update1(int rt){pos1[rt]=max(pos1[rt<<1],pos1[rt<<1|1]);}
inline void cvr1(int rt,int k){chkmin(pos1[rt].first,k),chkmin(cov1[rt],k);}
inline void pushcol1(int rt){
if(cov1[rt]!=inf)cvr1(rt<<1,cov1[rt]),cvr1(rt<<1|1,cov1[rt]),cov1[rt]=inf;
}void modify1(int l,int r,int rt,int nowl,int nowr,int k){
if(nowl<=l&&r<=nowr)return cvr1(rt,k);
int mid=(l+r)>>1;pushcol1(rt);
if(nowl<=mid)modify1(l,mid,rt<<1,nowl,nowr,k);
if(mid<nowr)modify1(mid+1,r,rt<<1|1,nowl,nowr,k);
update1(rt);
}inline void cover1(int now,pair<int,int>val){
int l=1,r=Q,rt=1;
while(l<r){int mid=(l+r)>>1;pushcol1(rt);if(now<=mid)r=mid,rt<<=1;else l=mid+1,rt=rt<<1|1;}
pos1[rt]=val;for(rt>>=1;rt;rt>>=1)update1(rt);
}
// 当 l=r 时只需考虑时间维度，用一个树状数组维护更快、更方便
int b[maxm];
inline void add(int i,int x){for(;i<=Q;i+=(i&-i))b[i]+=x;}
inline int cal(int i){int res=0;for(;i;i-=(i&-i))res+=b[i];return res;}
pair<int,int>SEG[maxn<<2];// SEG[rt] 表示编号为 rt 的分治区间为[SEG[rt].first,SEG[rt].second]
bool MemoryED;int main(){
read(n,Q),n--;
for(int i=1,op,l,r,t;i<=Q;i++){
read(op);
if(op==1)read(l,r),opt[opt_id[i]=++ocnt]=opr{l,r-1,i,0};
else if(op==2)read(t),opt[opt_id[t]].tr=i-1;
else read(l,r),insque(que[++qcnt]=qry{l,r-1,i});
}for(int i=1;i<=ocnt;i++){if(opt[i].tr==0)opt[i].tr=Q;insopt(opt[i]);}
for(int i=1;i<=(Q<<2);i++)cov0[i]=-inf,cov1[i]=inf,pos0[i]=make_pair(inf,-1),pos1[i]=make_pair(-inf,-1);
SEG[1]=make_pair(1,n);int len=n<<1;
for(int i=1;i<=n;i++)rec_lft[i].insert(inf),rec_rgt[i].insert(-inf);
for(int i=1;i<=len;i++)cls_lft[i]=inf,cls_rgt[i]=-inf;
// 依旧非递归
for(int m=n<<2,rt=1;rt<=m;rt++)if(SEG[rt].first)[[likely]]{
int l=SEG[rt].first,r=SEG[rt].second;
if(l==r){// 特判叶子节点用更快的树状数组
for(opr cur:seg[rt])add(cur.tl,1),add(cur.tr+1,-1);
for(qry cur:ask[rt])ans[cur.t]=cal(cur.t)>0;
for(opr cur:seg[rt])add(cur.tl,-1),add(cur.tr+1,1);
}else{
int mid=(l+r)>>1;
if(!ask[rt].empty())[[likely]]{// 没有询问就没必要处理
for(qry cur:ask[rt])rng2[cur.t]=make_pair(cur.l,cur.r);
// 第一部分
if(!seg[rt].empty()){
cnt=0;
for(opr cur:seg[rt])
evt[++cnt]=make_pair(cur.tl,make_pair(0,make_pair(cur.l,cur.r))),
evt[++cnt]=make_pair(cur.tr+1,make_pair(-1,make_pair(cur.l,cur.r)));
for(qry cur:ask[rt])
evt[++cnt]=make_pair(cur.t,make_pair(cur.t,make_pair(cur.l,cur.r)));
stable_sort(evt+1,evt+cnt+1);
for(int i=1;i<=cnt;i++){
auto[val,itr]=evt[i].second;
if(val==-1)del(l,r,itr.first,itr.second);
else if(val==0)ins(l,r,itr.first,itr.second);
else{
pair<int,int>cur=make_pair(
find_lft(l,mid,1,itr.first,itr.second),
find_rgt(mid+1,r,1,itr.first,itr.second)
);
rng[val]=make_pair(cur.first==-1?mid+1:cur.first,cur.second==-1?mid:cur.second);
}
}
}else for(qry cur:ask[rt])rng[cur.t]=make_pair(mid+1,mid);
// 第二部分
int ask_len=ask[rt].size();
if(!itv_lft[rt].empty()){
sort(ask[rt].begin(),ask[rt].end(),[&](const qry&x,const qry&y){return x.l<y.l;});
sort(itv_lft[rt].begin(),itv_lft[rt].end(),[&](const opr&x,const opr&y){return x.l<y.l;});
int itv_len=itv_lft[rt].size();
for(int i=0,j=0;i<itv_len;){
int cur_l=itv_lft[rt][i].l;
for(;j<ask_len&&ask[rt][j].l<cur_l;j++);
for(pair<int,int>cur=pos0[1];cur.first<cur_l;cur=pos0[1])
rng2[cur.second].first=cur.first,cover0(cur.second,make_pair(inf,-1));
for(;j<ask_len&&ask[rt][j].l==cur_l;j++)cover0(ask[rt][j].t,make_pair(cur_l,ask[rt][j].t));
for(;i<itv_len&&itv_lft[rt][i].l==cur_l;i++)
modify0(1,Q,1,itv_lft[rt][i].tl,itv_lft[rt][i].tr,itv_lft[rt][i].r+1);
for(pair<int,int>cur=pos0[1];cur.first<=cur_l;cur=pos0[1])
rng2[cur.second].first=cur.first,cover0(cur.second,make_pair(inf,-1));
}
for(pair<int,int>cur=pos0[1];cur.second!=-1;cur=pos0[1])
rng2[cur.second].first=cur.first,cover0(cur.second,make_pair(inf,-1));
}
if(!itv_rgt[rt].empty()){
sort(ask[rt].begin(),ask[rt].end(),[&](const qry&x,const qry&y){return x.r>y.r;});
sort(itv_rgt[rt].begin(),itv_rgt[rt].end(),[&](const opr&x,const opr&y){return x.r>y.r;});
int itv_len=itv_rgt[rt].size();
for(int i=0,j=0;i<itv_len;){
int cur_r=itv_rgt[rt][i].r;
for(;j<ask_len&&ask[rt][j].r>cur_r;j++);
for(pair<int,int>cur=pos1[1];cur.first>cur_r;cur=pos1[1])
rng2[cur.second].second=cur.first,cover1(cur.second,make_pair(-inf,-1));
for(;j<ask_len&&ask[rt][j].r==cur_r;j++)cover1(ask[rt][j].t,make_pair(cur_r,ask[rt][j].t));
for(;i<itv_len&&itv_rgt[rt][i].r==cur_r;i++)
modify1(1,Q,1,itv_rgt[rt][i].tl,itv_rgt[rt][i].tr,itv_rgt[rt][i].l-1);
for(pair<int,int>cur=pos1[1];cur.first>=cur_r;cur=pos1[1])
rng2[cur.second].second=cur.first,cover1(cur.second,make_pair(-inf,-1));
}
for(pair<int,int>cur=pos1[1];cur.second!=-1;cur=pos1[1])
rng2[cur.second].second=cur.first,cover1(cur.second,make_pair(-inf,-1));
}for(qry cur:ask[rt])
ans[cur.t]=rng2[cur.t].first>=rng[cur.t].first&&rng2[cur.t].second<=rng[cur.t].second;
}SEG[rt<<1]=make_pair(l,mid),SEG[rt<<1|1]=make_pair(mid+1,r);
}
}
for(int i=1;i<=qcnt;i++)putchar(str[ans[que[i].t]]),putchar('\n');
return 0;
}
```