种南瓜这题怎么写？

Question

小 P 要在一段长度为 n 的土地上种魔法南瓜，但是魔法南瓜十分珍贵并且种植它还需要特殊的地质。

所以他对土地进行了 q 次勘测，第 i 次勘测是如下两种结果之一：

1 l r : 表示他发现 [l,r] 的土地含有一种全新的元素。

2 x : 他发现之前的第 x 次勘测是错误的，所以会删除第 x 次的勘测结果（保证第 x 次操作是之前未被删除的第一种勘测结果）。

魔法南瓜对于地质的要求十分严苛，必须满足对于任意两个区间，它们的关系只能为包含、被包含或不相交。否则，就会因为元素混乱而无法种植魔法南瓜。

请在每次勘测后给出这片土地是否能种植魔法南瓜。

以上的 [l,r] 指的是 l 地块到 r 地块的所有地块。

形式化题意：
给你一个标号为 1…n 的数轴，有 q 次操作：
1 l r : 表示在数轴
l 放置左括号，r 放置右括号。

2 x : 表示删除第 x 次操作放置的括号。

每次操作后，问能否从数轴 1到 n 的位置依次取出括号（同一位置的括号应先取出左括号再取出右括号，同种括号可以任意顺序取出）形成一个序列。要求这是一个括号序列，并且该括号序列中任意一对匹配的括号对应该是在同一次操作中放置的。

输入格式
第一行输入两个整数 n,q
接下来 q 行表示有 q 次操作，操作的类型有 2 种，每种操作的输入格式如下：

1 l r : 表示他发现 [l,r] 的土地含有一种全新的元素。

2 x : 他发现之前的第 x 次勘测是错误的，所以会删除第 x 次的勘测结果（保证第 x 次操作是第一种勘测结果）。

输出格式
对于每次询问，如果可以种植魔法南瓜则输出一行 YES ，否则输出一行 NO 。

输出的结果大小写不敏感，例如，yEs、Yes、yes、YES 都视作肯定的回答。

输入输出样例
输入 #1复制
5 3
1 2 4
1 3 5
2 1
输出 #1复制
Yes
No
Yes

给出C++代码

Answer 1

方法思路

1. 数据结构选择：使用一个有序集合（set）来维护当前活跃的区间，按左端点排序。这样可以高效地查找前驱和后继区间。
2. 插入操作：在插入新区间时，检查其前驱和后继区间是否存在部分重叠的情况。如果存在部分重叠，则插入后的结构无效，否则有效。
3. 删除操作：直接从集合中删除对应的区间，并重新检查整个结构的有效性。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

struct Interval {
    int l, r;
    Interval(int l = 0, int r = 0) : l(l), r(r) {}
    bool operator<(const Interval& other) const {
        if (l != other.l) return l < other.l;
        return r < other.r;
    }
};

vector<Interval> ops;
set<Interval> active;
vector<bool> deleted;

bool checkConflict(const Interval& newInt) {
    auto it = active.lower_bound(newInt);
    
    // 检查前驱
    if (it != active.begin()) {
        auto prevIt = prev(it);
        const Interval& prev = *prevIt;
        if (prev.r >= newInt.l) {
            if (prev.r < newInt.r) {
                return true;
            }
        }
    }
    
    // 检查后继
    if (it != active.end()) {
        const Interval& succ = *it;
        if (succ.l <= newInt.r) {
            if (succ.r > newInt.r) {
                return true;
            }
        }
    }
    
    return false;
}

bool checkAll() {
    if (active.empty()) return true;
    auto it = active.begin();
    int prevR = it->r;
    ++it;
    for (; it != active.end(); ++it) {
        if (it->l > prevR) {
            prevR = it->r;
        } else if (it->r <= prevR) {
            prevR = it->r;
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    deleted.resize(q, false);
    
    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            Interval current(l, r);
            ops.push_back(current);
            
            bool conflict = checkConflict(current);
            if (conflict) {
                deleted[i] = true;
                cout << "NO\n";
            } else {
                active.insert(current);
                if (checkAll()) {
                    cout << "YES\n";
                } else {
                    active.erase(current);
                    deleted[i] = true;
                    cout << "NO\n";
                }
            }
        } else {
            int x;
            cin >> x;
            x--;
            if (deleted[x]) {
                cout << (checkAll() ? "YES" : "NO") << "\n";
                continue;
            }
            const Interval& toRemove = ops[x];
            active.erase(toRemove);
            deleted[x] = true;
            cout << (checkAll() ? "YES" : "NO") << "\n";
        }
    }
    
    return 0;
}