[bzoj3196]-Tyvj 1730 二逼平衡树

发布于 2018-02-23  25 次阅读



题目(BZOJ)
题目(LibreOJ)
题目(洛谷)
 
裸的树套树......我写的是线段树套splay,常数是比较大......

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;int ck=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=-1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	e*=ck;
}
const int N=50050;
const int M=1600050;
int n,Q,head,tail;
int a[N],ans;
int ch[M][2],siz[M],key[M],fa[M],rt[M],cnt[M],idx;
inline int getx(int x){return ch[fa[x]][1]==x;}
inline void pushup(int x){if(x){siz[x]=cnt[x];if(ch[x][0])siz[x]+=siz[ch[x][0]];if(ch[x][1])siz[x]+=siz[ch[x][1]];}}
inline void roll(int x){
	int y=fa[x],z=fa[y],l,r;
	l=(ch[y][1]==x)^1;r=l^1;
	ch[y][r]=ch[x][l];fa[ch[y][r]]=y;ch[x][l]=y;fa[y]=x;
	if(z)ch[z][ch[z][1]==y]=x;fa[x]=z;
	pushup(y);pushup(x);
}
inline void splay(int x){for(int f;f=fa[x];roll(x))if(fa[f])roll((getx(x)==getx(f))?f:x);}
inline void make_tree(int id,int val){
	siz[id]=cnt[id]=1;fa[id]=0;key[id]=val;
	ch[id][0]=ch[id][1]=0;
}
inline void clear_tree(int x){siz[x]=fa[x]=ch[x][0]=ch[x][1]=cnt[x]=key[x]=0;}
inline void insert(int id,int val){
	if (!rt[id]){++idx;make_tree(idx,val);rt[id]=idx;return;}
	int now=rt[id],f=0;
	while(true){
		if (val==key[now]){
			cnt[now]++;pushup(f);splay(now);
			rt[id]=now;return;
		}
		f=now;now=ch[now][key[now]<val];
		if (!now){
			++idx;make_tree(idx,val);fa[idx]=f;
			ch[f][key[f]<val]=idx;
			pushup(f);splay(idx);rt[id]=idx;return;
		}
	}
}
inline int find_pre(int id){int now=ch[rt[id]][0];while(ch[now][1])now=ch[now][1];return now;}
inline int find_suc(int id){int now=ch[rt[id]][1];while(ch[now][0])now=ch[now][0];return now;}
inline void find_pos(int id,int val){
	int now=rt[id];
	while(true){
		if(key[now]==val){splay(now);rt[id]=now;return;}
		else if(key[now]>val)now=ch[now][0];else if(key[now]<val)now=ch[now][1];
	}
}
inline void del(int id){
	int now=rt[id],y=now;
	if(cnt[now]>1){cnt[now]--;pushup(now);return;}
	if(!ch[now][0]&&!ch[now][1]){clear_tree(rt[id]);rt[id]=0;return;}
	if(!ch[now][0]){rt[id]=ch[y][1];fa[rt[id]]=0;clear_tree(y);return;}
	if(!ch[now][1]){rt[id]=ch[y][0];fa[rt[id]]=0;clear_tree(y);return;}
	int pre=find_pre(id);y=rt[id];splay(pre);rt[id]=pre;
	ch[rt[id]][1]=ch[y][1];fa[ch[y][1]]=rt[id];
	clear_tree(y);pushup(rt[id]);
}
inline int find_rank(int id,int val){
	int now=rt[id],ans=0;
	while(true){
		if(!now)return ans;
		if(key[now]==val)return ((ch[now][0])?siz[ch[now][0]]:0)+ans;
		if(key[now]<val){ans+=((ch[now][0])?siz[ch[now][0]]:0)+cnt[now];now=ch[now][1];}
		else if(key[now]>val)now=ch[now][0];
	}
}
inline int find_pre_val(int id,int k){
	int now=rt[id];
	while(now){if(key[now]<k){ans=max(ans,key[now]);now=ch[now][1];}else now=ch[now][0];}
	return ans;
}
inline int find_suc_val(int id,int k){
	int now=rt[id];
	while(now){if(key[now]>k){ans=min(ans,key[now]);now=ch[now][0];}else now=ch[now][1];}
	return ans;
}
#define ls id<<1
#define rs id<<1|1
void build(int l,int r,int id,int pos,int val){
	insert(id,val);
	if (l==r) return;
	int mid=(l+r)>>1;
	if (pos<=mid) build(l,mid,ls,pos,val);
	else build(mid+1,r,rs,pos,val);
}
void change(int l,int r,int id,int pos,int val){
	find_pos(id,a[pos]);del(id);insert(id,val);
	if(l==r)return;
	int mid=(l+r)>>1;
	if (pos<=mid) change(l,mid,ls,pos,val);
	else change(mid+1,r,rs,pos,val);
}
void qrank(int l,int r,int id,int L,int R,int k){
	if (L<=l&&R>=r){
		ans+=find_rank(id,k);
		return;
	}
	int mid=(l+r)>>1;
	if (L<=mid) qrank(l,mid,ls,L,R,k);
	if (R>=mid+1) qrank(mid+1,r,rs,L,R,k);
}
void qpre(int l,int r,int id,int L,int R,int val){
	if (L<=l&&R>=r){
		ans=max(ans,find_pre_val(id,val));
		return;
	}
	int mid=(l+r)>>1;
	if (L<=mid) qpre(l,mid,ls,L,R,val);
	if (R>=mid+1) qpre(mid+1,r,rs,L,R,val);
}
void qsuc(int l,int r,int id,int L,int R,int val){
	if (L<=l&&R>=r){
		ans=min(ans,find_suc_val(id,val));
		return;
	}
	int mid=(l+r)>>1;
	if (L<=mid) qsuc(l,mid,ls,L,R,val);
	if (R>=mid+1) qsuc(mid+1,r,rs,L,R,val);
}
inline void sol1(){
	int l,r,k;read(l),read(r),read(k);qrank(1,n,1,l,r,k);
	printf(
}
inline void sol2(){
	int l,r,k;read(l),read(r),read(k);
	int L=head,R=tail+1;
	while(L<R){
		int mid=(L+R)>>1;ans=0;
		qrank(1,n,1,l,r,mid);
		if (ans<k) L=mid+1;
		else R=mid;
	}
	printf(
}
inline void sol3(){
	int pos,k;read(pos),read(k);
	tail=max(tail,k);
	change(1,n,1,pos,k);
	a[pos]=k;
}
inline void sol4(){
	int l,r,k;read(l),read(r),read(k);ans=-2147483647;qpre(1,n,1,l,r,k);
	printf(
}
inline void sol5(){
	int l,r,k;read(l),read(r),read(k);ans=2147483647;qsuc(1,n,1,l,r,k);
	printf(
}
int main(){
	read(n),read(Q);
	for (int i=1;i<=n;++i) read(a[i]),tail=max(tail,a[i]);
	for (int i=1;i<=n;++i) build(1,n,1,i,a[i]);
	while(Q--){
		int opt;read(opt);ans=0;
		switch (opt){
			case 1:{sol1();break;}
			case 2:{sol2();break;}
			case 3:{sol3();break;}
			case 4:{sol4();break;}
			case 5:{sol5();break;}
			default:{break;}
		}
	}
	return 0;
}