BZOJ1269 - [AHOI2006]文本编辑器editor

2016/10/16

继续说昨天 thx 菊苣讲 Hash 的时候顺带提了下 ext/rope 这个库,然后 这篇文章 告诉我 BZOJ1269 是 ext/rope 的大水题。

简单来说就是维护一个字符串,支持随机插入,区间反转,区间删除,单点查询。

首先 rope 这货的 insert/erase/get 是 O(logN) 的,然后区间反转这个东西可以通过维护正向串和逆向串实现。

然后抄抄抄!Orz

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
crope a, b, tmp;
char buf[10];
int now, N, len, size;
char str[1<<21], rstr[1<<21];

int main() {
    cin >> N;

    while(N--) {
        scanf("%s", buf);
        switch(buf[0]) {
            case 'M': { scanf("%d", &now); break; }
            case 'P': { now--; break; }
            case 'N': { now++; break; }
            case 'G': { putchar(a[now]); putchar('\n'); break; }
            case 'I': {
                cin >> size;
                len = a.length();
                for(int i=0;i<size;i++) {
                    do { str[i] = getchar(); }
                    while(str[i] == '\n');
                    rstr[size-i-1] = str[i];
                }
                rstr[size] = str[size] = '\0';
                a.insert(now, str);
                b.insert(len-now, rstr);
                break;
            }
            case 'D': {
                scanf("%d", &size);
                len = a.length();
                a.erase(now, size);
                b.erase(len-now-size, size);
                break;
            }
            case 'R': {
                scanf("%d", &size);
                len = a.length();
                tmp = a.substr(now, size);
                a = a.substr(0, now) + b.substr(len-now-size, size) + a.substr(now+size, len-now-size);
                b = b.substr(0, len-now-size) + tmp + b.substr(len-now,now);
                break;
            }
        }
    }
}