【bzoj3678】wangxz与OJ

Solution

　　这题==真实智力康复qwq

　　然而众多神犇都说是10min写完的题我。。可能写了近1h吧==深深感受到自己的弱小qwq

　　（丢上来是因为。。我的splay实在是太垃圾了==）

　　其实就是splay的裸题啊qwq（然后因为过于不熟练导致写了巨久==）然后的话不同的地方就是插入的时候你不能一个一个往里面插。。因为插入的是连续的一段数，我们考虑直接将这段数存在一个点里面，在需要用其中的某个位置的时候再把这个位置分离出来

　　具体实现的话就是每个节点维护\(vall\)和\(valr\)就好了，提取某一个位置（假如说是第\(x\)个位置）的时候我们先找到这个位置再哪个点里面，然后把这个点（如果有的话）分成三个点，\(x\)之前的数一个点，\(x\)一个点，\(x\)之后的数一个点，然后返回一下就好了，注意一下splay中的父子关系什么的

　　删除\([l,r]\)位置中的数的话直接把\(l-1\)这个位置和\(r+1\)这个位置提取出来，然后大力splay：先把\(l-1\)转到根，再把\(r+1\)转到\(l-1\)的左儿子，这样\(r+1\)的整个左子树就是\([l,r]\)了，那我们直接把\(r+1\)的左儿子断掉就好了

　　代码大概长这个样子

#include<iostream>

#include<cstdio>

#include<cstring>

#define mp make_pair

#define Pr pair<int,int>

using namespace std;

const int N=1e5+10,S=N*10;

int n,m,ans;

namespace Splay{/*{{{*/

	int ch[S][2],vall[S],valr[S],fa[S],sz[S];

	int n,tot,rt;

	int which(int x){return ch[fa[x]][1]==x;}

	bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

	int newnode(int l,int r){

		ch[++tot][0]=0; ch[tot][1]=0; vall[tot]=l; valr[tot]=r;

		sz[tot]=r-l+1;

		return tot;

	}

	void pushup(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+(valr[x]-vall[x]+1);}

	void rotate(int x){

		int dir=which(x),f=fa[x];

		if (!isroot(f)) ch[fa[f]][which(f)]=x;

		fa[x]=fa[f]; fa[f]=x;

		if (ch[x][dir^1]) fa[ch[x][dir^1]]=f;

		ch[f][dir]=ch[x][dir^1];

		ch[x][dir^1]=f;

		pushup(f);

		pushup(x);

	}

	void splay(int x,int top){

		for (int f=fa[x]; fa[x]!=top; f=fa[x]){

			if (fa[f]!=top)

				rotate(which(f)==which(x)?f:x);

			rotate(x);

		}

		if (!top) rt=x;

	}

	int _build(int l,int r){

		if (l>r) return 0;

		int mid=l+r>>1;

		if (l==r){sz[mid]=1; return mid;}

		ch[mid][0]=_build(l,mid-1);

		ch[mid][1]=_build(mid+1,r);

		if (ch[mid][0]) fa[ch[mid][0]]=mid;

		if (ch[mid][1]) fa[ch[mid][1]]=mid;

		pushup(mid);

		return mid;

	}

	void build(int l,int r){rt=_build(l,r); tot=r;}

	int get_pos(int x,int k){

		if (k<=sz[ch[x][0]]) return get_pos(ch[x][0],k);

		if (k>sz[ch[x][0]]+(valr[x]-vall[x]+1)) return get_pos(ch[x][1],k-(sz[ch[x][0]]+valr[x]-vall[x]+1));

		int nw;

		k-=sz[ch[x][0]];

		if (k!=1){

			nw=newnode(vall[x],vall[x]+k-2);

			vall[x]=valr[nw]+1;

			ch[nw][0]=ch[x][0]; fa[ch[x][0]]=nw;

			ch[x][0]=nw; fa[nw]=x;

			pushup(nw);

			k=1;

		}

		if (k!=valr[x]-vall[x]+1){

			nw=newnode(vall[x]+k,valr[x]);

			valr[x]=vall[nw]-1;

			ch[nw][1]=ch[x][1]; fa[ch[x][1]]=nw;

			ch[x][1]=nw; fa[nw]=x;

			pushup(nw);

		}

		return x;

	}

	Pr split(int l,int r){

		int le=get_pos(rt,l),ri=get_pos(rt,r);

		splay(le,0);

		splay(ri,le);

		return mp(le,ri);

	}

	void insert(int p,int l,int r){

		Pr rec=split(p,p+1);

		int nw=newnode(l,r);

		ch[rec.second][0]=nw; fa[nw]=rec.second;

		pushup(rec.second);

		pushup(rec.first);

	}

	void del(int l,int r){

		Pr rec=split(l-1,r+1);

		ch[rec.second][0]=0;

		pushup(rec.second);

		pushup(rec.first);

	}

	int query(int x){

		int pos=get_pos(rt,x);

		return vall[pos];

	}

}/*}}}*/

int main(){

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

#endif

	int op,x,y,p;

	scanf("%d%d",&n,&m);

	for (int i=2;i<=n+1;++i){

		scanf("%d",&x);

		Splay::vall[i]=Splay::valr[i]=x;

	}

	Splay::build(1,n+2);//0~n+1

	for (int i=1;i<=m;++i){

		scanf("%d",&op);

		if (op==0){

			scanf("%d%d%d",&p,&x,&y);

			Splay::insert(p+1,x,y);

		}

		else if (op==1){

			scanf("%d%d",&x,&y);

			Splay::del(x+1,y+1);

		}

		else{

			scanf("%d",&p);

			printf("%d\n",Splay::query(p+1));

		}

	}

}

巴特西

【bzoj3678】wangxz与OJ

Solution

最新文章

热门文章