202112-4 磁盘文件操作

25% 数据——直接模拟

我们按照题目要求进行对应操作即可，注意每一个要求执行的条件：

• 写入操作：从左往右依次执行，直到第一个不被自己占用的位置。除了第一个点就被其他程序占用以外，必然会写入。遇到自己占用，则覆盖。
• 删除操作：同时整体进行，要求所有位置都被目前程序占用。要么全删，要么不做任何更改。
• 恢复操作：同时整体进行，要求所有位置都不被占用，且上次占用程序为目前程序。要么全恢复，要么不做任何更改。遇到自己占用，则不做任何更改。
• 读入操作：读取占用程序和数值，若未被占用，则输出 0 0。

100% 数据——离散化+线段树

通过这道题的操作要求等，我们可以大致推测出这道题可能需要使用线段树。

提示

如果没什么思路，可以拿各种数据结构往上套。 例如本题，因为涉及区间修改、单点查询，对于树状数组来说负担太重，我们可以尝试其他数据结构。 如果使用平衡树，则一般是要求出第 k 大数，或者是序列翻转类问题，对于本题来说不太契合。 其他数据结构不再一一列举。综合考虑下，线段树是比较符合要求的。

考虑线段树的做法

先不考虑线段树的内存空间问题，我们分析一下如何用线段树解决这道题目。

考虑我们需要维护的量，目前已知的有磁盘位置的值、目前占用程序 id、上次占用程序 id。

在这里，我们假设一个位置未被占用和被 id 为 0 的程序占用是等价的。

• 写入操作：可以划分为找到写入右边界和直接写入两个操作。

  直接写入操作就是直接的线段树区间修改， 而划分操作需要知道该区间被占用的位置是否属于将要写入的 id。 我们不妨将这个量设为 id1。

• 删除操作：可以划分为判断是否可删和直接删除两个操作。

  直接删除操作就是直接的线段树区间修改， 而判断是否可删需要知道该区间所有的位置是否属于将要写入的 id。 我们不妨将这个量设为 id2，注意 id1 与 id2 的区别——是否允许包含未被占用的程序。

• 恢复操作：可以划分为判断是否可恢复和直接恢复两个操作。

  该操作与删除操作类似，不过需要注意的是判断时需要判断目前占用的 id 和上次被占用的 id。

• 读取操作：可以划分为查询占用程序 id和查询值两个操作。

  该操作是相对比较质朴的单点查询，当然也可以处理为区间。

通过以上分析，我们得到了需要维护的量：值、有关目前占用程序 id 的两个量、上次被占用的程序 id。我们考虑每个量针对父子之间的维护。

• 值 val：每个节点代表取值的多少，若左右子节点不同则设为一个不存在的值。因为我们是单点查询，所以不用担心查询到不存在的值的问题。
• 被占用位置程序 id1：
  • 若左右子节点都未被占用，则该节点标记为未占用；
  • 若左右子节点中存在不唯一节点，则该节点标记为不唯一。
  • 若左右子节点中一个节点未占用，则该节点标记为另一个非空节点的标记；
  • 若左右子节点都非空且相等，则该节点标记为任意一个节点；
  • 若左右子节点都非空且不等，则该节点标记为不唯一；
• 被占用位置程序 id2：为了方便进行讨论，将未被程序占用节点视为被 id 为 0 的程序占用。
  • 若左右子节点中存在不唯一节点，则该节点标记为不唯一。
  • 若左右子节点相等，则该节点标记为任意一个节点；
  • 若左右子节点不等，则该节点标记为不唯一；
• 上一次被占用程序 lid：与 id2 相同。
  • 若左右子节点中存在不唯一节点，则该节点标记为不唯一。
  • 若左右子节点相等，则该节点标记为任意一个节点；
  • 若左右子节点不等，则该节点标记为不唯一；

解决空间问题

理解线段树的解法之后，就会出现另一个问题：空间达到了 1e9 级别，肯定会 MLE。

我们可以从另一个角度考虑：一共有 \(2\times 10^5\) 次询问，每次最多操作涉及一个区间，可以用两个端点表示。 考虑到临界处的影响，一次操作最多会涉及 4 个点 （比如原来的区间是 \([1, 10]\)，我们更改了区间 \([3,5]\)，那么得到的区间为 \([1,2],[3,5],[6,10]\)，多出了 \(2,3,5,6\) 四个点）。 那么总体来看，涉及到的点最多有 \(2\times 10^5\times 4 = 8\times 10^5\) 个。

我们可以维持这些点的相对大小关系，而将其投影到一个值域较小的区域，就可以减少空间占用了。这种方法称为离散化。

离散化

把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。 离散化本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。

离散化的一般性步骤：

• 统计所有出现过的数字，在知道确切上界的时候可以用数组，不清楚情况下可以用 vector；
• 对所有的数据排序 (sort)、去重 (unique)；
• 对于每个数，其离散化后的对应值即为其在排序去重后数组中的位置，可以通过二分 (lower_bound) 确定。

这道题允许我们提前将所有可能出现的数记录下来（当然不是所有的题目都允许这样），所以这道题就解决了。 线段树节点的个数与询问个数成比例，时间复杂度 \(\mathrm{O}(k\log k)\)。

代码实现

C++

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 200010;
const int INF = 1e9 + 10;
int n, m, k;
#define ls o << 1
#define rs ls | 1
struct treenode {
    // 当前节点的值，若不唯一则为 INF；lazy 为 INF 表示无延迟更新
    int val, lazy_val;
    // 当前占用 id，若存在除 0 以外两种 id 则为 -1；lazy 为 -1 表示无延迟更新
    int id1, lazy_id1;
    // 当前占用 id，若存在两种 id 则为 -1；lazy 为 -1 表示无延迟更新
    int id2, lazy_id2;
    // 上次占用 id，若存在两种 id 则为 -1；lazy 为 -1表示无延迟更新
    int lid, lazy_lid;
} tree[maxn << 5];

void pushup(int o) {
    // 线段树上传操作，合并左右子树结果
    // val 的合并
    tree[o].val = (tree[ls].val == tree[rs].val) ? tree[ls].val : INF;
    // id1 的合并
    if (tree[ls].id1 == -1 || tree[rs].id1 == -1) {
        tree[o].id1 = -1;
    } else if (tree[ls].id1 == tree[rs].id1) {
        tree[o].id1 = tree[ls].id1;
    } else if (tree[ls].id1 == 0) {
        tree[o].id1 = tree[rs].id1;
    } else if (tree[rs].id1 == 0) {
        tree[o].id1 = tree[ls].id1;
    } else {
        tree[o].id1 = -1;
    }
    // id2 的合并
    if (tree[ls].id2 == -1 || tree[rs].id2 == -1) {
        tree[o].id2 = -1;
    } else if (tree[ls].id2 == tree[rs].id2) {
        tree[o].id2 = tree[ls].id2;
    } else {
        tree[o].id2 = -1;
    }
    // lid 的合并
    if (tree[ls].lid == -1 || tree[rs].lid == -1) {
        tree[o].lid = -1;
    } else if (tree[ls].lid == tree[rs].lid) {
        tree[o].lid = tree[ls].lid;
    } else {
        tree[o].lid = -1;
    }
}

void pushdown(int o) {
    // 线段树标记下传操作
    if (tree[o].lazy_val != INF) {
        tree[ls].val = tree[rs].val = tree[o].lazy_val;
        tree[ls].lazy_val = tree[rs].lazy_val = tree[o].lazy_val;
        tree[o].lazy_val = INF;
    }
    if (tree[o].lazy_id1 != -1) {
        tree[ls].id1 = tree[rs].id1 = tree[o].lazy_id1;
        tree[ls].lazy_id1 = tree[rs].lazy_id1 = tree[o].lazy_id1;
        tree[o].lazy_id1 = -1;
    }
    if (tree[o].lazy_id2 != -1) {
        tree[ls].id2 = tree[rs].id2 = tree[o].lazy_id2;
        tree[ls].lazy_id2 = tree[rs].lazy_id2 = tree[o].lazy_id2;
        tree[o].lazy_id2 = -1;
    }
    if (tree[o].lazy_lid != -1) {
        tree[ls].lid = tree[rs].lid = tree[o].lazy_lid;
        tree[ls].lazy_lid = tree[rs].lazy_lid = tree[o].lazy_lid;
        tree[o].lazy_lid = -1;
    }
}

void build(int o, int l, int r) {
    // 线段树初始化建树
    if (l == r) {
        tree[o].val = 0;
        tree[o].lazy_val = INF;
        tree[o].id1 = tree[o].id2 = tree[o].lid = 0;
        tree[o].lazy_id1 = tree[o].lazy_id2 = tree[o].lazy_lid = -1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    tree[o].lazy_val = INF;
    pushup(o);
}

#define ALLOK -2
int find_right(int o, int l, int r, int ql, int qid) {
    // 操作一中，固定左端点，寻找右端点可能的最大值
    // 这里没有考虑和右端点的比较，直接寻找了最大的可能值
    pushdown(o);
    if (r < ql || tree[o].id1 == qid || tree[o].id1 == 0) {
        // 全部符合条件
        return ALLOK;
    } else if (tree[o].id2 != -1) {
        // 不符合条件，返回该区域左边第一个
        return l - 1;
    } else {
        // 需要寻找确切位置
        // 先查找左区间，如果左区间全满足则再寻找右区间
        int mid = (l + r) >> 1;
        int leftPart = (ql <= mid) ? find_right(ls, l, mid, ql, qid) : ALLOK;
        return (leftPart == ALLOK) ? find_right(rs, mid + 1, r, ql, qid)
                                : leftPart;
    }
}
#undef ALLOK

void modify_val(int o, int l, int r, int ql, int qr, int val, int id,
                bool ignoreLid = false) {
    // 若 val = INF 代表不需要对 val 进行处理
    // 若 ignoreLid = true 则不对 lid 进行更改
    if (l >= ql && r <= qr) {
        if (val != INF)
            tree[o].val = tree[o].lazy_val = val;
        tree[o].id1 = tree[o].lazy_id1 = id;
        tree[o].id2 = tree[o].lazy_id2 = id;
        if (!ignoreLid)
            tree[o].lid = tree[o].lazy_lid = id;
        return;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        modify_val(ls, l, mid, ql, qr, val, id, ignoreLid);
    }
    if (qr > mid) {
        modify_val(rs, mid + 1, r, ql, qr, val, id, ignoreLid);
    }
    pushup(o);
}

bool is_same_id(int o, int l, int r, int ql, int qr, int id,
                bool isRecover = false) {
    // 判断该区域 id 和 lid 是否满足条件
    if (l >= ql && r <= qr) {
        if (isRecover) {
            // 检查 id = 0 且 lid = id
            return (tree[o].id2 == 0 && tree[o].lid == id);
        } else {
            // 检查 id = id
            return (tree[o].id2 == id);
        }
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    bool isSame = true;
    if (ql <= mid) {
        isSame = isSame && is_same_id(ls, l, mid, ql, qr, id, isRecover);
    }
    if (qr > mid && isSame) {
        isSame = isSame && is_same_id(rs, mid + 1, r, ql, qr, id, isRecover);
    }
    return isSame;
}

int query_val(int o, int l, int r, int p) {
    // 线段树单点求值：val
    if (p >= l && p <= r && tree[o].val != INF) {
        return tree[o].val;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (p <= mid)
        return query_val(ls, l, mid, p);
    else
        return query_val(rs, mid + 1, r, p);
}

int query_id(int o, int l, int r, int p) {
    // 线段树单点求值：id2
    if (p >= l && p <= r && tree[o].id2 != -1) {
        return tree[o].id2;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (p <= mid)
        return query_id(ls, l, mid, p);
    else
        return query_id(rs, mid + 1, r, p);
}

#undef ls
#undef rs

struct instruction {
    int opt, id, l, r, x;
} inst[maxn];
// numList 存储所有可能出现的数，totnum 表示个数
int numList[maxn << 2], totnum;
void discretization() {
    // 离散化操作
    sort(numList + 1, numList + 1 + totnum);
    totnum = unique(numList + 1, numList + 1 + totnum) - numList - 1;
    m = totnum;
    for (int i = 1; i <= k; ++i) {
        if (inst[i].opt == 0 || inst[i].opt == 1 || inst[i].opt == 2) {
            inst[i].l =
                lower_bound(numList + 1, numList + 1 + totnum, inst[i].l) -
                numList;
            inst[i].r =
                lower_bound(numList + 1, numList + 1 + totnum, inst[i].r) -
                numList;
        } else {
            inst[i].x =
                lower_bound(numList + 1, numList + 1 + totnum, inst[i].x) -
                numList;
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    numList[++totnum] = 1;
    numList[++totnum] = m;
    for (int i = 1; i <= k; ++i) {
        scanf("%d", &inst[i].opt);
        if (inst[i].opt == 0) {
            scanf("%d%d%d%d", &inst[i].id, &inst[i].l, &inst[i].r, &inst[i].x);
            numList[++totnum] = inst[i].l;
            numList[++totnum] = inst[i].r;
            // 注意边界问题，为了方便这里把交界处两点分开了，下同
            if (inst[i].l != 1)
                numList[++totnum] = inst[i].l - 1;
            if (inst[i].r != m)
                numList[++totnum] = inst[i].r + 1;
        } else if (inst[i].opt == 1) {
            scanf("%d%d%d", &inst[i].id, &inst[i].l, &inst[i].r);
            numList[++totnum] = inst[i].l;
            numList[++totnum] = inst[i].r;
            if (inst[i].l != 1)
                numList[++totnum] = inst[i].l - 1;
            if (inst[i].r != m)
                numList[++totnum] = inst[i].r + 1;
        } else if (inst[i].opt == 2) {
            scanf("%d%d%d", &inst[i].id, &inst[i].l, &inst[i].r);
            numList[++totnum] = inst[i].l;
            numList[++totnum] = inst[i].r;
            if (inst[i].l != 1)
                numList[++totnum] = inst[i].l - 1;
            if (inst[i].r != m)
                numList[++totnum] = inst[i].r + 1;
        } else {
            scanf("%d", &inst[i].x);
            // 对于查询的数，不需要进行离散化，查找第一个比它大的数即可
        }
    }

    // 离散化处理
    discretization();

    // 线段树初始化建树
    build(1, 1, m);

    // 进行操作
    for (int i = 1; i <= k; ++i) {
        if (inst[i].opt == 0) {
            // 写入操作：先求得范围，再进行填充
            int r = find_right(1, 1, m, inst[i].l, inst[i].id);
            if (r == -2)
                // r = -2 代表全部满足
                r = inst[i].r;
            else
                r = min(r, inst[i].r);
            if (inst[i].l <= r) {
                printf("%d\n", numList[r]); // 注意返回离散化前的值
                modify_val(1, 1, m, inst[i].l, r, inst[i].x, inst[i].id);
            } else {
                printf("-1\n");
            }
        } else if (inst[i].opt == 1) {
            // 删除操作：先判断是否可行，之后执行
            if (is_same_id(1, 1, m, inst[i].l, inst[i].r, inst[i].id)) {
                printf("OK\n");
                modify_val(1, 1, m, inst[i].l, inst[i].r, INF, 0, true);
            } else {
                printf("FAIL\n");
            }
        } else if (inst[i].opt == 2) {
            // 恢复操作：先判断是否可行，之后执行
            if (is_same_id(1, 1, m, inst[i].l, inst[i].r, inst[i].id, true)) {
                printf("OK\n");
                modify_val(1, 1, m, inst[i].l, inst[i].r, INF, inst[i].id,
                        true);
            } else {
                printf("FAIL\n");
            }
        } else if (inst[i].opt == 3) {
            // 读取操作：分别读取 id 和 val
            int id = query_id(1, 1, m, inst[i].x);
            int val = query_val(1, 1, m, inst[i].x);
            if (id == 0) {
                printf("0 0\n");
            } else {
                printf("%d %d\n", id, val);
            }
        }
    }
    return 0;
}

100% 数据——动态开点线段树

在上一题的做法中，我们需要先读入所有的数据并进行离散化处理，之后再执行主要的算法过程。 但不是所有的题目都可以在执行主要的算法过程前得到所有的输入数据。

离线算法

要求在执行算法前输入数据已知的算法称为离线算法。 一般而言，如果没有对输入输出做特殊处理，则可以用离线算法解决该问题。

在线算法

不需要输入数据已知就可以执行的算法称为在线算法。 一般而言，如果对输入输出做特殊处理（如本次的询问需要与上次执行的答案进行异或才能得到真正的询问），则只能用离线算法解决该问题。

对于一道能用离线和在线算法解决的题目，如果出题人对数据进行了加密处理，导致只能使用在线算法，则我们称这道题是强制在线的。

离散化需要事先知道所有可能出现的数，所以是离线算法。如果要强制在线，就需要另一种思路。

同样，从询问涉及的点有限出发，我们考虑最多能涉及线段树上点的个数。 线段树的高度为 \(\mathrm{O}(\log m)\)，假设每个涉及查询的点都到达了线段树的叶子结点， 且不考虑根到任意两个结点之间重复的节点，则总共涉及的线段树节点数的个数为 \(\mathrm{O}(k\log m)\)。 所以我们只需要为用到的节点开辟空间即可。

针对一般的线段树，我们是预先建好了整棵线段树（build 函数）， 每个线段树节点的左右子节点编号与其本身编号都是对应的（通常一个子节点是父结点的二倍，而另一个子节点则相差 1）。 而对于这种只为需要用到节点开辟空间的线段树，其左右子树只有在需要的时候才会被创建， 所以编号间没有特定关系，需要记录。

考虑什么时候需要开辟新结点：在初始化的时候需要开创一个根节点； 在进行修改及查询的时候，如果区间不是所要的区间，则需要开创新的节点。 有一个技巧是，在修改和查询的时候往往要下传标记（pushdown），可以在此之前检查是否需要开创节点。

代码实现

C++

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 200010;
const int INF = 1e9 + 10;
int n, m, k;
struct treenode {
    // 左右子节点编号
    int lc, rc;
    // 当前节点的值，若不唯一则为 INF；lazy 为 INF 表示无延迟更新
    int val, lazy_val;
    // 当前占用 id，若存在除 0 以外两种 id 则为 -1；lazy 为 -1 表示无延迟更新
    int id1, lazy_id1;
    // 当前占用 id，若存在两种 id 则为 -1；lazy 为 -1 表示无延迟更新
    int id2, lazy_id2;
    // 上次占用 id，若存在两种 id 则为 -1；lazy 为 -1表示无延迟更新
    int lid, lazy_lid;
} tree[maxn << 5];
int cnt; // 线段树节点个数
#define ls tree[o].lc
#define rs tree[o].rc
int insert_node() {
    // 向线段树中插入一个节点
    ++cnt;
    tree[cnt].lc = tree[cnt].rc = 0;
    tree[cnt].val = 0;
    tree[cnt].id1 = tree[cnt].id2 = 0;
    tree[cnt].lid = 0;
    tree[cnt].lazy_val = INF;
    tree[cnt].lazy_id1 = tree[cnt].lazy_id2 = -1;
    tree[cnt].lid = -1;
    return cnt;
}

void pushup(int o) {
    // 线段树上传操作，合并左右子树结果
    // val 的合并
    tree[o].val = (tree[ls].val == tree[rs].val) ? tree[ls].val : INF;
    // id1 的合并
    if (tree[ls].id1 == -1 || tree[rs].id1 == -1) {
        tree[o].id1 = -1;
    } else if (tree[ls].id1 == tree[rs].id1) {
        tree[o].id1 = tree[ls].id1;
    } else if (tree[ls].id1 == 0) {
        tree[o].id1 = tree[rs].id1;
    } else if (tree[rs].id1 == 0) {
        tree[o].id1 = tree[ls].id1;
    } else {
        tree[o].id1 = -1;
    }
    // id2 的合并
    if (tree[ls].id2 == -1 || tree[rs].id2 == -1) {
        tree[o].id2 = -1;
    } else if (tree[ls].id2 == tree[rs].id2) {
        tree[o].id2 = tree[ls].id2;
    } else {
        tree[o].id2 = -1;
    }
    // lid 的合并
    if (tree[ls].lid == -1 || tree[rs].lid == -1) {
        tree[o].lid = -1;
    } else if (tree[ls].lid == tree[rs].lid) {
        tree[o].lid = tree[ls].lid;
    } else {
        tree[o].lid = -1;
    }
}

void pushdown(int o) {
    // 线段树标记下传操作
    // 如果对应点未被创建，则进行创建
    if (!ls)
        ls = insert_node();
    if (!rs)
        rs = insert_node();
    if (tree[o].lazy_val != INF) {
        tree[ls].val = tree[rs].val = tree[o].lazy_val;
        tree[ls].lazy_val = tree[rs].lazy_val = tree[o].lazy_val;
        tree[o].lazy_val = INF;
    }
    if (tree[o].lazy_id1 != -1) {
        tree[ls].id1 = tree[rs].id1 = tree[o].lazy_id1;
        tree[ls].lazy_id1 = tree[rs].lazy_id1 = tree[o].lazy_id1;
        tree[o].lazy_id1 = -1;
    }
    if (tree[o].lazy_id2 != -1) {
        tree[ls].id2 = tree[rs].id2 = tree[o].lazy_id2;
        tree[ls].lazy_id2 = tree[rs].lazy_id2 = tree[o].lazy_id2;
        tree[o].lazy_id2 = -1;
    }
    if (tree[o].lazy_lid != -1) {
        tree[ls].lid = tree[rs].lid = tree[o].lazy_lid;
        tree[ls].lazy_lid = tree[rs].lazy_lid = tree[o].lazy_lid;
        tree[o].lazy_lid = -1;
    }
}

#define ALLOK -2
int find_right(int o, int l, int r, int ql, int qid) {
    // 操作一中，固定左端点，寻找右端点可能的最大值
    // 这里没有考虑和右端点的比较，直接寻找了最大的可能值
    pushdown(o);
    if (r < ql || tree[o].id1 == qid || tree[o].id1 == 0) {
        // 全部符合条件
        return ALLOK;
    } else if (tree[o].id2 != -1) {
        // 不符合条件，返回该区域左边第一个
        return l - 1;
    } else {
        // 需要寻找确切位置
        // 先查找左区间，如果左区间全满足则再寻找右区间
        int mid = (l + r) >> 1;
        int leftPart = (ql <= mid) ? find_right(ls, l, mid, ql, qid) : ALLOK;
        return (leftPart == ALLOK) ? find_right(rs, mid + 1, r, ql, qid)
                                : leftPart;
    }
}
#undef ALLOK

void modify_val(int o, int l, int r, int ql, int qr, int val, int id,
                bool ignoreLid = false) {
    // 若 val = INF 代表不需要对 val 进行处理
    // 若 ignoreLid = true 则不对 lid 进行更改
    if (l >= ql && r <= qr) {
        if (val != INF)
            tree[o].val = tree[o].lazy_val = val;
        tree[o].id1 = tree[o].lazy_id1 = id;
        tree[o].id2 = tree[o].lazy_id2 = id;
        if (!ignoreLid)
            tree[o].lid = tree[o].lazy_lid = id;
        return;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        modify_val(ls, l, mid, ql, qr, val, id, ignoreLid);
    }
    if (qr > mid) {
        modify_val(rs, mid + 1, r, ql, qr, val, id, ignoreLid);
    }
    pushup(o);
}

bool is_same_id(int o, int l, int r, int ql, int qr, int id,
                bool isRecover = false) {
    // 判断该区域 id 和 lid 是否满足条件
    if (l >= ql && r <= qr) {
        if (isRecover) {
            // 检查 id = 0 且 lid = id
            return (tree[o].id2 == 0 && tree[o].lid == id);
        } else {
            // 检查 id = id
            return (tree[o].id2 == id);
        }
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    bool isSame = true;
    if (ql <= mid) {
        isSame = isSame && is_same_id(ls, l, mid, ql, qr, id, isRecover);
    }
    if (qr > mid && isSame) {
        isSame = isSame && is_same_id(rs, mid + 1, r, ql, qr, id, isRecover);
    }
    return isSame;
}

int query_val(int o, int l, int r, int p) {
    // 线段树单点求值：val
    if (p >= l && p <= r && tree[o].val != INF) {
        return tree[o].val;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (p <= mid)
        return query_val(ls, l, mid, p);
    else
        return query_val(rs, mid + 1, r, p);
}

int query_id(int o, int l, int r, int p) {
    // 线段树单点求值：id2
    if (p >= l && p <= r && tree[o].id2 != -1) {
        return tree[o].id2;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (p <= mid)
        return query_id(ls, l, mid, p);
    else
        return query_id(rs, mid + 1, r, p);
}

#undef ls
#undef rs

int main() {
    scanf("%d%d%d", &n, &m, &k);
    // 创建根节点
    insert_node();
    // 进行操作
    int r_opt, r_id, r_l, r_r, r_x, r_p;
    while (k--) {
        scanf("%d", &r_opt);
        if (r_opt == 0) {
            // 写入
            scanf("%d%d%d%d", &r_id, &r_l, &r_r, &r_x);
            int r = find_right(1, 1, m, r_l, r_id);
            if (r == -2)
                r = r_r;
            else
                r = min(r, r_r);
            if (r_l <= r) {
                printf("%d\n", r);
                modify_val(1, 1, m, r_l, r, r_x, r_id);
            } else {
                printf("-1\n");
            }
        } else if (r_opt == 1) {
            // 删除
            scanf("%d%d%d", &r_id, &r_l, &r_r);
            if (is_same_id(1, 1, m, r_l, r_r, r_id)) {
                printf("OK\n");
                modify_val(1, 1, m, r_l, r_r, INF, 0, true);
            } else {
                printf("FAIL\n");
            }
        } else if (r_opt == 2) {
            // 恢复
            scanf("%d%d%d", &r_id, &r_l, &r_r);
            if (is_same_id(1, 1, m, r_l, r_r, r_id, true)) {
                printf("OK\n");
                modify_val(1, 1, m, r_l, r_r, INF, r_id, true);
            } else {
                printf("FAIL\n");
            }
        } else {
            // 查询
            scanf("%d", &r_p);
            int id = query_id(1, 1, m, r_p);
            int val = query_val(1, 1, m, r_p);
            if (id == 0) {
                printf("0 0\n");
            } else {
                printf("%d %d\n", id, val);
            }
        }
    }
    return 0;
}

评论