Codeforces 1641C

题意

一段区间，几个操作：

• 一段区间内全为0
• 一段区间内存在1
• 查询一个点的值是否能被确定，能则输出该值

Solution

• 树状数组
• 并查集（V）

Code

//
// Created by sfc9982 on 2022/03/15.
//

#include <iostream>
#include <cstring>
#include <string>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

int f[200050], maxv[200050];

inline int fa(int x)
{
    return f[x] == x ? x : f[x] = fa(f[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
    {
        f[i] = i;
        maxv[i] = -1;
    }
    for (int i = 1; i <= m; i++)
    {
        int op;
        cin >> op;
        switch (op)
        {
            case 0:
            {
                int l, r, v;
                cin >> l >> r >> v;
                if (!v)
                {
                    l = fa(l - 1);
                    for (int j = fa(r); j != l; j = fa(j - 1))
                    {
                        maxv[l] = max(maxv[l], maxv[j]);
                        f[j] = l;
                    }
                }
                else
                {
                    r = fa(r);
                    maxv[r] = max(maxv[r], l - 1);
                }
                break;
            }
            case 1:
            {
                int x;
                cin >> x;
                cout << (f[x] == x ? maxv[x] != -1 && fa(maxv[x]) == fa(x - 1) ? "YES\n" : "N/A\n" : "NO\n");
                break;
            }
            default:;
        }

    }
    return 0;
}