JRKSJ ExR C

· · 题解

下面把 r\to r-1。则问题转化为：选择所有被 [ql,qr] 包含的区间，判断是否能覆盖 [ql,qr] 内的所有整点。

下称一个操作的范围为 [ql,qr,tl,tr]（区间，时间区间），一个询问为 [ql,qr,t]。

先对序列分治，计算所有跨过 mid 的询问。

考虑先算跨过 mid 的区间的贡献。对于询问 [ql,qr,t]，能覆盖到的最小位置 x 就是存在一个操作 [x,r,tl,tr] 使得 x\in [ql,mid],r\le qr,t\in [tl,tr]。对时间维度扫描线，线段树二分即可。

然后考虑所有在两边的区间，能不能把剩下的空隙填上。假设考虑左边，我们对时间轴开一个线段树，扫描序列维度（i=l\to mid）。

每次扫到一个询问就放在线段树上，维护当前这个询问的右端点到了哪里。扫到一个操作就是区间取 max。做完 [i,r] 的所有操作后，不断取线段树上最小值，如果 <i 了就弹掉。

时间复杂度 O(q\log^2 q)。

struct Max{
    int x;
    Max (int xx=-inf){
        x=xx;
    }
};
Max operator +(Max a,Max b){
    return Max(max(a.x,b.x));
}

struct Min{
    int x;
    Min (int xx=inf){
        x=xx;
    }
};
Min operator +(Min a,Min b){
    return Min(min(a.x,b.x));
}

struct opMin{
    int x;
    opMin (int xx=inf){
        x=xx;
    }
};

struct opMax{
    int x;
    opMax (int xx=-inf){
        x=xx;
    }
};

void operator +=(opMax &a,opMax b){
    a.x=max(a.x,b.x);
}
void operator +=(opMin &a,opMin b){
    a.x=min(a.x,b.x);
}

void operator +=(Min &a,opMax b){
    a.x=max(a.x,b.x);
}
void operator +=(Max &a,opMin b){
    a.x=min(a.x,b.x);
}

int n,q,m,m2;
int qwq[maxn];
int ql[maxn],qr[maxn],dl[maxn],tl[maxn],tr[maxn],tim[maxn];

struct node{
    int ql,qr,tl,tr;
};

int fid[maxn];

int c[maxn];
bool ask(int l,int r){
    For(i,l-1,r+1) c[i]=0;
    For(i,1,m) if(!dl[i]) {
        if(ql[i]>=l && qr[i]<=r) ++c[ql[i]],--c[qr[i]+1];
    }
    For(i,l,r) {
        c[i]+=c[i-1];
        if(!c[i]) return 0;
    }
    return 1;
}

bool res[maxn];

int dest(vector<node>&ts,vector<node>&qs){
    vi tmp;
    for(auto [ql,qr,tl,tr]:ts) tmp.pb(tl),tmp.pb(tr);
    for(auto [ql,qr,tl,tr]:qs) tmp.pb(tl);
    sort(ALL(tmp));
    tmp.erase(unique(ALL(tmp)),tmp.end());
    auto V=[&](int x){
        x=lower_bound(ALL(tmp),x)-tmp.begin();
        return x+1;
    };
    for(auto &[ql,qr,tl,tr]:ts) tl=V(tl),tr=V(tr);
    for(auto &[ql,qr,tl,tr]:qs) tl=V(tl);
    return tmp.size();
}

multiset<int>s[maxn];

vi in[maxn],ot[maxn],qq[maxn];

int tol[maxn],tor[maxn];
int qid[maxn];

int t3[maxn],t4[maxn];

void solve(int l,int r,vector<node>ts,vector<node>qs)
{
    if(!SZ(qs)) return;

//  cout<<"solve "<<l<<" "<<r<<endl;

    int m=dest(ts,qs);
    int mid=l+r>>1;

//  cout<<"m: "<<m<<endl;

    segt1<Min>T1;
    segt1<Max>T2;

    vector<node>QL,QR,TL,TR;

    For(i,1,m) s[i].clear(),in[i].clear(),ot[i].clear(),qq[i].clear();

    For(i,0,SZ(ts)-1){
        auto [ql,qr,tl,tr]=ts[i];
        if(ql<=mid && qr>mid) in[tl].pb(i),ot[tr].pb(i);
        else if(qr<=mid) TL.pb(ts[i]);
        else TR.pb(ts[i]);
    }
    bool hav=0;
    For(i,0,SZ(qs)-1){
        auto [ql,qr,tl,tr]=qs[i];
        if(ql<=mid && qr>mid) qq[tl].pb(i),tol[tr]=mid+1,tor[tr]=mid;
        else if(qr<=mid) QL.pb(qs[i]);
        else QR.pb(qs[i]);
    }

    T1.init(mid-l+1);
    T2.init(r-mid);

    auto gval=[&](int x){
        if(x<=mid){
            return s[x].empty()? inf:*s[x].begin();
        }else{
            return s[x].empty()?-inf:*s[x].rbegin();
        }
    };

    auto upd1=[&](int x){
        if(x<=mid){
            T1.upd(x-l+1,{gval(x)});
        }else{
            T2.upd(x-mid,{gval(x)});
        }
    };

    For(i,1,m){
        for(auto id:in[i]){
            auto [ql,qr,tl,tr]=ts[id];
            s[ql].insert(qr);
            s[qr].insert(ql);
            upd1(ql);
            upd1(qr);
        }
        for(auto id:qq[i]){
            auto [ql,qr,tl,ii]=qs[id];
        //  cout<<"ID "<<id<<endl;
            tol[ii]=T1.findL(ql-l+1,mid-l+1,[&](Min t){
                return t.x<=qr;
            });
            tor[ii]=T2.findR(1,qr-mid,[&](Max t){
                return t.x>=ql;
            });
            tol[ii]+=l-1;
            tor[ii]+=mid;
            if(!(tol[ii]>=l && tol[ii]<=mid)) tol[ii]=mid+1;
            if(!(tor[ii]>=mid+1 && tor[ii]<=r)) tor[ii]=mid;
        }
        for(auto id:ot[i]){
            auto [ql,qr,tl,tr]=ts[id];
        //  cout<<"del: "<<ql<<" "<<qr<<endl;
            s[ql].erase(s[ql].find(qr));
            s[qr].erase(s[qr].find(ql));
        //  cout<<"done.\n";
            upd1(ql);
            upd1(qr);
        }
    }

    For(i,0,m) in[i].clear(),ot[i].clear(),qq[i].clear();

//  cout<<"QWQ\n";

    segt<Min,opMax>T3;
    segt<Max,opMin>T4;

    T3.init(m);
    T4.init(m);
    For(i,l,r) in[i].clear(),qq[i].clear();

    For(i,0,SZ(TL)-1){
        auto [ql,qr,tl,tr]=TL[i];
        in[ql].pb(i);
    }
    For(i,0,SZ(qs)-1){
        auto [ql,qr,tl,tr]=qs[i];
        if(ql<=mid && qr>mid) qq[ql].pb(i),qq[qr].pb(i);
    }
    For(i,l,mid){
        for(auto id:qq[i]){
            auto [ql,qr,tl,ii]=qs[id];
            qid[tl]=ii;
            T3.upd(tl,{i-1});
        }
        for(auto id:in[i]){
            auto [ql,qr,tl,tr]=TL[id];
            T3.mdf(tl,tr,{qr});
        }
        while(1){
            int p=T3.findL(1,m,[&](Min t){
                return t.x<i;
            });
            if(!(p>=1&&p<=m)) break;
            int ii=qid[p];
            if(i<tol[ii]) res[ii]=0;
            T3.upd(p,{inf});
        }
    }
    For(i,l,mid) in[i].clear(),qq[i].clear();

    For(i,0,SZ(TR)-1){
        auto [ql,qr,tl,tr]=TR[i];
        in[qr].pb(i);
    }
    Rep(i,r,mid+1){
        for(auto id:qq[i]){
            auto [ql,qr,tl,ii]=qs[id];
            qid[tl]=ii;
            T4.upd(tl,{i+1});
        }
        for(auto id:in[i]){
            auto [ql,qr,tl,tr]=TR[id];
            T4.mdf(tl,tr,{ql});
        }
        while(1){
            int p=T4.findR(1,m,[&](Max t){
                return t.x>i;
            });
            if(!(p>=1&&p<=m)) break;
            int ii=qid[p];
            if(tor[ii]<i) res[ii]=0;
            T4.upd(p,{-inf});
        }
    }

    For(i,mid+1,r) in[i].clear(),qq[i].clear();

    solve(l,mid,TL,QL);
    solve(mid+1,r,TR,QR);
}

void work()
{
    n=read(),q=read();

    vector<node> Qs,Ts;
    For(i,1,q){
        int op=read();
        if(op==1){
            ++m,ql[m]=read(),qr[m]=read()-1;
            dl[m]=0;
            fid[i]=m;
            tl[m]=m2+1;
            if(ql[m]==qr[m]) ++qwq[ql[m]];
            tr[m]=-1;
        }
        if(op==2){
            int x=read();
            x=fid[x];   
            assert(!dl[x]);
            if(ql[x]==qr[x]) --qwq[ql[x]];
            dl[x]=1;
            tr[x]=m2;
        }
        if(op==3){
            int l=read(),r=read()-1;
            ++m2;
            if(l==r) res[m2]=(qwq[l]);
            else Qs.pb({l,r,m2,m2}),res[m2]=1;
            tim[m2]=i;
        }
    }

    For(i,1,m){
        if(tr[i]==-1)tr[i]=m2;
        if(tl[i]<=tr[i]) Ts.pb({ql[i],qr[i],tl[i],tr[i]});
    }

    solve(1,n-1,Ts,Qs);
    For(i,1,m2) {
        if(res[i])puts("Y");
        else puts("N");
    }
}

signed main()
{
//  freopen("my.out","w",stdout);
    int T=1;
    while(T--)work();
    return 0;
}