CF1641C

CF的题就是牛逼。

solution

题目传送门

题目大意：

病人数：n，操作数：m
对于一排病人， 医生可以做三种操作：

    1.l, r, 0 表示第 l 到 r 个人中没有病人
    2.l, r, 1 表示第 l 到 r 个人中至少有一个病人生病
    3.询问第 j 个病人有没有生病

对于每一个操作 3 ， 可以确定生病输出 YES , 可以确定不生病输出 NO , 否则输出 N/A
每一次首先输入一个数t，t=0则为第1、2种操作，t=1则为第3种操作

首先将序列：1-n定义为unknow，可以发现一个人x可以被确定为病人当且仅当有一个操作2的区间中除了x以外的所有数都不是病人（废话），那么我们用一个set维护那些人可能是病人，于是我们可以快速查找到x 前第一个unknow：st和下一个unknow：ed，可以发现操作2中如果有区间满足：
$$
st < l \le x ,x\le r < ed
$$
那么x就是病人，此时问题已经转化到序列上，我们造一颗线段树维护以x为起点的操作2的最小r，那么我们就可以直接查询$[st+1,x]$这段区间，判断之中的最小值是否小于ed就可以了。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, T;
set<int>s;
namespace Seg{
    #define l(x) (x << 1)
    #define r(x) (x << 1 | 1)
    struct Node{
        int l, r, v;
    }tr[N << 2];
    inline void pushup(int x)
    {
        tr[x].v = min(tr[l(x)].v, tr[r(x)].v);
    }
    inline void change(int x, int w)
    {
        tr[x].v = min(tr[x].v, w);
    }
    void build(int x, int l, int r)
    {
        tr[x] = {l, r, n + 1};
        if(l == r) return ;
        int mid = l + r >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        pushup(x);
    }
    void modify(int x, int l, int r, int w)
    {
        if(tr[x].l == tr[x].r) return change(x, w);
        int mid = tr[x].l + tr[x].r >> 1;
        if(l <= mid) modify(x << 1, l, r, w);
        else modify(x << 1 | 1, l, r, w);
        pushup(x);
    }
    int query(int x, int l, int r)
    {
        if(l <= tr[x].l && tr[x].r <= r) return tr[x].v;
        int mid = tr[x].l + tr[x].r >> 1, res = n + 1;
        if(l <= mid) res = min(res, query(x << 1, l, r));
        if(r > mid) res = min(res, query(x << 1 | 1, l, r));
        return res;
    }
}
int main()
{
	scanf("%d%d", &n, &m);
    Seg:: build(1, 1, n);
    for(int i = 0;i <= n + 1;i ++) s.insert(i);
    int op, l, r, x;
    while(m --)
    {
        scanf("%d", &op);
        if(op == 0)
        {
            scanf("%d%d%d", &l, &r, &x);
            if(x == 0)
            {
                while(!s.empty())
                {
                    x = *s.lower_bound(l);
                    if(x > r) break;
                    s.erase(x);
                }
                continue;
            }
            else Seg:: modify(1, l, r, r);
        }
        else{
            scanf("%d", &x);
            if(!s.count(x)) puts("NO");
            else{
                auto st = s.lower_bound(x), ed = s.upper_bound(x);
                st --;
                if(Seg:: query(1, (*st) + 1, x) < *ed) puts("YES");
                else puts("N/A");
            }
        }
    }
	return 0;
}