Tag Archives: 块状链表

BZOJ 1507([NOI2003]Editor-块状链表)

Posted on by

1507: [NOI2003]Editor

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 922  Solved: 323
[Submit][Status][Discuss]

Description

很久很久以前，DOS3.x 的程序员们开始对 EDLIN 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器……
多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试）！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？
为了明确任务目标，小明对“文本编辑器”做了一个抽象的定义：
文本：由 0 个或多个字符构成的序列。这些字符的 ASCII 码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。
光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。
文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下六条操作的程序。
如果这段文本为空，我们就说这个文本编辑器是空的。

你的任务是：
 建立一个空的文本编辑器。
 从输入文件中读入一些操作指令并执行。
 对所有执行过的 GET 操作，将指定的内容写入输出文件。

Input

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

Output

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

Sample Input

15

Insert 26

abcdefghijklmnop

qrstuv wxy

Move 16

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

这题我是用块状链表做的

块状链表的复杂度大约是O（√n）

一定要尽可能将块分成长度为√tot的，balance()时要把所有的长度分为介于1/2√tot-2√tot之间

另外merge时要注意先把cur移动再重载合并格的长度（不容易查出错,不知为何,加错也能过8个点）

要参考老董的讲解与nocow的模板

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cmath>
using namespace std;
#define MAXP (1024*1024)
#define MAXN (2900)
struct block
{
    int n;
    char a[MAXN];
    block *next,*pre;
    block():n(0){next=pre=NULL;}
}*first;
block* q[MAXN];
int size=0,tot=0;
void del(block *x)
{
    q[++size]=x;
    if (x->pre) x->pre->next=x->next;
    if (x->next) x->next->pre=x->pre;
    if (x==first) first=x->next;
}
block *newblock()
{
    if (size) return q[size--];
    block *x=new block();
    return x;
}
void link(block *a,block *b)
{
    if (a) a->next=b;
    if (b) b->pre=a;
}
void spilt(block *x,int nowsize)
{
    if (!nowsize||nowsize==x->n) return;
    block *tmp=x->next;
    x->next=newblock();
    block *x2=x->next;
    x2->n=x->n-nowsize;
    for (int i=1;i<=x2->n;i++) x2->a[i]=x->a[nowsize+i];
    x->n=nowsize;
    link(x2,tmp);
    link(x,x2);
}
struct cursor
{
    int n;
    block *ll;
    cursor():n(0){ll=first; }
    void pre()
    {
        n--;
        if (n<0)
        {
            ll=ll->pre;
            n=ll->n-1;
        }
    }
    void next()
    {
        n++;
        if (n>ll->n)
        {
            ll=ll->next;
            n=1;
        }
    }
    void move(int k)
    {
        n=k,ll=first;
        while (n>ll->n)
        {
            n-=ll->n;
            ll=ll->next;
        }
    }
}cur;
void get(cursor cur,int k)
{
    int p=cur.ll->n-cur.n;
    if (p>=k)
    {
        for (int i=cur.n+1;i<=cur.n+k;i++)
            printf("%c",cur.ll->a[i]);
    }
    else
    {
        for (int i=cur.n+1;i<=cur.ll->n;i++) printf("%c",cur.ll->a[i]);
        cur.ll=cur.ll->next;cur.n=0;
        get(cur,k-p);
    }
}
void merge(block *x)
{
    if (!x->next) return;
    for (int i=1;i<=x->next->n;i++) x->a[x->n+i]=x->next->a[i];
    if (cur.ll==x->next)
    {
        cur.ll=x;
        cur.n+=x->n;
    }
    x->n+=x->next->n;
    del(x->next);
}
void balance()
{
    int maxsize=min(MAXN,(int)sqrt(tot)*2);
    int minsize=(int)sqrt(tot)/2;
    block *x=first;
    while (x)
    {
        while (x->n<minsize||x->n>maxsize)
        {
            if (x->n<minsize)
            {
                merge(x);
                if (!x->next) break;
            //  get(cur,1);
            }
            else
            {
                spilt(x,(x->n)>>1);
                if (cur.ll==x&&cur.n>cur.ll->n)
                {
                    cur.n-=cur.ll->n;
                    cur.ll=cur.ll->next;
                }
            //  get(cur,1);
            }
        }
        x=x->next;
    }
}
void delet(int k)
{
    if (!k) return;
    if (cur.n)
    {
        spilt(cur.ll,cur.n);
        cur.ll=cur.ll->next; cur.n=0;
    }
    while (k>cur.ll->n)
    {
        del(cur.ll);
        k-=cur.ll->n;
        cur.ll=cur.ll->next;
    //  cur.n=0;
    }
    if (k==cur.ll->n)
    {
        cur.ll->n=0;
    }
    else
    {
        spilt (cur.ll,k);
        delet(k);
    }
    balance();
}
void insert(int k)
{
    block *l=newblock();*l=block();
    block *r=l;
    int maxsize=min(MAXN,(int)sqrt(tot));
    for (int i=1;i<=k;i++)
    {
        char c;
        for (scanf("%c",&c);(c<32)||(c>126)||(c=='n');scanf("%c",&c));
        if (r->n>maxsize)
        {
            block *tmp=r;
            r=newblock();*r=block();link(tmp,r);
        }
        r->a[++r->n]=c;
    }
    if (cur.n)
    {
        spilt(cur.ll,cur.n);
        block *tmp=cur.ll->next;
        link(cur.ll,l),link(r,tmp);
    }
    else
    {
        link(cur.ll->pre,l),link(r,cur.ll),cur.ll=l;
        if (first->pre) first=l;
    }
    balance();
}
int main()
{
    first=newblock();cur.ll=first;
    int t;scanf("%d",&t);
    while (t--)
    {
        char s[10];
        scanf("%s",s);
        int k;
        switch(s[0])
        {
            case'M':scanf("%d",&k);cur.move(k);break;
            case'I':scanf("%d",&k);tot+=k;insert(k);break;
            case'D':scanf("%d",&k);tot-=k;delet(k);break;
            case'G':scanf("%d",&k);get(cur,k);printf("n");break;
            case'P':cur.pre();break;
            case'N':cur.next();break;
        }
//      get(cursor(),tot);cout<<endl;
    }
    return 0;
}