TJ 2 P4567
HansLimon
2019-11-06 12:03:59
# 注意，非正解
###### rope大法好
[如果你不会rope](http://iwo.im/?q=C%2B%2B%20rope)
之后我会写一篇rope的博客的(~~咕咕咕~~)
### Part 1
我们先看看有哪些操作能直接(或者稍经思考)解决
- Move ${\color{lightgreen}\text{OK}}$
- Insert ${\color{lightgreen}\text{OK}}$
- Delete ${\color{lightgreen}\text{OK}}$
- Rotate ${\color{red}\text{NO}}$
- Get ${\color{lightgreen}\text{OK}}$
- Prev ${\color{lightgreen}\text{OK}}$
- Next ${\color{lightgreen}\text{OK}}$
这么看来好像只有$rotate$有一点问题(~~小声bb~~)
### Part 2
关于光标：
我们模拟一个cnt代表光标，用以执行Move、Prev、Next及Get指令，如下
```cpp
reader>>k//慢读qwq
if (inst[0] == 'M')cnt = k;
```
```cpp
else if (inst[0] == 'P'/* == "Prev"*/)cnt --;
else if (inst[0] == 'N'/* == "Next"*/)cnt ++;
```
### Part 3
关于插入删除：
```cpp
reader>>k;
......OTHER CODES.....
else if (inst[0] == 'I'){
for (register int i = 0;i < k;i ++){
goal[i] = getchar();
}
goal[k] = '\0';
a.insert(cnt, goal);//a就是我们的rope
}
```
但是为了便于rotate操作，我们可以考虑再来一个倒着记录的rope b，因此插入语句应该这样：
```cpp
reader>>k;
......OTHER CODES.....
else if (inst[0] == 'I'){
register int length = a.size();
for (register int i = 0;i < k;i ++){
bac[k - i - 1] = goal[i] = getchar();//bac是当前S反过来的char数组
}
goal[k] = bac[k] = '\0';
a.insert(cnt, goal);
b.insert(length - cnt, bac);
}
```
同理，删除操作如下
```cpp
else if (inst[0] == 'D'){
register int length = a.size();
a.erase(cnt, k);
b.erase(length - cnt - k, k);
}
```
### Part 4
现在剩下的就是恶心的$rotate$了
由于rope里面的链式操作使得我们不能直接删除再插入，而STL自带的函数常数又太大。所以我们要换条路子。
最开始我的想法其实是把rotate换成Get、Next、Delete这三个指令的组合，每一次从b中Get一个到临时的char数组中然后再Next，重复K次，最后再插回去。
###### 感觉这样应该能慢到飞起
所以想了想觉得应该额外来一个临时的rope tmp，用substr方法一系列瞎操作，详见代码，感觉应该挺好理解：
```cpp
else if (inst[0] == 'R'){
register int length = a.size();
tmp = a.substr(cnt, k);//取出来
a = a.substr(0, cnt) + b.substr(length - cnt - k, k) + a.substr(cnt + k, length - cnt - k);//两端不变，中间把b对应位置移过来
b = b.substr(0, length - cnt - k) + tmp + b.substr(length - cnt, cnt);//一样qwq
}
```
嗯 o\(\*￣▽￣\*\)o 就酱\~
### Part 5
快乐的放码时间：
```cpp
#include <cstdio>
#include <ext/rope>
const int N = 1<<22 + 7;
int n, k, cnt;
char now, inst[N], goal[N], bac[N];
struct readers{
char now;
bool state;
readers operator >>(int &goal){
goal = 0;
state = true;
while (now = getchar(), now < 48 || now > 57)state = now^45;
while (48 <= now && now <= 57){
goal = (goal<<1) + (goal<<3) + (now^48);
now = getchar();
}
if (!state)goal = -goal;
return *this;
}
}reader;
__gnu_cxx::rope<char> a, b, tmp;
int main(){
reader>>n;
while (n --){
/*bef:*/scanf("%s", inst);
// if (inst[0] == 10)goto bef;
// printf("inst:"), puts(inst);
if (inst[0] == 'I'/*"Insert"*/ || inst[0] == 'M'/* == "Move"*/ || inst[0] == 'D'/* == "Delete"*/ || inst[0] == 'R'/* == "Rotate"*/){
reader>>k;
if (inst[0] == 'M')cnt = k;
else if (inst[0] == 'I'){
register int length = a.size();
for (register int i = 0;i < k;i ++){
bac[k - i - 1] = goal[i] = getchar();
}
goal[k] = bac[k] = '\0';
a.insert(cnt, goal);
b.insert(length - cnt, bac);
}else if (inst[0] == 'D'){
register int length = a.size();
a.erase(cnt, k);
b.erase(length - cnt - k, k);
}else if (inst[0] == 'R'){
register int length = a.size();
tmp = a.substr(cnt, k);
a = a.substr(0, cnt) + b.substr(length - cnt - k, k) + a.substr(cnt + k, length - cnt - k);
b = b.substr(0, length - cnt - k) + tmp + b.substr(length - cnt, cnt);
}
}else if (inst[0] == 'P'/* == "Prev"*/)cnt --;
else if (inst[0] == 'N'/* == "Next"*/)cnt ++;
else if (inst[0] == 'G'/* == "Get"*/){
putchar(a[cnt]);
if (a[cnt] != 10)putchar(10);
}
}
return 0;
}
```
本来是想挖个坑的，想让你们体验一下刚开始我用string的痛qwq
### Part 6
还有一点，可能有人不是很清楚Get操作那里，因为
${\color{red}\text{换行符也是可见字符啊qwq}}$(详情请见**输入格式**)
但是输出的时候只输出一行，所以如果已经输出了换行的话就不能再来换行了qwq