[CSP202112-4] 磁盘文件操作–动态开点线段树+线段树上二分
这题一看区间长度 $10^9$ ,如果用全强制在线做法显然要上动态开点线段树(不过这题离散化线段树也是可以的,只不过有点麻烦我不愿意写)
然后我们注意一下题目当中需要维护哪些内容:
- 占用当前片段的程序id
- 被删除之后曾经占用当前片段的程序id
- 被占用/被删除之前曾经的值
那么这三个我们就可以用三个数来维护。本题对他们分别有赋值操作,那么显然就应该使用赋值懒标记来维护区间懒惰操作。
然后在维护根节点信息时,由于我们只需要知道区间当中这些信息是否是一致的,那就只要判断左右子树如果id一致,根节点就用相同id;反之则让根节点id为 -1 ,没有被占用就用 0 就可以了。
然后分别注意一下这几个操作当中都需要什么。
占用操作首先需要找到可以赋值的最右侧端点在哪里。我们需要使用二分查找。搜索的底层是只要当前块没有被占用,或者占用id一致即可。此时最右端点就是当前区间右端点和目标区间右端点的最小值。否则就向左或者右侧进行查找。如果两边都可以查找,且左侧查出来的右端点能够连通右边,那就需要接着找右侧的最大端点。
接下来无脑赋值即可,赋值只需要改变当前id和value,并且把赋值标记给摆上即可。
删除操作首先需要检查整个区间的id是否相同且等于对应id。如果等于的话,就无脑删除,只需要将曾经id赋值为当前id、再把当前id改为0,就行了,不需要管value(因为恢复的时候这个value还可以接着用)。然后赋值对应标记即可。
恢复的话,就需要看对应段的pre id是否等于对应id,同理如果等于,就无脑恢复,只需要把当前id改为曾经id即可,标记页只用打给当前id。
在查找的时候,和上面合并到根节点的思路一样,只要出现不符合预期情况(比如恢复时发现当前节点还在占用或者左右两边区间的id不一致)则返回-1。然后返回的id只要和查找id一致,就说明是可以后续操作的。
最后是查找,就正常二分查找就行,然后如果当前id不是0,就输出对应value,否则就需要把value改为0。
在CCF官方数据中,最强的点是时间占用281ms,空间占用196MB。说明动态开点线段树还是很吃空间消耗的。如果这题又要求强制在线又卡空间限制的话,动态开点splay等带有删除节点功能的数据结构应该是更好的选择。
但是其实我这个写法更关键的在于 vector
自身 push_back
原理带来的大常数,不仅记录了额外信息,其每次扩容都是成倍增长从而保证分摊 $O(1)$ 。如果我们只开一个静态数组,那节点上限应该是 $2\times \log L \times n$ ,其中 $L$ 是整个区间长度,$n$ 是操作+查询的次数。改成静态数组之后为空间占用136.1MB
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int rd()
{
int k = 0, f = 1;
char s = getchar();
while (s < '0' || s > '9')
{
if (s == '-')
f = -1;
s = getchar();
}
while (s >= '0' && s <= '9')
{
k = (k << 1) + (k << 3) + (s ^ '0');
s = getchar();
}
return f > 0 ? k : -k;
}
void wr(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar((x % 10) ^ '0');
}
struct dynamic_segment_tree
{
static const int INF = 1000000000;
static const int NOT_ONLY = 1145141919;
struct info_node // 用于记录磁盘位置的信息
{
int id, pre_id, val; // 程序id, 历史值, 当前值
// id : 未占用的id为0 同一区间有两种不同id设为-1
// pre_id : 只有被清除过还能恢复的时候才会用上
bool tag_id, tag_pre, tag_val; // 三者懒标记, 只有赋值标志所以用bool就行
};
struct node // 节点信息=数据信息+左右子节点下标
{
int lc, rc;
info_node info;
};
vector<node> tr;
int rt; // 根节点下标 基本上设定为1 放在这里以防万一需要修改
int interval_L, interval_R;
dynamic_segment_tree(int L = 1, int R = INF)
{
interval_L = L, interval_R = R;
tr.clear(), tr.resize(2), rt = 1;
}
// 动态开点
void alloc_lchild(int u)
{
if (tr[u].lc == 0)
tr[u].lc = tr.size(), tr.push_back(node());
}
void alloc_rchild(int u)
{
if (tr[u].rc == 0)
tr[u].rc = tr.size(), tr.push_back(node());
}
void alloc_childs(int u) { alloc_lchild(u), alloc_rchild(u); }
void pushup(int u)
{
int lc = tr[u].lc, rc = tr[u].rc;
// 如果两边一致
if (tr[lc].info.id == tr[rc].info.id && tr[lc].info.id != -1)
{
tr[u].info.id = tr[lc].info.id;
// 如果两者恢复的前id相同 那么当前节点代表的区间就和他们一致
if (tr[u].info.id == 0 && tr[lc].info.pre_id == tr[rc].info.pre_id)
tr[u].info.pre_id = tr[lc].info.pre_id;
else
tr[u].info.pre_id = -1;
// 两边值的合并, 不同则说明不唯一, 用一个值域外的值表示即可
if (tr[lc].info.val == tr[rc].info.val)
tr[u].info.val = tr[lc].info.val;
else
tr[u].info.val = NOT_ONLY;
}
else
tr[u].info.id = -1;
}
void pushdown(int u)
{
alloc_childs(u);
int lc = tr[u].lc, rc = tr[u].rc;
if (tr[u].info.tag_id)
{
tr[lc].info.tag_id = tr[rc].info.tag_id = 1;
tr[lc].info.id = tr[rc].info.id = tr[u].info.id;
tr[u].info.tag_id = 0;
}
if (tr[u].info.tag_pre)
{
tr[lc].info.tag_pre = tr[rc].info.tag_pre = 1;
tr[lc].info.pre_id = tr[rc].info.pre_id = tr[u].info.pre_id;
tr[u].info.tag_pre = 0;
}
if (tr[u].info.tag_val)
{
tr[lc].info.tag_val = tr[rc].info.tag_val = 1;
tr[lc].info.val = tr[rc].info.val = tr[u].info.val;
tr[u].info.tag_val = 0;
}
}
// [L, R] 是当前搜索区间 [l, r] 是目标搜寻区间
int _search(int u, int L, int R, int l, int r, int id)
{
// 寻找可以赋值的最右侧
// 满足条件 : 当前区间状态一致+当前区间没被占用或是被同id占用
if (tr[u].info.id != -1)
return (tr[u].info.id == id || tr[u].info.id == 0) ? min(R, r) : -1;
pushdown(u);
int M = (L + R) >> 1;
if (l > M)
return _search(tr[u].rc, M + 1, R, l, r, id);
if (r <= M)
return _search(tr[u].lc, L, M, l, r, id);
// 两边区间都要搜索, 如果左半侧正好到头,再搜右半边
int res = _search(tr[u].lc, L, M, l, r, id);
if (res == M)
res = max(res, _search(tr[u].rc, M + 1, R, l, r, id));
return res;
}
// 找 [l, r] 中可被id占用的最右侧
int search(int l, int r, int id) { return _search(rt, interval_L, interval_R, l, r, id); }
void _set(int u, int L, int R, int l, int r, int id, int val)
{
if (R < l || L > r)
return;
if (l <= L && R <= r)
{
tr[u].info.id = id, tr[u].info.val = val;
tr[u].info.tag_id = tr[u].info.tag_val = 1;
return;
}
pushdown(u);
int M = (L + R) >> 1;
_set(tr[u].lc, L, M, l, r, id, val);
_set(tr[u].rc, M + 1, R, l, r, id, val);
pushup(u);
}
// 这里赋值不考虑区间可行性(交给search来做),强制覆盖即可
// 同理后面的erase和restore也是强制覆盖
void set(int l, int r, int id, int val) { _set(rt, interval_L, interval_R, l, r, id, val); }
int set_real(int l, int r, int id, int val)
{
int real_r = search(l, r, id);
if (real_r != -1)
set(l, real_r, id, val);
return real_r;
}
// cur_or_pre true : cur false : pre
int find_id(int u, int L, int R, int l, int r, int id, bool cur_or_pre)
{
if (l <= L && R <= r)
{
if (cur_or_pre)
return tr[u].info.id;
else
return tr[u].info.id == 0 ? tr[u].info.pre_id : -1;
}
pushdown(u);
int M = (L + R) >> 1;
if (l > M)
return find_id(tr[u].rc, M + 1, R, l, r, id, cur_or_pre);
if (r <= M)
return find_id(tr[u].lc, L, M, l, r, id, cur_or_pre);
int l_res = find_id(tr[u].lc, L, M, l, r, id, cur_or_pre);
if (l_res == -1)
return -1;
int r_res = find_id(tr[u].rc, M + 1, R, l, r, id, cur_or_pre);
if (r_res == -1 || l_res != r_res)
return -1;
return l_res;
}
bool detect(int l, int r, int id, bool cur_or_pre) { return find_id(rt, interval_L, interval_R, l, r, id, cur_or_pre) == id; }
void _erase(int u, int L, int R, int l, int r)
{
if (R < l || L > r)
return;
if (l <= L && R <= r)
{
tr[u].info.pre_id = tr[u].info.id, tr[u].info.id = 0;
tr[u].info.tag_id = tr[u].info.tag_pre = 1;
return;
}
pushdown(u);
int M = (L + R) >> 1;
_erase(tr[u].lc, L, M, l, r);
_erase(tr[u].rc, M + 1, R, l, r);
pushup(u);
}
void erase(int l, int r) { _erase(rt, interval_L, interval_R, l, r); }
bool erase_real(int l, int r, int id)
{
bool flag = detect(l, r, id, true);
if (flag)
erase(l, r);
return flag;
}
void _restore(int u, int L, int R, int l, int r)
{
if (R < l || L > r)
return;
if (l <= L && R <= r)
{
tr[u].info.id = tr[u].info.pre_id;
tr[u].info.tag_id = 1;
return;
}
pushdown(u);
int M = (L + R) >> 1;
_restore(tr[u].lc, L, M, l, r);
_restore(tr[u].rc, M + 1, R, l, r);
pushup(u);
}
void restore(int l, int r) { _restore(rt, interval_L, interval_R, l, r); }
bool restore_real(int l, int r, int id)
{
bool flag = detect(l, r, id, false);
if (flag)
restore(l, r);
return flag;
}
pair<int, int> _query(int u, int L, int R, int pos)
{
if (L == R)
return make_pair(tr[u].info.id, tr[u].info.id > 0 ? tr[u].info.val : 0);
pushdown(u);
int M = (L + R) >> 1;
if (M >= pos)
return _query(tr[u].lc, L, M, pos);
else
return _query(tr[u].rc, M + 1, R, pos);
}
pair<int, int> query(int pos) { return _query(rt, interval_L, interval_R, pos); }
};
int main()
{
int n = rd(), m = rd(), k = rd(), op = 0, l = 0, r = 0, id = 0, x = 0, pos = 0;
dynamic_segment_tree seg_tree = dynamic_segment_tree(1, m);
pair<int, int> res;
while (k--)
{
op = rd();
switch (op)
{
case 0:
id = rd(), l = rd(), r = rd(), x = rd();
wr(seg_tree.set_real(l, r, id, x)), putchar('\n');
break;
case 1:
id = rd(), l = rd(), r = rd();
puts(seg_tree.erase_real(l, r, id) ? "OK" : "FAIL");
break;
case 2:
id = rd(), l = rd(), r = rd();
puts(seg_tree.restore_real(l, r, id) ? "OK" : "FAIL");
break;
case 3:
pos = rd();
res = seg_tree.query(pos);
wr(res.first), putchar(' '), wr(res.second), putchar('\n');
default:
break;
}
}
}