文章目录

• 题意
• 思路

传送门

题意

有 n n n个人，给你 q q q个请求，分以下三种：

• [ l , r , x ] [l,r,x] [l,r,x] 如果 x = 0 x=0 x=0，代表 [ l , r ] [l,r] [l,r]这个区间内的人都没病。
• [ l , r , x ] [l,r,x] [l,r,x] 如果 x = 1 x=1 x=1，代表 [ l , r ] [l,r] [l,r]这个区间内的人至少一个有病。
• j j j 查询第 j j j个人是否能确定有病或者没病，如果能确定那么是有病还是没病。

1 ≤ n , q ≤ 2 e 5 1\le n,q\le 2e5 1≤n,q≤2e5

思路

一个人没病很好确定，考虑一个人有病怎么确定呢？

对于 t = 1 t=1 t=1的时候，如果这个区间内的没病的人数等于区间长度减 1 1 1，那么剩下那个人一定有病，否则就不能确定。

让后这个题的一个比较难的点是假设当前是第 i i i个询问，你需要根据前 i i i个询问的信息来回答当前的答案，在线很难，我们不妨离线来搞。

离线来的话，对于每个没病的人都记一下这个位置确定的最小时间，显然势能线段树即可。让后再从头遍历一下 x = 1 x=1 x=1的信息，首先查询一下当前区间没病的人是否等于区间长度减 1 1 1，让后再看一下区间最大值是否小于当前询问时间 i i i，都满足的话找到剩余的这个人的位置，将 a n s [ p o s ] = m i n ( a n s [ p o s ] , m a x ( i , m x ) ) ans[pos]=min(ans[pos],max(i,mx)) ans[pos]=min(ans[pos],max(i,mx))即可。

再处理查询，根据上面的信息分情况即可。

复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。

#include<bits/stdc++.h>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define pb push_back
using namespace std;

const int N=200010,INF=0x3f3f3f3f,mod=1e9+7;
typedef long long LL;

int n,qq;
int ans[N];
struct Query {
    int op,l,r,x;
}q[N];
struct Node {
    int l,r;
    int cnt,mx;
    int id;
}tr[N<<2];

void pushup(int u) {
    tr[u].cnt=tr[L].cnt+tr[R].cnt;
    tr[u].mx=max(tr[L].mx,tr[R].mx);
    if(tr[L].id!=0) tr[u].id=tr[L].id;
    else if(tr[R].id!=0) tr[u].id=tr[R].id;
    else tr[u].id=0;
}

void build(int u,int l,int r) {
    tr[u]={l,r,0,-1,0};
    if(l==r) {
        tr[u].id=l;
        return;
    }
    build(L,l,Mid); build(R,Mid+1,r);
    pushup(u);
}

void change(int u,int l,int r,int x) {
    if(tr[u].cnt==Len(u)) return;
    if(tr[u].l==tr[u].r) {
        tr[u].cnt=1;
        tr[u].mx=x;
        tr[u].id=0;
        return;
    }
    if(l<=Mid) change(L,l,r,x);
    if(r>Mid) change(R,l,r,x);
    pushup(u);
}

int query_cnt(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].cnt;
    int ans=0;
    if(l<=Mid) ans+=query_cnt(L,l,r);
    if(r>Mid) ans+=query_cnt(R,l,r);
    return ans;
}

int query_max(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mx;
    int ans=-1;
    if(l<=Mid) ans=max(ans,query_max(L,l,r));
    if(r>Mid) ans=max(ans,query_max(R,l,r));
    return ans;
}

Node query_id(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    if(r<=Mid) return query_id(L,l,r);
    if(l>Mid) return query_id(R,l,r);
    Node ans,ls,rs;
    ls=query_id(L,l,r);
    rs=query_id(R,l,r);
    ans.cnt=ls.cnt+rs.cnt;
    ans.mx=max(ls.mx,rs.mx);
    if(ls.id!=0) ans.id=ls.id;
    else if(rs.id!=0) ans.id=rs.id;
    else ans.id=0;
    /*
    if(ls.cnt==ls.r-ls.l+1&&rs.cnt==rs.r-rs.l+1) ans.id=0;
    else if(ls.cnt!=ls.r-ls.l+1) ans.id=ls.id;
    else ans.id=rs.id;
    ans.l=ls.l; ans.r=rs.r;
    */
    return ans;
}

void solve() {
    scanf("%d%d",&n,&qq);
    build(1,1,n);
    for(int i=1;i<=n;i++) ans[i]=qq+1;
    for(int i=1;i<=qq;i++) {
        int op; scanf("%d",&op);
        if(op==0) {
            int l,r,x; scanf("%d%d%d",&l,&r,&x);
            q[i]={op,l,r,x};
            if(x==0) change(1,l,r,i);
        } else {
            int x; scanf("%d",&x);
            q[i]={op,-1,-1,x};
        }
    }
    for(int i=1;i<=qq;i++) {
        if(q[i].op==0&&q[i].x==1) {
            int l=q[i].l,r=q[i].r;
            int mx=query_max(1,l,r);
            int cnt=query_cnt(1,l,r);
            if(cnt!=r-l) continue;
            Node res=query_id(1,l,r);
            ans[res.id]=min(ans[res.id],max(mx,i));
            //cout<<"**"<<ans[res.id]<<endl;
        }
    }
    for(int i=1;i<=qq;i++) {
        if(q[i].op==1) {
            int x=q[i].x;
            int cnt=query_cnt(1,x,x);
            int mx=query_max(1,x,x);
            if(cnt&&mx<i) puts("NO");
            else {
                if(ans[x]>i) puts("N/A");
                else puts("YES");
            }
        }
    }
}

int main() {
	int _=1;
	while(_--) {
		solve();
	}

    return 0;
}
/*
0 4 5 0
1 5
1 6
0 4 6 1
1 6
0 2 5 1
0 2 2 0
1 3
1 2

1 2 3 4 5 6
1 0 1 0 0 1
*/