3223:Tyvj 1729文芸バランスツリー

3223:Tyvj 1729文芸バランスツリー
Time Limit: 10 Sec  
メモリLimit: 128 MB
Submit: 2466  
Solved: 1380
[Submit][Sttus][Dispacs]
Description
データ構造(件名参照可能)を書いて、順序正しい数列を維持する必要があります.ここでは、次のような動作を提供します. 4 3 2 1,反転区間が[2,4]だったら、結果は5です. 2 3 4 1 
Input
第一行為n,m nは初期シーケンスにn個の数があることを示し、このシーケンスは順次(1,2…n−1,n)である.  mは反転操作回数を表します.次に、m行の各行数[l,r] データ保証 1<=l<=r==n 
Output
 
一行n個の数字を出力して、元のシーケンスがm回変換された後の結果を表します. 
Sample Input
5 3 1 3 1 3 1 3 1 4
Sample Output
4 3 2 1 5
HINT
N、M<=100000
ソurce
バランスツリー
[Submit][Sttus][Dispacs]
splayは区間問題を解決します.
操作のたびにl-1をルートr+1に変えて、ルートの右の息子に変えます.このようにr+1の左の息子は[l,r]です.そしてマークします.
マークはxorで操作する必要があります.反転が可逆的ですから.
そして挿入するたびに、新しく挿入された点をルートに移動します.

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

const int maxn = 1E5 + 10;

int n,m,ans[maxn];

class data{
	private:
		struct Node{
			Node *ch[2];
			int num,mark,siz;
		}*root,*tot,pool[maxn];
		
		void maintain(Node *&x) {
			int s0 = (x->ch[0] == NULL)?0:x->ch[0]->siz;
			int s1 = (x->ch[1] == NULL)?0:x->ch[1]->siz;
			x->siz = s0+s1+1;
		}
		
		void rotate(Node *&x,int d) {
			Node *y = x->ch[d]; //y->fa = x->fa; 
			x->ch[d] = y->ch[d^1]; //y->ch[d^1]->fa = x;
			y->ch[d^1] = x; //x->fa = y;
			maintain(x); 
			x = y; 
			maintain(x);
		}
		
		int Insert(Node *&x,int num) {
			int ret = 0;
			if (x == NULL) {
				x = ++tot;
				x->ch[0] = x->ch[1] = NULL;
				x->num = num; x->siz = 1;
				x->mark = 0; return 1;
			}
			
			int d = (x->num > num)?0:1;
			int s0 = (x->ch[0] == NULL)?0:x->ch[0]->siz;
			ret = s0+1;
			int sum = Insert(x->ch[d],num);
			//x->ch[d]->fa = x;
			maintain(x);
			return ret + sum;
		}
		
		void pushdown(Node *&x) {
			if (x->mark) {
				swap(x->ch[0],x->ch[1]);
				if (x->ch[0] != NULL) x->ch[0]->mark ^= 1;
				if (x->ch[1] != NULL) x->ch[1]->mark ^= 1;
				x->mark = 0;
			}
		}
		
		/*Node* find(Node *x,int rank) {
			pushdown(x);
			int s0 = (x->ch[0] == NULL)?0:x->ch[0]->siz;
			if (s0+1 == rank) return x;
			else if (s0+1 > rank) return find(x->ch[0],rank);
			else return find(x->ch[1],rank-s0-1);
		}*/
		
		void splay(Node *&x,int rank) {
			pushdown(x);
			int s0 = (x->ch[0] == NULL)?0:x->ch[0]->siz;
			if (s0+1 != rank) {
				int d;
				if (s0+1 >= rank) d = 0;
				else d = 1,rank = rank - s0 - 1;
				pushdown(x->ch[d]);
				int s1 = (x->ch[d]->ch[0] == NULL)?0:x->ch[d]->ch[0]->siz;
				if (s1+1 != rank) {
					int d2;
					if (s1+1 >= rank) d2 = 0;
					else d2 = 1,rank = rank - s1 - 1;
					splay(x->ch[d]->ch[d2],rank);
					if (d == d2) rotate(x,d);
					else rotate(x->ch[d],d2);
				}
				rotate(x,d); 
			}
		}
		
		void DFS(Node *x,int sum) {
			pushdown(x);
			int s0 = (x->ch[0] == NULL)?0:x->ch[0]->siz;
			ans[s0+1+sum] = x->num;
			if (x->ch[0] != NULL) DFS(x->ch[0],sum);
			if (x->ch[1] != NULL) DFS(x->ch[1],sum+s0+1);
		}
		
	public:
		data() {
			root = NULL;
			tot = pool;
		}
		
		int Ins(int num) {
			return Insert(root,num);
		}
		
		void setmark() {
			//pushdown(root);
			//pushdown(root->ch[1]);
			root->ch[1]->ch[0]->mark ^= 1;
		}

		void spl(int rank,int typ) {
			if (!typ) splay(root,rank);
			else {
				pushdown(root);
				int s0 = (root->ch[0] == NULL)?0:root->ch[0]->siz;
				splay(root->ch[1],rank-s0-1);
			}
		}
		
		void dfs() { 
			DFS(root,0);
		}
};

int main()
{
	#ifdef YZY
		   freopen("yzy.txt","r",stdin);
	#endif
	
	static data tree;
	cin >> n >> m;
	for (int i = 0; i <= n+1; i++) 
		tree.spl(tree.Ins(i),0);
	//tree.dfs();
	
	while (m--) {
		int l,r;
		scanf("%d%d",&l,&r);
		tree.spl(l,0); 
		tree.spl(r+2,1);
		tree.setmark();
		//tree.dfs();
	}
	
	tree.dfs();
	for (int i = 2; i <= n+1; i++) {
		printf("%d ",ans[i]);
	}
	
	return 0;
}