题解：P11536 [NOISG2023 Finals] Curtains

Purslane · 2025-01-12 12:19:06 · 题解

Solution

给个 O((n+q) \log^2 n) 的做法，不需要任何思考，而且运行时间只是单 \log 的两倍。

考虑扫描线，对于 l=n,n-1,\cdots,1，维护每个 r \ge l，用 [l,r] 内包含的连续段能覆盖的最长的连续后缀长度，设为 a_r。我们只需要询问 a_r=l 是否成立。

现在考虑一个 [l,x] 的新线段。对于 r \ge x 且 a_r \le x+1，都可以有 a_r \leftarrow l。

发现这个形式和区间取 \min 非常像，所以可以直接上线段树势能，复杂度 O(n \log^2 n)。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int MAXN=5e5+10;
int n,m,q,ans[MAXN],tag[MAXN<<2];
vector<int> seg[MAXN];
vector<pair<int,int>> qr[MAXN];
struct INFO {int mn,smn;}t[MAXN<<2];
inline int calc(const int a,const int b,const int c,const int d) {if(a==b) return min(c,d);if(a<b) return min(b,c);return min(a,d); }
INFO operator +(INFO A,INFO B) {return {min(A.mn,B.mn),calc(A.mn,B.mn,A.smn,B.smn)};}
void assign(int k,int tg) {
    tag[k]=tg,t[k].mn=tg;
    return ;
}
void push_down(int k,int l,int r) {
    if(tag[k]!=-1) {
        int flg1=0,flg2=0;
        if(t[lson].mn<=t[rson].mn) flg1=1;
        if(t[rson].mn<=t[lson].mn) flg2=1;
        if(flg1) assign(lson,tag[k]);
        if(flg2) assign(rson,tag[k]);
    }
    return tag[k]=-1,void();
}
void update(int k,int l,int r,int x,int y,int v,int nv) {
    if(t[k].mn>v) return ;
    if(x<=l&&r<=y) {
        if(t[k].smn>v) return assign(k,nv),void();
        push_down(k,l,r);
        update(lson,l,mid,x,y,v,nv);
        update(rson,mid+1,r,x,y,v,nv);
        return t[k]=t[lson]+t[rson],void(); 
    }
    push_down(k,l,r);
    if(x<=mid) update(lson,l,mid,x,y,v,nv);
    if(y>mid) update(rson,mid+1,r,x,y,v,nv);
    return t[k]=t[lson]+t[rson],void();
}
void build(int k,int l,int r) {
    tag[k]=-1;
    if(l==r) return t[k]={l+1,n+100},void();
    build(lson,l,mid),build(rson,mid+1,r);
    return t[k]=t[lson]+t[rson],void(); 
}
int query(int k,int l,int r,int pos) {
    if(l==r) return t[k].mn;
    push_down(k,l,r);
    if(pos<=mid) return query(lson,l,mid,pos);
    return query(rson,mid+1,r,pos); 
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    ffor(i,1,m) {
        int l,r;
        cin>>l>>r,seg[l].push_back(r);  
    }
    ffor(i,1,q) {
        int s,e;
        cin>>s>>e,qr[s].push_back({e,i});   
    }
    build(1,1,n);
    roff(i,n,1) {
        for(auto id:seg[i]) update(1,1,n,id,n,id+1,i);
        for(auto pr:qr[i]) if(query(1,1,n,pr.first)==i) ans[pr.second]=1;
    }
    ffor(i,1,q) if(ans[i]) cout<<"YES\n";
    else cout<<"NO\n";
    return 0;
}