#P2021124. 磁盘文件操作

磁盘文件操作

磁盘文件操作

题目描述

题目背景

小C对计算机运行的原理很感兴趣,经常进行一些研究和实验。

有一天,他在尝试删除一个好几GB大小的文件时,惊奇地发现删除操作几乎在一瞬间就完成了!这让他很是纳闷:如果计算机在每次删除文件时都直接在磁盘上把对应的数据抹掉,不是应该要花挺长时间吗?

于是他找来了小S和小P一起讨论。小S说,或许计算机是一个很“懒”的体系,在删除时不会真的去抹除数据吧?而小P则更见多识广一些,他当即找来了一个号称能“恢复磁盘数据”的软件,当场把小C刚刚删除的文件恢复了!

这让小C有了更强的好奇心,于是他们决定设计一个模型来模拟一个磁盘文件的写入、删除及恢复过程。但是在他们生活的西西艾弗岛上没有合适的条件来运行他们的模型,于是他们联系了带着一台算力超强的电脑来西西艾弗岛旅游的你来帮助他们。

题目描述

在小C、小S和小P设计的模型中,计算机中有n段程序(编号为1∼n),它们共享一块大小为m的磁盘空间(编号为1∼m),磁盘上的每个位置可以写入一个整数。

最初,磁盘上每个位置上的数都是0,并不被任何程序占用。

现在,这n段程序同时执行,在某一时刻,某段程序可能对磁盘数据进行读写等操作。

操作共k个,按时间先后顺序给出,具体操作如下:

0idlrx:编号为id的程序尝试向磁盘空间中[l,r]位置上每个位置都写入一个整数x。

操作执行过程中,程序id会尝试从最左端l开始向右顺次写入数据。

对于每个位置,若目前不被任何程序占用,则成功写入整数x,并将其视为被程序id占用;

若该位置目前正被程序id自己占用,则这次写入的x可以覆盖之前写入的结果,此后该位置仍被程序id占用;

直到成功向r位置写入数据,或遇到第一个正在被其他程序占用的位置为止,此时该操作立刻中断。

1idlr:程序id尝试删除磁盘中[l,r]位置上的所有数据。

这一操作当且仅当[l,r]区间内所有位置都正在被程序id占用时才能成功执行。

执行效果为将其中所有位置都解除占用,即恢复到可以被任意程序写入的状态。但为了便于恢复数据,不会立即将全部位置重新覆盖成0。

否则,认为此操作执行失败,不进行任何修改。

2idlr:程序id尝试恢复磁盘中[l,r]位置上的所有数据。

这一操作当且仅当[l,r]区间内所有位置都未被占用,且上一次被占用是被程序id占用时才能成功执行

执行效果为将其中所有位置恢复为被程序id占用的状态,同时由于之前删除操作并未改变其存储的值,因此本次操作也不需要改变每个位置上的值。

否则,认为此操作执行失败,不进行任何修改。

3p:尝试读取磁盘中p位置的数据,返回结果为两个整数。

如果该位置当前正被程序id占用且存储的值为p,返回结果为idp。

如果该位置当前没有被任何程序占用,返回00。

你需要实现一个程序,帮助小C、小S和小P来模拟实现上述过程,并对于每个操作输出操作结果。

输入格式

从标准输入读入数据。

第一行:3个正整数n,m,k。

接下来k行,每行若干个整数描述一个操作,格式如上所述。

输出格式

输出到标准输出。

输出共k行,对于每个操作输出一行。

对于每个写入操作,输出一个整数表示此次操作写入成功的最右位置;特别地如果该操作一个位置也没有写入成功,输出−1。

对于每个删除、恢复操作,若该操作成功,输出一个字符串OK,否则输出一个字符串FAIL。

对于每个读取操作,输出两个整数表示此次查询的结果。

数据范围

(原站未提供,导入后需人工补齐)

样例

3 15 12
0 1 1 5 -1
0 2 10 13 2
0 1 4 14 6
1 1 2 8
3 1
3 3
3 14
2 1 3 5
0 3 7 8 -4
2 1 6 8
1 3 6 7
0 2 5 7 3
5
13
9
OK
1 -1
0 0
0 0
OK
8
FAIL
FAIL
-1

提示

子任务

对于25%的数据,n,k≤2000,m≤10000;

对于另外15%的数据,没有删除、恢复操作;

对于另外20%的数据,没有恢复操作;

对于另外15%的数据,n=1。

对于100%的数据,1≤n,k≤2×10^5,1≤m≤10^9,1≤id≤n,1≤l≤r≤m,1≤p≤m,|x|≤10^9。