题解：P11695 [JRKSJ ExR] 昼寝

Eterna · 2025-10-16 14:26:16 · 题解

题目中所有区间都是左闭右开的，令 r\gets r-1 变为闭区间。

而每个区间 [l_i,r_i] 在数轴上存在的时间都是一个区间 [b_i,e_i]。

贪心的想，如果我们将时刻 t_i 的询问 [L_i,R_i] 中所有满足 b_j \le t_i \le e_j,L_i \le l_j \le r_j \le R_i 的区间全部选上一定最优。

对数轴分治，设当前分治区间为 [L,R]，中点为 \displaystyle \mathrm{mid} = \lfloor \frac{L+R}{2}\rfloor。处理所有 L \le L_i \le \mathrm{mid} < R_i \le R 的询问。

此时考虑跨过或不跨过中点区间的贡献。

1. 跨过中点，以下区间 [l_j,r_j] 也仅指跨过中点的区间。

   先选上跨过中点的所有区间 L_i \le l_j \le r_j \le R_i，则其中所有区间的并也是一个过中点的区间 [f_i,d_i]。考虑分别快速求出 f_i,d_i。

   以 f_i 为例。对于若干区间，如果他们有相同的 l_i，他们的贡献相同，则对于 r_i，我们只需要找到最小的 r_i。即对于每个位置 k 求出 g_k=\min _{l_j=k}\limits r_j。可以知道 f_i=\min \{k\mid g_k \le r\}。

   在时间维上扫描线，利用动态维护 g 是容易的，查询 f 直接线段树二分。

   而 d_i 与 f_i 做法基本相同，不再重复。

2. 不跨过中点，以下区间 [l_j,r_j] 也仅指不跨过中点的区间。

   依旧以左半区间为例，因为跨过中点的区间已经覆盖了 [f_i,\mathrm{mid}]，所以我们只需判断不跨过中点的区间是否可以覆盖 [L_i,f_i)。

   设 h_i 为询问中最小的未被覆盖的点。左半边有解当且仅当 h_i \ge f_i。

   在序列维上扫描线，从 L 到 \mathrm{mid}。在时间维上维护一个 \{H_i\} 记录答案。

   当我们扫到一个询问的 L_i 时，我们激活其对应的 H_t，这样可以排除掉所有 l_j<L_i 的区间。

   扫到一个 l_j 时，那么在时刻 [b_j,e_j] 中的询问有 h_i > r_j。对 H 区间和 (r_j+1) 做 \mathrm{chkmax} 即可。

   最后取出 H_j=i 的位置，因为后面的区间全都 l_j > H_i，不管怎么取都会空出 H_i。

   而右半区间与左半区间做法基本相同，不再重复。

对于 l_i=r_i,L_i=R_i 的区间与询问单独拿出来做，考虑一下时间即可。

时间复杂度为 \mathcal{O}(m \log^2 n+n \log n)。

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=1000005,M=500005,inf=1e8;
int n,m,cnt,qct,h[M],H[M],f[M],F[M],pos[N],S[N],TG[M];
bool ans[M];
struct node{int l,r,b,e;}t[M];
struct quer
{
    int l,r,tim;
    inline bool operator <(const quer &o)const{return tim<o.tim;}
}q[M],Gmid[M<<1];
vector<int> P[N];vector<quer> PT[N];
multiset<int> s[N];
inline void cmax(int &x,int y){x=x<y?y:x;}
inline void cmin(int &x,int y){x=x>y?y:x;}
struct seg1
{
    int mx[N<<2];
    inline void mod(int id,int v)
    {
        id=pos[id],mx[id]=v;
        for(id>>=1;id;id>>=1)mx[id]=max(mx[id<<1],mx[id<<1|1]);
    }
    inline int askr(int id,int l,int r,int x,int y)
    {
        if(mx[id]<y||l>x)return 0;if(l==r)return l;int mid=l+r>>1,X=0;
        if(mx[id<<1|1]>=y)X=askr(id<<1|1,mid+1,r,x,y);
        if(!X&&mx[id<<1]>=y)X=askr(id<<1,l,mid,x,y);
        return X;
    }
}Gr;
struct seg2
{
    int mn[N<<2];
    inline void mod(int id,int v)
    {
        id=pos[id],mn[id]=v;
        for(id>>=1;id;id>>=1)mn[id]=min(mn[id<<1],mn[id<<1|1]);
    }
    inline int askl(int id,int l,int r,int x,int y)
    {
        if(mn[id]>y||r<x)return 0;if(l==r)return l;int mid=l+r>>1,X=0;
        if(mn[id<<1]<=y)X=askl(id<<1,l,mid,x,y);
        if(!X&&mn[id<<1|1]<=y)X=askl(id<<1|1,mid+1,r,x,y);
        return X;
    }
}Gl;
struct SEG1
{
    int mn[M<<2],T[M<<2];
    inline void psh(int id,int v){cmax(mn[id],v),cmax(T[id],v);}
    inline void phd(int id){if(T[id])psh(id<<1,T[id]),psh(id<<1|1,T[id]),T[id]=0;}
    inline void Cmax(int id,int l,int r,int x,int y,int v)
    {
        if(x>y)return;
        if(x<=l&&y>=r)return psh(id,v);
        int mid=l+r>>1;phd(id);
        if(x<=mid)Cmax(id<<1,l,mid,x,y,v);
        if(y>mid)Cmax(id<<1|1,mid+1,r,x,y,v);
        mn[id]=min(mn[id<<1],mn[id<<1|1]);
    }
    inline void mod(int id,int l,int r,int x,int v)
    {
        if(l==r)return mn[id]=v,void();
        int mid=l+r>>1;phd(id);
        if(x<=mid)mod(id<<1,l,mid,x,v);
        else mod(id<<1|1,mid+1,r,x,v);
        mn[id]=min(mn[id<<1],mn[id<<1|1]);
    }
    inline int fd(int id,int l,int r)
    {
        if(l==r)return l;int mid=l+r>>1;phd(id);
        return mn[id<<1]<mn[id<<1|1]?fd(id<<1,l,mid):fd(id<<1|1,mid+1,r);
    }
    inline void clear(int id,int l,int r)
    {
        mn[id]=inf,T[id]=0;if(l==r)return;int mid=l+r>>1;
        clear(id<<1,l,mid),clear(id<<1|1,mid+1,r);
    }
}TL;
struct SEG2
{
    int mx[M<<2],T[M<<2];
    inline void psh(int id,int v){cmin(mx[id],v),cmin(T[id],v);}
    inline void phd(int id){if(T[id]!=inf)psh(id<<1,T[id]),psh(id<<1|1,T[id]),T[id]=inf;}
    inline void Cmin(int id,int l,int r,int x,int y,int v)
    {
        if(x>y)return;
        if(x<=l&&y>=r)return psh(id,v);
        int mid=l+r>>1;phd(id);
        if(x<=mid)Cmin(id<<1,l,mid,x,y,v);
        if(y>mid)Cmin(id<<1|1,mid+1,r,x,y,v);
        mx[id]=max(mx[id<<1],mx[id<<1|1]);
    }
    inline void mod(int id,int l,int r,int x,int v)
    {
        if(l==r)return mx[id]=v,void();
        int mid=l+r>>1;phd(id);
        if(x<=mid)mod(id<<1,l,mid,x,v);
        else mod(id<<1|1,mid+1,r,x,v);
        mx[id]=max(mx[id<<1],mx[id<<1|1]);
    }
    inline int fd(int id,int l,int r)
    {
        if(l==r)return l;int mid=l+r>>1;phd(id);
        return mx[id<<1]>mx[id<<1|1]?fd(id<<1,l,mid):fd(id<<1|1,mid+1,r);
    }
    inline void clear(int id,int l,int r)
    {
        mx[id]=0,T[id]=inf;if(l==r)return;int mid=l+r>>1;
        clear(id<<1,l,mid),clear(id<<1|1,mid+1,r);
    }
}TR;
struct BIT
{
    int c[M];
    inline void add(int x,int y){for(;x<=m;x+=x&-x)c[x]+=y;}
    inline int ask(int x){int s=0;for(;x;x-=x&-x)s+=c[x];return s;}
}ck;
inline void gt(int id,int l,int r)
{
    if(l==r)return pos[l]=id,void();
    int mid=l+r>>1;gt(id<<1,l,mid),gt(id<<1|1,mid+1,r);
}
inline void clr(int x){s[x].clear(),Gl.mod(x,inf),Gr.mod(x,-inf);}
inline void del(int x,int y)
{
    int mn=*s[x].begin();s[x].erase(s[x].find(y));
    if(mn!=(s[x].size()?*s[x].begin():inf))Gl.mod(x,(s[x].size()?*s[x].begin():inf));
}
inline void Del(int x,int y)
{
    int mx=*s[x].rbegin();s[x].erase(s[x].find(y));
    if(mx!=(s[x].size()?*s[x].rbegin():-inf))Gr.mod(x,(s[x].size()?*s[x].rbegin():-inf));
}
inline void add(int x,int y)
{
    int mn=(s[x].size()?*s[x].begin():inf);s[x].insert(y);
    if(mn!=*s[x].begin())Gl.mod(x,*s[x].begin());
}
inline void Add(int x,int y)
{
    int mx=(s[x].size()?*s[x].rbegin():-inf);s[x].insert(y);
    if(mx!=*s[x].rbegin())Gr.mod(x,*s[x].rbegin());
}
inline void sol(int l,int r,vector<node> T,vector<quer> Q)
{
    if(!Q.size()||!T.size())return;
    if(l==r)
    {
        for(auto [l,r,b,e]:T)ck.add(b,1),ck.add(e+1,-1);
        for(auto [l,r,tim]:Q)if(ck.ask(tim))ans[tim]=1;
        for(auto [l,r,b,e]:T)ck.add(b,-1),ck.add(e+1,1);
        return;
    }

    int mid=l+r>>1;
    vector<node> Tl,Tr,Tmid;
    vector<quer> Ql,Qr,Qmid;
    for(int i=l;i<=r;++i)clr(i);
    for(node e:T)
        if(e.l<=mid&&e.r>mid)Tmid.push_back(e);
        else if(e.r<=mid)Tl.push_back(e);
        else Tr.push_back(e);
    for(quer e:Q)
        if(e.l<=mid&&e.r>mid)Qmid.push_back(e);
        else if(e.r<=mid)Ql.push_back(e);
        else Qr.push_back(e);
    int CNT=0;
    for(auto [l,r,b,e]:T)
        if(l<=mid&&r>mid)Gmid[++CNT]={l,r,b},Gmid[++CNT]={-l,r,e+1};
    stable_sort(Gmid+1,Gmid+CNT+1);
    int lst=1;
    for(auto [ql,qr,tim]:Qmid)
    {   
        while(lst<=CNT)
        {
            auto [L,R,tmm]=Gmid[lst];
            if(tmm>tim)break;++lst;
            if(L<0)del(-L,R),Del(R,-L);
            else add(L,R),Add(R,L); 
        }
        f[tim]=Gl.askl(1,1,n,ql,qr);
        F[tim]=Gr.askr(1,1,n,qr,ql);
        if(!f[tim]||f[tim]>mid)f[tim]=mid+1;
        if(!F[tim]||F[tim]<=mid)F[tim]=mid;
    }
    int D=0;for(auto [l,r,tim]:Q)S[++D]=tim;
    for(auto [l,r,tim]:Qmid)P[l].push_back(tim),P[r].push_back(tim),
        h[tim]=mid+1,H[tim]=mid;
    stable_sort(S+1,S+D+1),D=unique(S+1,S+D+1)-S-1;
    TL.clear(1,1,D),TR.clear(1,1,D);
    for(auto [L,R,b,e]:Tl)PT[L].push_back({R,b,e});
    for(auto [L,R,b,e]:Tr)PT[R].push_back({L,b,e});
    for(int i=l,B,E,POS;i<=mid;PT[i].clear(),P[i].clear(),++i)
    {
        for(int ID:P[i])
            TL.mod(1,1,D,lower_bound(S+1,S+D+1,ID)-S,i);
        for(auto [R,b,e]:PT[i])
            B=lower_bound(S+1,S+D+1,b)-S,
            E=upper_bound(S+1,S+D+1,e)-S-1,
            TL.Cmax(1,1,D,B,E,R+1);
        while(TL.mn[1]==i)
            POS=TL.fd(1,1,D),h[S[POS]]=i,TL.mod(1,1,D,POS,inf);
    }
    for(int i=r,B,E,POS;i>mid;PT[i].clear(),P[i].clear(),--i)
    {
        for(int ID:P[i])
            TR.mod(1,1,D,lower_bound(S+1,S+D+1,ID)-S,i);
        for(auto [L,b,e]:PT[i])
            B=lower_bound(S+1,S+D+1,b)-S,
            E=upper_bound(S+1,S+D+1,e)-S-1,
            TR.Cmin(1,1,D,B,E,L-1);
        while(TR.mx[1]==i)
            POS=TR.fd(1,1,D),H[S[POS]]=i,TR.mod(1,1,D,POS,0);
    }
    for(auto [l,r,tim]:Qmid)
        ans[tim]=(h[tim]>=f[tim]&&H[tim]<=F[tim]);
    sol(l,mid,Tl,Ql),sol(mid+1,r,Tr,Qr);
}
signed main()
{
    n=rd,m=rd,gt(1,1,n);
    for(int i=1,op,l,r;i<=m;++i)
    {
        op=rd;
        if(op==1)l=rd,r=rd-1,t[++cnt]={l,r,i,m},TG[i]=cnt;
        if(op==2)l=TG[rd],t[l].e=i-1;
        if(op==3)l=rd,r=rd-1,q[++qct]={l,r,i};
    }
    vector<node> T;vector<quer> Q;
    for(int i=1;i<=cnt;++i)T.push_back(t[i]);
    for(int i=1;i<=qct;++i)Q.push_back(q[i]);
    sol(1,n,T,Q);
    for(int i=1;i<=qct;++i)cout<<(ans[q[i].tim]?"Y\n":"N\n");
    return 0;
}