[AHOI2006] 텍스트 편집기 편집기 BZOIJ 1269

제목의 뜻은 특징이 없고 의미가 뚜렷하다. 바로 테스트 템플릿이다.
내 거푸집, 정말 썩어 터졌어!!!!그런데 쓸 수 있어, 겨우 쓸 수 있지...왜 이렇게 느린지 모르겠어. 내가 삽입할 때 게으름 피우면서 체인 하나로 꽂았나 봐.(어차피 splay가 알아서 조정할 거면서...이론 실천은 TLE를 못해야지~~~~)

#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;

const int maxint=~0U>>1;

/*
splay，             
*/

struct mark
{
	bool reverse; //               
	/*
	bool b;
	bool a;
	  a,b           ，         ，         ，     
	*/
	mark()
	{
		reverse=0;
	}
	//1      0    
};
vector<int>outputnum;

/*
splay     
*/
struct node
{
	int key;
	int size;
	mark cd;

	node *c[2];
	node():key(0),size(0){c[0]=c[1]=this;}
	node(int key_,node* c0_,node* c1_):
	key(key_){c[0]=c0_;c[1]=c1_;}
	node* rz(){return size=c[0]->size+c[1]->size+1,this;}
} Tnull,*null=&Tnull;

struct splay
{
	node *root;
	splay() /*             */
	{
		root=(new node(*null))->rz();
		root->key=maxint;
	}	



	/* k     ，   k       ，  ，       ，    
	 *         。  【        ！】
	 * do_reversal     ，  node           
	*/
	void do_reversal(node* k)
	{
		if (k -> cd.reverse)//          
		{
			k -> cd.reverse = 0; //       ，    ，    
			swap(k -> c[0], k -> c[1]);//      
			if (k -> c[0] != null)	k -> c[0] -> cd.reverse ^= 1;
			if (k -> c[1] != null) 	k -> c[1] -> cd.reverse ^= 1;
		}
	}


	/*
	 *        ，    2 
	*/
	void check()
	{
		do_reversal(root);//        ，         ,do_reversal               
		//    ，              
		if (root -> c[0] != null)	do_reversal(root -> c[0]);
		if (root -> c[1] != null)	do_reversal(root -> c[1]);
	}

	//zig,zigzig,finish,select  ，   key  ，        
	void zig(bool d)
	{
		node *t=root->c[d];
		root->c[d]=null->c[d];
		null->c[d]=root;
		root=t;
	} 
	void zigzig(bool d)
	{
		node *t=root->c[d]->c[d];
		root->c[d]->c[d]=null->c[d];
		null->c[d]=root->c[d];
		root->c[d]=null->c[d]->c[!d];
		null->c[d]->c[!d]=root->rz();
		root=t;
	}
	void finish(bool d)
	{
		node *t=null->c[d],*p=root->c[!d];
		while(t!=null)
		{
			t=null->c[d]->c[d];
			null->c[d]->c[d]=p;
			p=null->c[d]->rz();
			null->c[d]=t;
		}
		root->c[!d]=p;
	}
	void select(int k) // k+1       ,    k          
	{
		int t;
		while(1)
		{
			check();
			bool d=k>(t=root->c[0]->size);
			if(k==t||root->c[d]==null)break;
			if(d)k-=t+1;
			bool dd=k>(t=root->c[d]->c[0]->size);
			if(k==t||root->c[d]->c[dd]==null){zig(d);break;}
			if(dd)k-=t+1;
			d!=dd?zig(d),zig(dd):zigzig(d);
		}
		finish(0),finish(1);
		root->rz();//      size
	}




	/*
		pg(node k);
		     ，        ，size，     
		       pg(*root)   
	*/
	void pg(node k)//     

	{
		cout<<k.key<<" [left son:";
		if (k.c[0] != null)	cout<<k.c[0] -> key;
		else cout<<"none";
		cout<<"]  [right son:";

		if (k.c[1] != null)	cout<< k.c[1] -> key;
		else cout<<"none";
		cout<<"]     [size =";
		cout<<k.size<<"]" <<"   ？"<<" "<<k.cd.reverse<<"
";
		if (k.c[0] != null)	pg(*k.c[0]);
		if (k.c[1] != null)	pg(*k.c[1]);
	}



	/*
	 *           ,  -maxint, +maxin
	 *          zhongxu(root)
	*/
	void zhongxu(node* k)
	{
		do_reversal(k);//        
		if (k -> c[0] != null)	do_reversal(k -> c[0]);
		if (k -> c[1] != null)	do_reversal(k -> c[1]);
		if (k -> c[0] != null)	zhongxu(k -> c[0]);
		cout<<(char)k -> key<<" ";
		if (k -> c[1] != null)	zhongxu(k -> c[1]);			
	}


	//	vector<int>outputnum;    
	//	              outputnum
	void get_output_info(node* k)
	{
		do_reversal(k);//        
		if (k -> c[0] != null)	do_reversal(k -> c[0]);
		if (k -> c[1] != null)	do_reversal(k -> c[1]);
		if (k -> c[0] != null)	get_output_info(k -> c[0]);
		outputnum.push_back(k -> key);
		if (k -> c[1] != null)	get_output_info(k -> c[1]);			
	}
	void output()//      ，  -max +max
	{
		outputnum.clear();
		get_output_info(root);
		for (int i = 1; i != outputnum.size() - 2; ++ i)	printf("%d ", outputnum[i]);
		printf("%d
", outputnum[outputnum.size() - 2]);
	}

	void output(int left, int right)
		// (left right)       
	{
		outputnum.clear();
		transformation(left, right);
		get_output_info(root -> c[1] -> c[0]);
		//cout<<outputnum.size()<<endl;
		for (int i = 0; i != outputnum.size() - 1; ++ i)	printf("%d ", outputnum[i]);
		printf("%c
", outputnum[outputnum.size() - 1]);		
	}

	///////////////////////////////////////



	node* init(int x[], int n)//       ,  n   ，   1     
	{
		//      ，             -maxint    
		root -> c[0] = (new node(-maxint, null, null)) -> rz();//          
		root -> rz();
		for (int i = 1; i <= n; ++ i)
		{
			transformation(i, i + 1);
			root -> c[1] -> c[0] = (new node(x[i], null, null)) -> rz();
			root -> c[1] -> rz();
			root -> rz();
		}
		return root;
	}
	node* init_no_maxint(int x[], int n)//  ，     -maxint， max    ，        
	{
		root -> c[0] = (new node(x[1], null, null)) -> rz();//          
		root -> rz();
		for (int i = 2; i <= n; ++ i)
		{
			transformation(i - 1, i);
			root -> c[1] -> c[0] = (new node(x[i], null, null)) -> rz();
			root -> c[1] -> rz();
			root -> rz();
		}	
		transformation(n, n + 1);
		delete root -> c[1];
		root -> c[1] = null;
		return root -> rz();
	}


	/*
	 * clear()        splay        
	*/
	void dfs_clear(node *k)
	{
		if (k -> c[0] != null)
		{
			dfs_clear(k -> c[0]);
			delete (k -> c[0]);
		}
		if (k -> c[1] != null)
		{
			dfs_clear(k -> c[1]);
			delete k -> c[1];
		}
	}
	node* clear() //     ，     maxint   
	{
		int allsize = root -> size;
		select(allsize - 1);
		dfs_clear(root);
		root -> c[0] = root -> c[1] = null;
		return root;
	}

	/*
	 *   left       ，right      
	 *        [left+1,right-1]
	 *   ，    -maxint, maxint 2   
	*/
	node* transformation(int left, int right)
	{
		select(left - 1);
		node *oldroot = root;
		root = root -> c[1];
		select(right -left - 1);
		node *t = root;
		root = oldroot;
		root -> c[1] = t;
		return root -> rz();
	}


	/*
	 *  [left+1, right -1]       
	*/
	node* reversal(int left, int right) // (left,right)     ，   left,right
	{
		transformation(left, right);
		root -> c[1] -> c[0] -> cd.reverse ^= 1;
		return root;
	}
	int sel(int k){return select(k-1),root->key;} // k    
} sp;


struct interval//        splay
{
	splay core;//     -max,   max

	inline int size()
	{
		return core.root -> size - 2;
	}

	inline void output()
	{
		core.output();
	}

	void output(int left, int right)//  left  right     
	{
		right += 2;
		core.output(left, right);
	}


	inline void clear()
	{
		core.clear();
	}

	inline void init(int x[], int n)//   ， core    
		//   1  ，  n   ！
	{
		core.init(x, n);
	}


	/*
	 *  left   ，  right   ，    
	*/
	void daozhuan(int left, int right) 
	{
		right += 2;
		core.reversal(left, right);
	}


	/*
	 *           ,  ，              ！
	*/
	void output_all_element()
	{
		core.zhongxu(core.root);
		cout<<endl;
	}
	

	node* delete_qujian(int left, int right)
	{
		right += 2;
		core.transformation(left, right);
		node *ret = core.root -> c[1] -> c[0];
		core.root -> c[1] -> c[0] = null;
		core.root -> c[1] -> rz();
		core.root -> rz();
		return ret;
	}

	void insert_node(node *newinter, int k)//   [1,k],[k+1,n]    
	{
		++k; //    -max   ，          
		core.transformation(k, k + 1);
		core.root -> c[1] -> c[0] = newinter;
	}

	/*
	 *   k       n   ，n      x[1..n] 。    1  
	*/
	void insert(int x[], int n, int k)
	{
		splay tmp;
		node *tmproot = tmp.init_no_maxint(x, n);
		insert_node(tmproot, k);
	}
}qujian;

int x[2000000];

int main()
{
	int t, guangbiao=0;
	scanf("%d", &t);
	char s[100], ch;
	qujian.init(x,0);
	while (t--)
	{
		scanf("%s", s);
		if (strcmp(s, "Insert") == 0)
		{
			int n;
			scanf("%d", &n);
			getchar();
			for (int i = 1; i <= n; ++ i)	
			{
				ch = getchar();
				x[i] = ch;
			}
			qujian.insert(x, n, guangbiao);
		}
		if (strcmp(s, "Move") == 0)
		{
			scanf("%d", &guangbiao);
		}
		if (strcmp(s, "Delete") == 0)
		{
			int n;
			scanf("%d", &n);
			qujian.delete_qujian(guangbiao + 1, guangbiao + n);
		}
		if (strcmp(s, "Rotate") == 0)
		{
			int n;
			scanf("%d", &n);
			qujian.daozhuan(guangbiao + 1, guangbiao + n);
		}
		if (strcmp(s, "Get") == 0)
		{
			qujian.output(guangbiao + 1, guangbiao + 1);
		}
		if (strcmp(s, "Prev") == 0)
		{
			--guangbiao;
		}
		if (strcmp(s, "Next") == 0)
		{
			++guangbiao;
		}
	}
	return 0;
}
/*
10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
editor
Move 0
Get
Move 11
Rotate 4
Get

*/