记录编号	249035	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	2.375 s
提交时间	2016-04-11 20:47:33	内存使用	35.48 MiB

#include<iostream>
#include<cstdio>
#include<time.h>
#include<stdlib.h>
using namespace std;
const int maxn = 5e4+10;
const int inf = 1e8+1;

int n, q;
int a[maxn];

struct node {
	int ls, rs, fa;
	int v, fix, size;
	inline node() {}
	inline node(int fa_, int v_, int fix_) { ls = rs = v = 0, fa = fa_, v = v_, fix = fix_; }
	inline void init() { ls = rs = fa = 0; }
}ns[maxn<<5];
int tot;


class treap {
private:
	int root_;
public:
	inline treap() { root_ = 0; }
	
	inline int root() { return root_; }
	
	inline int size() { return ns[root_].size; }
	
	inline void zig(int tar) {
		int tmp = ns[tar].fa;
		if(ns[ns[tmp].fa].ls == tmp) ns[ns[tmp].fa].ls = tar;
		else ns[ns[tmp].fa].rs = tar;
		ns[tar].fa = ns[tmp].fa;
		
		ns[tmp].ls = ns[tar].rs;
		if(ns[tar].rs) ns[ns[tar].rs].fa = tmp;
		
		ns[tar].rs = tmp; ns[tmp].fa = tar;
		
		ns[tmp].size = ns[ns[tmp].ls].size + ns[ns[tmp].rs].size + 1;
	}
	
	inline void zag(int tar) {
		int tmp = ns[tar].fa;
		if(ns[ns[tmp].fa].ls == tmp) ns[ns[tmp].fa].ls = tar;
		else ns[ns[tmp].fa].rs = tar;
		ns[tar].fa = ns[tmp].fa;
		
		ns[tmp].rs = ns[tar].ls;
		if(ns[tar].ls) ns[ns[tar].ls].fa = tmp;
		
		ns[tar].ls = tmp; ns[tmp].fa = tar;
		
		ns[tmp].size = ns[ns[tmp].ls].size + ns[ns[tmp].rs].size + 1;
	}
	
	inline void rebalance(int now) {
		int fa = ns[now].fa;
		while(fa && ns[now].fix < ns[fa].fix) {
			now == ns[fa].ls ? zig(now) : zag(now);
			fa = ns[now].fa;
		}
		if(fa == 0) root_ = now;
		ns[now].size = ns[ns[now].ls].size + ns[ns[now].rs].size + 1;
	}
	
	int dfs(int fr, int now) {
		int now_root = ++tot;
		ns[now_root] = ns[now];
		ns[now_root].fa = fr;
		if(ns[now].ls) {
			ns[now_root].ls = dfs(now_root, ns[now].ls);
		}
		if(ns[now].rs) {
			ns[now_root].rs = dfs(now_root, ns[now].rs);
		}
		return now_root;
	}
	
	inline void copy(int be, int size) {
		root_ = tot+1;
		dfs(0, be);
	}
	
	inline void set_root(int tar, int num) {
		root_ = num;
		ns[root_] = node(0, tar, rand());
		ns[root_].size = 1;
	}
	
	inline void insert(int tar, int num) {
//		printf("%d\n", num);
		if(!root_) {
			set_root(tar, num);
			return;
		}
		int now = root_;
		while(true) {
			ns[now].size++;
			if(tar < ns[now].v) {
				if(ns[now].ls) now = ns[now].ls;
				else {
					ns[now].ls = num;
					ns[num] = node(now, tar, rand());
					rebalance(num);
					return;
				}
			} else {
				if(ns[now].rs) now = ns[now].rs;
				else {
					ns[now].rs = num;
					ns[num] = node(now, tar, rand());
					rebalance(num);
					return;
				}
			}
		}
	}
	
	inline int find_del(int now) {
		while(ns[now].ls) {
			ns[now].size--;
			now = ns[now].ls;
		}
		int fa = ns[now].fa;
		if(ns[fa].ls == now) ns[fa].ls = ns[now].rs;
		else ns[fa].rs = ns[now].rs;
		if(ns[now].rs) ns[ns[now].rs].fa = fa;
		return now;
	}
	
	inline int del(int tar) { 
		if(ns[tar].ls && ns[tar].rs) {//替换掉tar
			int tmp = find_del(ns[tar].rs);
			ns[tar].v = ns[tmp].v;
			ns[tmp].init();
			return tmp;
		} else {//直接删掉tar 
			int fa = ns[tar].fa;
			if(ns[tar].ls) {
				if(ns[fa].ls == tar) ns[fa].ls = ns[tar].ls;
				else ns[fa].rs = ns[tar].ls;
				ns[ns[tar].ls].fa = fa;
				if(fa == 0) root_ = ns[tar].ls;
			} else if(ns[tar].rs){
				if(ns[fa].ls == tar) ns[fa].ls = ns[tar].rs;
				else ns[fa].rs = ns[tar].rs;
				ns[ns[tar].rs].fa = fa;
				if(fa == 0) root_ = ns[tar].rs;
			} else {//叶子节点 
				if(ns[fa].ls == tar) ns[fa].ls = 0;
				else ns[fa].rs = 0;
				if(fa == 0) root_ = 0;
			}
			return tar;
		}
	}
	
	inline void change(int tar, int v) {
		int now = root_;
		while(true) { //找到位置 
			ns[now].size--;
			if(ns[now].v == tar) break;
			else if(tar < ns[now].v) now = ns[now].ls;
			else now = ns[now].rs;
		}
		int num = del(now); //删掉原来的数 
		insert(v, num); //插入新数 
	}
	
	inline int get_rank(int tar) {
		int ans = 0, now = root_;
		while(now) {
			if(ns[now].v < tar) ans += ns[ns[now].ls].size+1, now = ns[now].rs;
			else  now = ns[now].ls;
		}
		return ans;
	}
	
	inline int get_pre(int tar) {//找前驱 
		int ans = -inf, now = root_;
		while(now) {
			if(ns[now].v < tar) ans = max(ans, ns[now].v), now = ns[now].rs;
			else  now = ns[now].ls;
		}
		return ans;
	}
	
	inline int get_sux(int tar) {
		int ans = inf, now = root_;
		while(now) {
			if(ns[now].v > tar) ans = min(ans, ns[now].v), now = ns[now].ls;
			else  now = ns[now].rs;
		}
		return ans;
	}
	
	void print(int now) {
		if(ns[now].ls) print(ns[now].ls);
		printf("%d ",ns[now].v);
		if(ns[now].rs) print(ns[now].rs);
	}
	
	void out() {
		print(root_);
	}
}; 


class segment_tree {
private:
	struct snode {
		int l, r;
		treap t;
		snode() {}
		snode(int l_, int r_) { l = l_, r = r_, t = treap(); }
	}sns[maxn<<2];
	 
public:
	
	inline void build(int i, int l, int r) {
		if(l == r) {
			sns[i] = snode(l, r);
			sns[i].t.insert(a[l], ++tot);
//			printf("l = %d r = %d:\n", l, r);
//			sns[i].t.out();
//			printf("\n");
			return;
		}
		
		build(i << 1, l, (l+r) >> 1);//先处理根节点，这样可以保证子树连续 
		build ((i << 1) | 1, ((l+r) >> 1) + 1, r);
		
		sns[i] = snode(l, r);
		sns[i].t.copy(sns[i<<1].t.root(), sns[i<<1].t.size());//先拷贝左子节点 
		for(int j = ((l+r) >> 1) + 1; j <= r; j++) {//右半部分全部插入 
			sns[i].t.insert(a[j], ++tot);
		}
//		printf("l = %d r = %d:\n", l, r);
//		sns[i].t.out();
//		printf("\n");
	}
	
	inline void change(int tar, int v) {
		int i = 1;
		while(sns[i].l != sns[i].r) {
			sns[i].t.change(a[tar], v);
			if(tar <= sns[i<<1].r) i = (i << 1);
			else i = ((i << 1) | 1);
		}
		sns[i].t.change(a[tar], v);
	}
		
	int get_rank(int i, int l, int r, int num) {
		if(sns[i].l == l && sns[i].r == r) return sns[i].t.get_rank(num);

		if(sns[i<<1].r >= r) return get_rank(i<<1, l, r, num);
		else if(sns[(i<<1)|1].l <= l) return get_rank((i<<1)|1, l, r, num);
		else return get_rank(i<<1, l, sns[i<<1].r, num) + get_rank((i<<1)|1, sns[(i<<1)|1].l, r, num);
	}
	
	inline int get_num(int l, int r, int rank) {
		int bl = 0, br = inf;
		int mid;
		while(bl < br) {
			mid = (bl+br) >> 1;
			if(get_rank(1, l, r, mid) >= rank) br = mid;
			else  bl = mid+1;
		}
		return br-1;
	}
	
	inline int get_pre(int i, int l, int r, int num) {
		if(sns[i].l == l && sns[i].r == r) return sns[i].t.get_pre(num);

		if(sns[i<<1].r >= r) return get_pre(i<<1, l, r, num);
		else if(sns[(i<<1)|1].l <= l) return get_pre((i<<1)|1, l, r, num);
		else return max(get_pre(i<<1, l, sns[i<<1].r, num), get_pre((i<<1)|1, sns[(i<<1)|1].l, r, num));
	}
	
	inline int get_sux(int i, int l, int r, int num) {
		if(sns[i].l == l && sns[i].r == r) return sns[i].t.get_sux(num);

		if(sns[i<<1].r >= r) return get_sux(i<<1, l, r, num);
		else if(sns[(i<<1)|1].l <= l) return get_sux((i<<1)|1, l, r, num);
		else return min(get_sux(i<<1, l, sns[i<<1].r, num), get_sux((i<<1)|1, sns[(i<<1)|1].l, r, num));
	}
}st;

int get_num() {
	int ans = 0;
	int han = 1;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') {
		if(tmp == '-') han = -1;
		tmp = getchar();
	}
	while(tmp <= '9' && tmp >= '0') {
		ans = ans*10 + tmp - '0';
		tmp = getchar();
	}
	return ans*han;
} 

inline void read() {
	n = get_num();
	q = get_num();
	for(int i = 1; i <= n; i++) {
		a[i] = get_num();
	}
}

inline void solve() {
	st.build(1, 1, n);
	int han, l, r, k, tar;
	for(int i = 1; i <= q; i++) {
		han = get_num();
		if(han == 1) 	  { l = get_num(); r = get_num(); k = get_num(); printf("%d\n", st.get_rank(1, l, r, k)+1); }
		else if(han == 2) { l = get_num(); r = get_num(); k = get_num(); printf("%d\n", st.get_num(l, r, k)); }
		else if(han == 3) { tar = get_num(); k = get_num(); st.change(tar, k); a[tar] = k;}
		else if(han == 4) { l = get_num(); r = get_num(); k = get_num(); printf("%d\n", st.get_pre(1, l, r, k)); }
		else if(han == 5) { l = get_num(); r = get_num(); k = get_num(); printf("%d\n", st.get_sux(1, l, r, k)); }
	}
}

int main() {
	freopen("psh.in", "r", stdin);
	freopen("psh.out", "w", stdout);
	srand((unsigned)time(NULL));
	read();
	solve();
	return 0;
}