【BZOJ-1507】Editor 块状链表

时间：2024-01-12 16:24:50

1507: [NOI2003]Editor

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 3397  Solved: 1360
[Submit][Status][Discuss]

Description

【BZOJ-1507】Editor 块状链表

Input

输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中： 为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。 除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 这里我们有如下假定：  MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。  所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。  DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。  输入文件没有错误。 对C++选手的提示：经测试，最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。

Output

输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。

Sample Input

15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22

Sample Output

.\/.
abcde^_^f.\/.ghijklmno

HINT

Source

Solution

有块状链表和平衡树两种做法。

这里用来练块状链表。

Insert和Delete操作都是现将起始两块分裂，然后加入/拿掉中间的块

注意在Insert和Delete操作后要进行一次合并，防止退化成普通链表。

这题数据范围可能比较大，考虑写个内存池

这题把块的大小控制在3500大概能跑到640ms...

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 2000010

#define Bsize 3500

#define Bnum MAXN/Bsize*3

char S[MAXN];

int loc;

namespace BlockLists

{

    struct BlockListsNode{char data[Bsize+]; int size,next; }B[Bnum+];

    int sz,start;

    queue<int>trash;

    inline int New() {if (trash.empty()) return ++sz; int tmp=trash.front(); trash.pop(); return tmp;}

    inline void Del(int x) {trash.push(x);}

    inline int GetP(int rk) {for (int i=start; ~i; i=B[i].next) if (rk>B[i].size) rk-=B[i].size; else return i;}

    inline int GetK(int rk) {for (int i=start; ~i; i=B[i].next) if (rk>B[i].size) rk-=B[i].size; else return rk;}

    inline void Data(int pos,int len,char data[],int suf) {B[pos].next=suf; B[pos].size=len; memcpy(B[pos].data,data,len);}

    inline void Split(int pos,int rk)

    {

        if (B[pos].size==rk) return;

        int id=New(); Data(id,B[pos].size-rk,B[pos].data+rk,B[pos].next); B[pos].next=id; B[pos].size=rk;

    }

    inline void Merge(int pos)

    {

        for ( ; ~pos; pos=B[pos].next)

            for (int suf=B[pos].next; ~suf && B[pos].size+B[suf].size<Bsize; suf=B[suf].next)

                memcpy(B[pos].data+B[pos].size,B[suf].data,B[suf].size),B[pos].size+=B[suf].size,B[pos].next=B[suf].next,Del(suf);

    }

    inline void Insert(int s,int len)

    {

        int now=GetP(s),pos=GetK(s),l,id;  Split(now,pos);

        for (l=; l+Bsize<=len; l+=Bsize)

            id=New(),Data(id,Bsize,S+l,B[now].next),B[now].next=id,now=id;

        if (l<len) id=New(),Data(id,len-l,S+l,B[now].next),B[now].next=id;

        Merge(now);

    }

    inline void Delete(int s,int len)

    {

        int now=GetP(s),pos=GetK(s),p;  Split(now,pos);

        for (p=B[now].next; ~p; p=B[p].next) if (len>B[p].size) len-=B[p].size; else break;

        Split(p,len); p=B[p].next;

        for (int i=B[now].next; i!=p && ~i; i=B[now].next) B[now].next=B[i].next,Del(i);

        Merge(now);

    }

    inline void GetAns(int s,int len)

    {

        int now=GetP(s),pos=GetK(s),p,l;  l=min(len,B[now].size-pos);

        memcpy(S,B[now].data+pos,l);

        for (p=B[now].next; ~p && l+B[p].size<=len; p=B[p].next)

            memcpy(S+l,B[p].data,B[p].size),l+=B[p].size;

        if (l<len && ~p) memcpy(S+l,B[p].data,len-l);

        S[len]=; puts(S);

    }

    inline void Init() {start=,B[].size=,B[].next=-;}

}

using namespace BlockLists;

inline void GetS(int len) {int l=-; while (l<len-) {S[++l]=getchar(); if (S[l]< || S[l]>) l--;}}

int main()

{

//    freopen("editor2003.in","r",stdin);

//    freopen("editor2003.out","w",stdout);

    int T=read();

    BlockLists::Init();

    while (T--)

        {

            char opt[]; scanf("%s",opt); int x;

            switch (opt[])

                {

                    case 'M': loc=read(); break;

                    case 'I': x=read();  GetS(x); BlockLists::Insert(loc,x); break;

                    case 'D': x=read(); BlockLists::Delete(loc,x); break;

                    case 'G': x=read(); BlockLists::GetAns(loc,x); break;

                    case 'P': loc--; break;

                    case 'N': loc++; break;

                }

        }

    return ;

}

说起来太容易了，

昨晚接近3个小时手写模板，然后各种问题...最后还是借鉴了    将狼踩尽    大神的模板

相关文章