D

D

一道看上去就很链表的模拟题。
vim 使用者对此题有些莫名的感慨……

在 Normal Mode 下

• 按下 i ：进入 Insert Mode 。
• 按下 f ：紧接着一个小写字母 char，若当前光标后（右）方有至少一个 char ，将光标移动到其所在位置，否则不移动。
• 按下 x ：删除当前光标所在位的字符，后面的字符均会前移一格。
• 按下 h ：将光标向左（前）移动一格，若无法移动就不移动。
• 按下 l ：将光标向右（后）移动一格，若无法移动就不移动。
• 若按下了其他字符：无任何效果。

在 Insert Mode 下

• 按下非 e 小写字母 char ：在光标当前位置前插入这个字母 char。
• 按下 e ：退出 Insert Mode（进入 Normal Mode）。

如果使用链表，绝大部分操作都是 的，唯一看起来具有威胁的就是按下 f 的操作，单次操作极限可以达到 ，但均摊复杂度是正确的。
因为 f 操作单调右移，而题中唯一的左移操作每次只能移动一个单位，也就是说，每次 f 消耗的势能，都只能通过按下 h 来补充，对总体复杂度无影响。

#include <cstdio>
#include <list>
#include <cstring>
#include <algorithm>
#include <ctype.h>
using namespace std;
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
const int maxn = 2e5 + 100;
char s[maxn],t[maxn];
list<char> now;
int len,num;
int main()
{
    read(s + 1),read(t + 1);
    len = strlen(s + 1),num = strlen(t + 1);
    for(int i = 1;i<=len;++i) now.push_back(s[i]);
    int mode = 0;//0 for normal mode,1 for insert mode
    list<char>::iterator cur = now.begin();
    for(int i = 1;i<=num;++i)
    {
        char opt = t[i];
        if(mode == 0)
        {
            if(opt == 'i') mode = 1;
            else if(opt == 'f') 
            {
                char tar = t[++i];
                list<char>::iterator it = cur;
                ++it;
                while(it != now.end() && it != now.end())
                {
                    if(*it == tar) 
                    {
                        cur = it;
                        break;
                    }
                    ++it;
                }
            }
            else if(opt == 'x') cur = now.erase(cur);
            else if(opt == 'h') 
            {
                if(cur == now.begin()) continue;
                --cur;
            }
            else if(opt == 'l')
            {
                if(cur == now.end()) continue;
                ++cur;
            }
        }
        else
        {
            if(opt == 'e') mode = 0;
            else now.insert(cur,opt);
        }
    }
    for(list<char>::iterator it = now.begin();it!=now.end();++it) putchar(*it);
    return 0;
}