记录编号	429900	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	ZlycerQan	是否通过	通过
代码语言	C++	运行时间	3.088 s
提交时间	2017-07-28 18:17:09	内存使用	30.83 MiB

/*
	LibreOJ #106. 二逼平衡树
 
	写了整整一下午
	1遍AC
	感人肺腑啊。。。
	
	我的做法比较中规中矩
	
	线段树套splay
	对于操作1没什么好说， 在线段树查询区间时查出排名
	
	对于操作2， 一开始没想太多
	在写完基础函数时突然意识到不好做
	在想不出好办法后看了题解， 得知了要用二分
	二分一下这个数， 二分出一个答案查排名
	然后找前驱即可
	
	操作3要在splay中删除再插入即可
	操作4， 5没什么可说的。。。。。。
	
	这个写法不太好。。
	既然封装了。。。就要考虑一下充分利用封装的好处啊。。 
	 
*/
#include <cstdio>
 
#define Max 4000005
#define INF 1e9
 
#define Inline __attri\
bute__( ( optimize( "-O2" ) ) )

Inline void read (int &now)
{
	register char word = getchar ();
	bool temp = false;
	for (now = 0; word < '0' || word > '9'; word = getchar ())
		if (word == '-')
			temp = true;
	for (; word >= '0' && word <= '9'; now = now * 10 + word - '0', word = getchar ());
	if (temp)
		now = -now;
}
 
int data[Max];
 
struct S_D 
{
	S_D *child[2], *father;
	
	int size, weigth;
	int key;
	
	S_D ()
	{
		this->child[0] = this->child[1] = NULL;
		this->father = NULL;
		
		this->size = this->weigth = 1;
		this->key = 0;
	}
	
	void Clear ()
	{
		this->child[0] = this->child[1] = NULL;
		this->father = NULL;
	}
	
	int Get_Pos ()
	{
		return this->father->child[1] == this;
	}
	
	Inline void Updata ()
	{
		this->size = this->weigth;
		
		if (this->child[0])
			this->size += this->child[0]->size;
		if (this->child[1])
			this->size += this->child[1]->size;
	}
};
 
int Maxn = -INF;
 
Inline int max (int a, int b)
{
	return a > b ? a : b;
}
 
Inline int min (int a, int b)
{
	return a < b ? a : b;
}
 
struct X_D
{
	X_D *Left, *Right;
	
	int l, r;
	int Mid;
	
	X_D (int __l, int __r) : l (__l), r (__r)
	{
		Left = Right = NULL;
		Mid = __l + __r >> 1;
	}
};
 
int Answer;
 
class Splay_Tree_Type
{
	
	private :
		
		S_D *root[Max];
		
		Inline void Rotate (S_D *now)
		{
			S_D *Father = now->father;
			int pos = now->Get_Pos () ^ 1;
			
			Father->child[pos ^ 1] = now->child[pos];
			if (now->child[pos])
				now->child[pos]->father = Father;
			if ((now->father = Father->father) != NULL)
				now->father->child[now->father->child[1] == Father] = now;
				
			Father->father = now;
			now->child[pos] = Father;
			
			Father->Updata ();
			now->Updata ();
		}
		
		Inline void Splay (S_D *now)
		{
			for (S_D *Father; Father = now->father; this->Rotate (now))
				if (Father->father)
					this->Rotate (now->Get_Pos () == Father->Get_Pos () ? Father : now);
		}
		
	public :
		
		void Insert (int pos, int x)
		{
			if (root[pos] == NULL)
			{
				root[pos] = new S_D ;
				root[pos]->key = x;
				return ;
			}
			S_D *now = root[pos], *Father;
			
			for (; ; Father = now, now = now->child[x > now->key])
			{
				if (now == NULL)
				{
					now = new S_D;
					now->father = Father;
					now->key = x;
					Father->child[x > Father->key] = now;
					this->Splay (now);
					root[pos] = now;
					return ;
				}
				if (now->key == x)
				{
					now->weigth ++;
					this->Splay (now);
					root[pos] = now;
					return ;
				}
			}
		}
		
		int Find_Rank (int pos, int x)
		{
			S_D *now = root[pos];
			int Answer = 0;
			
			for (; ; )
			{
				if (now == NULL)
					return Answer;
				if (now->key == x)
					return (now->child[0] ? now->child[0]->size : 0) + Answer;
				else if (now->key < x)
				{
					Answer += (now->child[0] ? now->child[0]->size : 0) + now->weigth;
					now = now->child[1];
				}
				else if (now->key > x)
					now = now->child[0];
					
			}
		}
		
		Inline void Find (int pos, int x)
		{
			S_D *now;
			for (now = root[pos]; (now != NULL && x != now->key); now = now->child[x > now->key]);
			
			this->Splay (now);
			root[pos] = now;
			return ;
		}
		
		void Delete (int pos)
		{
			S_D *now = root[pos];
			if (now->weigth > 1)
			{
				now->weigth --;
				now->size --;
				return ;
			}
			if (now->child[0] == NULL && now->child[1] == NULL)
			{
				 root[pos] = NULL;
				 now->Clear ();
				 return ;
			}
			
			S_D *res;
			if (now->child[1] == NULL)
			{
				res = now;
				now->child[0]->father = NULL;
				root[pos] = now->child[0];
				res->Clear ();
				return ;
			}
			if (now->child[0] == NULL)
			{
				res = now;
				now->child[1]->father = NULL;
				root[pos] = now->child[1];
				res->Clear ();
				return ;
			}
			
			res = root[pos];
			S_D *res_pre = Find_Prefix_Pos (pos);
			this->Splay (res_pre);
			root[pos] = res_pre;
			root[pos]->child[1] = res->child[1];
			res->child[1]->father = root[pos];
			res->Clear ();
			root[pos]->Updata ();
			return;
		}
		
		Inline S_D *Find_Prefix_Pos (int pos)
		{
			S_D *now = root[pos];
			for (now = now->child[0]; now->child[1]; now = now->child[1]);
			return now;
		}
		
		int Ask_Prefix (int pos, int x)
		{
			S_D *now = root[pos];
			for (; now;)
			{
				if (now->key < x)
				{
					if (Answer < now->key)
						Answer = now->key;
					now = now->child[1];
				}
				else 
					now = now->child[0];
			}
			return Answer;
		}
		
		int Ask_Suffix (int pos, int x)
		{
			S_D *now = root[pos];
			for (; now; )
			{
				if (now->key > x)
				{
					if (Answer > now->key)
						Answer = now->key;
					now = now->child[0];
				}
				else 
					now = now->child[1];
			}
			return Answer;
		}
		
};
 
Splay_Tree_Type Splay;
 
class Segment_Tree_Type
{
	
	private :
		
		X_D *Root;
		void __Build_ (X_D *&now, int l, int r)
		{
			now = new X_D (l, r);
			
			if (l == r)
				return ;
			__Build_ (now->Left, l, now->Mid);
			__Build_ (now->Right, now->Mid + 1, r);
		}
		
		void __Insert_ (X_D *&now, int pos, int x, int _in)
		{
			Splay.Insert (_in, x);
			
			if (now->l == now->r)
				return ;
			if (pos <= now->Mid)
				__Insert_ (now->Left, pos, x, _in << 1);
			else 
				__Insert_ (now->Right, pos, x, _in << 1 | 1);
		}
				
		void __Query_Rank_ (X_D *&now, int l, int r, int k, int _in)
		{
			if (l <= now->l && now->r <= r)
			{
				Answer += Splay.Find_Rank (_in, k);
				return ;
			}
			
			if (l <= now->Mid)
				__Query_Rank_ (now->Left, l, r, k, _in << 1);
			if (now->Mid  < r)
				__Query_Rank_ (now->Right, l, r, k, _in << 1 | 1);
		}
		
		void __Change_ (X_D *&now, int pos, int x, int _in)
		{
			Splay.Find (_in, data[pos]);
			Splay.Delete (_in);
			Splay.Insert (_in, x);
			
			if (now->l == now->r)
				return ;
			if (pos <= now->Mid)
				__Change_ (now->Left, pos, x, _in << 1);
			else 
				__Change_ (now->Right, pos, x, _in << 1 | 1); 
		}
		
		void __Query_Prefix_ (X_D *&now, int l, int r, int x, int _in)
		{
			if (l <= now->l && now->r <= r)
			{
				Answer = max (Answer, Splay.Ask_Prefix (_in, x));
				return ;
			}
			
			if (l <= now->Mid)
				__Query_Prefix_ (now->Left, l, r, x, _in << 1);
			if (now->Mid < r)
				__Query_Prefix_ (now->Right, l, r, x, _in << 1 | 1);
		}
		
		void __Query_Suffix_ (X_D *&now, int l, int r, int x, int _in)
		{
			if (l <= now->l && now->r <= r)
			{
				Answer = min (Answer, Splay.Ask_Suffix (_in, x));
				return ;
			}
			
			if (l <= now->Mid)
				__Query_Suffix_ (now->Left, l, r, x, _in << 1);
			if (r > now->Mid)
				__Query_Suffix_ (now->Right, l, r, x, _in << 1 | 1);
		}
		
	public :
		
		void Build (int l, int r)
		{
			__Build_ (Root, l, r);
			return ;
		}
		
		Inline void Insert (int pos, int x)
		{
			__Insert_ (Root, pos, x, 1);
			return ;
		}
		
		Inline int Query_Suffix (int l, int r, int k)
		{
			Answer = INF;
			__Query_Suffix_ (Root, l, r, k, 1);
			return Answer;
		}
		
		Inline int Query_kth_number (int l, int r, int x)
		{
			int L, R, Mid;
			for (L = 0, R = Maxn + 1, Mid; L != R; )
			{
				Mid = L + R >> 1;
				Answer = 0;
				this->Query_Rank (l, r, Mid);
				if (Answer < x)
					L = Mid + 1;
				else
					R = Mid;
			}
			return L - 1;
		}
		
		Inline int Query_Rank (int l, int r, int k)
		{
			Answer = 0;
			__Query_Rank_(Root, l, r, k, 1);
			return Answer;
		}
		
		Inline int Query_Prefix (int l, int r, int k)
		{
			Answer = 0;
			__Query_Prefix_ (Root, l, r, k, 1);
			return Answer;
		}
		
		Inline void Change (int pos, int x)
		{
			__Change_ (Root, pos, x, 1);
			return ;
		}
};
 
Segment_Tree_Type Seg;
#define Cogs

int main (int argc, char *argv[])
{
#ifdef Cogs

	freopen ("psh.in", "r", stdin);
	freopen ("psh.out", "w", stdout);
	
#endif 	
	
	int N, M;
	read (N);
	read (M);
	
	Seg.Build (1, N);
	for (int i = 1; i <= N; i ++)
	{
		read (data[i]);
		Maxn = max (data[i], Maxn);
		
		Seg.Insert (i, data[i]); 
	}
	
	for (int type, x, y, z; M --; )
	{
		read (type);
		
		if (type == 1)
		{
			read (x);
			read (y);
			read (z);
			
			printf ("%d\n", Seg.Query_Rank (x, y, z) + 1);
		}
		else if (type == 2)
		{
			read (x);
			read (y);
			read (z);
			
			printf ("%d\n", Seg.Query_kth_number (x, y, z));
		}
		else if (type == 3)
		{
			read (x);
			read (z);
			Seg.Change (x, z);
			
			data[x] = z;
			Maxn = max (Maxn, x);
		}
		else if (type == 4)
		{
			read (x);
			read (y);
			read (z);
			
			printf ("%d\n", Seg.Query_Prefix (x, y, z));
		}
		else 
		{
			read (x);
			read (y);
			read (z);
			
			printf ("%d\n", Seg.Query_Suffix (x, y, z));
		}
	}
	return 0;
}