记录编号	119939	评测结果	WWWWWWWEEW
题目名称	[NOI 2003]文本编辑器	最终得分	0
用户昵称	HouJikan	是否通过	未通过
代码语言	C++	运行时间	2.435 s
提交时间	2014-09-14 20:32:56	内存使用	19.39 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct node
{
  node *lc,*rc;
  int s;
  char ch;
  node ()
  {
    lc=rc=NULL;
    s=1;
  }
};
//==============var declaration=================
node *root=NULL;
node *head=new node;
int cursor=0,sumlen=0;
char ins[20000001];
string cmd;
int top;
//==============function declaration============
void update(node *&p);
void rrotate(node *&p);
void lrotate(node *&p);
void find(int x,node *&p);
node *built(char *c,int l,int r);//[l,r)
void show(node *p,int &x);
//==============main code=======================
int main()
{  
  string FileName="editor2003";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
#endif  
  int q;
  head->rc=root;
  cin>>q;
  char c;
  int len,pos;
  node *left,*mid,*right;
  while(q--)
  {
    cin>>cmd;
    if (cmd[0]=='I')
    {
      top=0;
      cin>>len;
      sumlen+=len;
      while (top<len)
      {
        scanf("%c",&c);
        if(c!='\n')
          ins[top++]=c;
      }
      mid=built(ins,0,top);
      if (cursor!=0)
      {
        find(cursor,root);
        find(mid->s,mid);
        mid->rc=root->rc;
        root->rc=mid;
      }
      else
      {
        find(1,root);
        find(len,mid);
        mid->rc=root;
        root=mid;
      }
      update(root);
    }
    else if(cmd[0]=='M')
    {
      cin>>cursor;
      if (cursor==0)
        find(1,root);
      else 
        find(cursor,root);
    }
    else if (cmd[0]=='P')
    {
      cursor--;
      if (cursor==0)
        find(1,root);
      else 
        find(cursor,root);
    }
    else if (cmd[0]=='N')
    {
      cursor++;
      find(cursor,root);
    }
    else if (cmd[0]=='D')
    {
     cin>>len;
      sumlen-=len;
      if (cursor==0)
      {
        find(len+1,root);
        root->lc=NULL;
        update(root);
      }
      else
      {
        find(cursor+1,root);
        left=root->lc;
        if (cursor+len+1<=sumlen)
        {
          find(cursor+len+1,root);
          find(left->s,left);
          left->rc=root;
          root->lc=NULL;
          root=left;
        }
        else
          root=left;
        update(root);
      }
    }
    else if (cmd[0]=='G')
    {
      cin>>len;
      if (cursor==0)
      {
        find(1,root);
        show(root,len);
      }
      else
      {
        find(cursor,root);
        show(root->rc,len);
      }  
      printf("\n");
    }
  }
  return 0;
}
//================fuction code====================
void update(node *&p)
{
  p->s=1;
  if (p->lc!=NULL) 
    p->s+=p->lc->s;
  if (p->rc!=NULL)
    p->s+=p->rc->s;
}
void rrotate(node *&p)
{
  if (p->rc==NULL) return;
  node *o=p->rc;
  p->rc=o->lc;
  o->lc=p;
  p=o;
  update(p->lc);
  update(p);
}
void lrotate(node *&p)
{
  if (p->lc==NULL) return;
  node *o=p->lc;
  p->lc=o->rc;
  o->rc=p;
  p=o;
  update(p->rc);
  update(p);
}
void find(int x,node *&p)
{
  if (p==NULL)
    return;
  int ls,rs;
  if (p->lc==NULL) 
    ls=0;
  else
    ls=p->lc->s;
  if (p->rc==NULL) 
    rs=0;
  else
    rs=p->rc->s;
  if (ls+1==x)
    return;
  if (ls>=x)
  {
    find(x,p->lc);
    lrotate(p);
  }
  if (ls<x)
  {
    find(x-ls-1,p->rc);
    rrotate(p);
  }
  return ;
}
node *built(char *c,int l,int r)
{
  if (l>=r)
    return NULL;
  int m=(l+r)/2;
  node *p=new(node);
  p->ch=c[m];
  p->lc=built(c,l,m);
  p->rc=built(c,m+1,r);
  update(p);
  return p;
}
void show(node *p,int &x)
{
  if (p==NULL||x<=0)
    return;
  if (p->lc!=NULL)
    show(p->lc,x);
  if (x<=0)
    return;
  x--;
  pritnf("%c",p->ch);
  if (p->rc!=NULL)
    show(p->rc,x);
  return;
}