题解 P4008 【[NOI2003]editor文本编辑器】

attack · 2017-12-17 18:07:13 · 题解

作为题目提供者，先来水一发题解

本题可以说是平衡树的裸题，随便打打标记就能过了

不过在此提供一种块状链表的做法

块状链表，就是数组和链表的结合体

他的思想是对于每一个链表中的节点，都保存一个数组

剩下的就是暴力咯

时间复杂度:\sqrt{n}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=2000000+10;
const int BlockSize=3000 + 100,BlockNum=3000 + 10;
int Cur=0,head,tot;
char str[MAXN];
struct Block
{
    int size,nxt;
    bool rev;
    char a[BlockSize];
    void Clear()
    {
        size=0;nxt=-1,rev=0;
    }
}B[BlockNum];
queue<int>q;//鐢ㄤ竴涓?槦鍒楁潵缁存姢褰撳墠鏈夊摢浜涘潡
int NewNode()
{
    int t=q.front();q.pop();
    B[t].Clear();
    return t;
}
inline void Pre()
{
    while(q.size()!=0)    q.pop();
    for(int i=0;i<BlockNum;i++) q.push(i);
    head = NewNode();
}
void Find(int &idx,int &cur)
{
    while(idx!=-1&&cur>B[idx].size) cur-=B[idx].size,idx=B[idx].nxt;
}
void Pushdown(int idx)
{
    if(B[idx].rev) 
    {
    //    for(int i=0;i<B[idx].size;i++)
    //        cout<<B[idx].a[i];cout<<endl;
        reverse(B[idx].a,B[idx].a+B[idx].size);
    //    for(int i=0;i<B[idx].size;i++)
    //        cout<<B[idx].a[i];cout<<endl;
        B[idx].rev=0;
    }
}
inline void Split(int idx,int cur)
{
    if(idx==-1||cur==B[idx].size)    return ;
    Pushdown(idx);
    int tot=NewNode();
    memcpy(B[tot].a,B[idx].a+cur,sizeof(char) * (B[idx].size-cur) );
    B[tot].size=B[idx].size-cur;
    B[idx].size=cur;
    B[tot].nxt=B[idx].nxt;
    B[idx].nxt=tot;
}
void Delet(int idx)
{
    q.push(idx);
}
void Merge(int idx)
{
    for(int i=idx;i!=-1;i=B[i].nxt)
        for(int j=B[i].nxt;j!=-1;j=B[j].nxt)
        {
            if(B[i].size+B[j].size<=BlockSize)
            {
                Pushdown(i);
                Pushdown(j);
                memcpy(B[i].a+B[i].size,B[j].a,sizeof(char) * B[j].size);
                B[i].size+=B[j].size;B[i].nxt=B[j].nxt;
                Delet(j);
            }
            else break;
        }
}
inline void Insert(int cur,int x,char *str)
{
    int idx=head;
    Find(idx,cur);
    Split(idx,cur);
    int i=0;//宸茬粡鍔犲叆鐨勪釜鏁?
    while(i<x)
    {
        int Limit=min(BlockSize,x-i);
        int tot=NewNode();
        memcpy(B[tot].a,str+i,sizeof(char) * Limit);
        B[tot].size=Limit;
        B[tot].nxt=B[idx].nxt;
        B[idx].nxt=tot;
        idx=B[idx].nxt;
        i+=Limit;
    }
    Merge(head);
}
void Print(int k, int n, char *str)
{
    int idx = head;
    Find(idx, k);
    int len = 0;
    for(int i = idx; i != -1 && n > 0; i = B[i].nxt)
    {
        Pushdown(i);
        int Limit = min(n, B[i].size - k);
        memcpy(str + len, B[i].a + k, sizeof(char) * Limit);
        len += Limit, n -= Limit;
        k = 0;
    }
    str[len] = '\0';
    puts(str);
}
void Rever(int l,int r)
{
    int idx=head;
    Find(idx,l);
    Split(idx,l);
    int Start=idx,StartNxt=B[idx].nxt;
    idx=head;
    Find(idx,r);
    Split(idx,r);
    int EndNxt=B[idx].nxt;
    int Tmp[BlockNum],cnt=0;
    for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)
        B[i].rev^=1,Tmp[++cnt]=i;
    Tmp[++cnt]=Start;Tmp[0]=EndNxt;
    for(int i=cnt;i>=1;i--)
        B[Tmp[i]].nxt=Tmp[i-1];
    Merge(head);
}
void Dele(int l,int r)
{
    int idx=head;
    Find(idx,l);
    Split(idx,l);
    int Start=idx,StartNxt=B[idx].nxt;
    idx=head;
    Find(idx,r);
    Split(idx,r);
    int EndNxt=B[idx].nxt;
    for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)    Delet(i);
    B[Start].nxt=EndNxt;
    Merge(head);
}
int main()  
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int N;scanf("%d",&N);
    char opt[20];
    Pre();
    while(N--)
    {
        scanf("%s",opt);
        if(opt[0]=='M') 
            scanf("%d",&Cur);
        else if(opt[0]=='I')
        {
            int len;
            scanf("%d", &len);
            int i = 0;
            while(i < len) {char ch = getchar();if(ch >= 32 && ch <= 126) str[i++] = ch;}
            str[i++]='\0';
            Insert(Cur,len,str);
        }
        else if(opt[0]=='D')
        {
            int x;
            scanf("%d",&x);
            Dele(Cur,Cur+x);
        }
        else if(opt[0]=='R')
        {
            int x;
            scanf("%d",&x);
            Rever(Cur,x+Cur);
        }
        else if(opt[0]=='G')    
        {
            int x;
            scanf("%d",&x);
            Print(Cur,x,str);
        }
        else if(opt[0]=='P')    Cur--;
        else if(opt[0]=='N')    Cur++;
    }
    return 0;
}