bzoj 3196 Tyvj 1730 二逼平衡树【线段树套 splay】

四舍五入就是个暴力。

对于线段树的每个区间都开一棵按权值排序的splay

对于第二个操作，二分一下，每次查询mid的排名，复杂度 $ O(nlog(n)^{3}) $
其余的操作都是$ O(nlog(n)^{2}) $

#include<iostream>

#include<cstdio>

using namespace std;

const int N=50005,T=2500250,inf=1e9;

int n,m,a[N],rt[T],tot,mn=inf,mx=-inf;

struct pinghengshu

{

	int c[2],v,s,f;

}t[T];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void pu(int x)

{

	t[x].s=t[t[x].c[0]].s+t[t[x].c[1]].s+1;

}

void zhuan(int p)

{

    int q=t[p].f,y=t[q].f,x=(t[q].c[1]==p);

    t[q].c[x]=t[p].c[x^1];t[t[q].c[x]].f=q;

    t[p].c[x^1]=q;t[q].f=p;t[p].f=y;

    if(y)

    {

        if(t[y].c[0]==q)

			t[y].c[0]=p;

        else

			t[y].c[1]=p;

    }

    pu(q);

	pu(p);

}

void splay(int ro,int x)

{

	for(int y;y=t[x].f;zhuan(x))

		if(t[y].f)

		{

			if((t[y].c[0]==x)^(t[t[y].f].c[0]==y))

				zhuan(y);

			else

				zhuan(x);

		}

	rt[ro]=x;

}

void charu(int ro,int x,int z)

{

	t[x].s++;

	while(t[x].c[t[x].v<z])

		x=t[x].c[t[x].v<z],t[x].s++;

	t[x].c[t[x].v<z]=++tot;

	t[tot].f=x;

	t[tot].s=1;

	t[tot].v=z;

	splay(ro,tot);

}

void build(int ro,int l,int r)

{

	rt[ro]=++tot;

	t[tot].s=1;

	t[tot].v=a[l];

	if(l==r)

		return;

	for(int i=l+1;i<=r;i++)

		charu(ro,rt[ro],a[i]);

	int mid=(l+r)>>1;

	build(ro<<1,l,mid);

	build(ro<<1|1,mid+1,r);

}

int zhao(int x,int z)

{

	if(t[x].v==z)

		return x;

	while(t[x].c[t[x].v<z])

	{

		x=t[x].c[t[x].v<z];

		if(t[x].v==z)

			return x;

	}

	return 0;

}

void shanchu(int ro,int x)

{

	splay(ro,x);

	if(!t[x].c[0])

		rt[ro]=t[x].c[1],t[t[x].c[1]].f=0;

	else if(!t[x].c[1])

		rt[ro]=t[x].c[0],t[t[x].c[0]].f=0;

	else

	{

		t[t[x].c[0]].f=0;

		int tmp=t[x].c[0];

		while(t[tmp].c[1])

			tmp=t[tmp].c[1];

		splay(ro,tmp);

		t[tmp].c[1]=t[x].c[1];

		t[t[x].c[1]].f=tmp;

		pu(tmp);

	}

}

int fd(int x,int z)

{

    int ans=0;

    while(x)

    {

        if(t[x].v>z)

            x=t[x].c[0];

		else

			ans+=t[t[x].c[0]].s+1,x=t[x].c[1];

   }

   return ans;

}

int paiming(int x,int l,int r,int ll,int rr,int kk)

{

    if(ll<=l&&rr>=r)

        return fd(rt[x],kk);

    int mid=(l+r)>>1,ans=0;

    if(ll<=mid)

		ans+=paiming(x<<1,l,mid,ll,rr,kk);

    if(rr>mid)

		ans+=paiming(x<<1|1,mid+1,r,ll,rr,kk);

    return ans;

}

void gai(int x,int l,int r,int p,int z)

{

    charu(x,rt[x],z);

    int x1=zhao(rt[x],a[p]);

    shanchu(x,x1);

    if(l==r)

		return ;

    int mid=(l+r)>>1;

    if(p<=mid)

		gai(x<<1,l,mid,p,z);

    else

		gai(x<<1|1,mid+1,r,p,z);

}

int pre(int x,int z)

{

    int ans=-inf;

    while(t[x].c[t[x].v<=z])

    {

        if(t[x].v<=z)

			ans=t[x].v;

        x=t[x].c[t[x].v<=z];

    }

	if(t[x].v<=z)

		ans=max(ans,t[x].v);

    return ans;

}

int suc(int x,int z)

{

    int ans=inf;

    while(t[x].c[t[x].v<z])

    {

        if(t[x].v>=z)

			ans=t[x].v;

        x=t[x].c[t[x].v<z];

    }

	if(t[x].v>=z)

		ans=min(ans,t[x].v);

    return ans;

}

int qianqu(int x,int l,int r,int ll,int rr,int kk)

{

    if(l>=ll&&r<=rr)

        return pre(rt[x],kk);

    int ans=-inf;

    int mid=(l+r)>>1;

    if(ll<=mid)

		ans=max(ans,qianqu(x<<1,l,mid,ll,rr,kk));

    if(rr>mid)

		ans=max(ans,qianqu(x<<1|1,mid+1,r,ll,rr,kk));

    return ans;

}

int houji(int x,int l,int r,int ll,int rr,int kk)

{

    if(l>=ll&&r<=rr)

        return suc(rt[x],kk);

    int ans=inf;

    int mid=(l+r)>>1;

    if(ll<=mid)

		ans=min(ans,houji(x<<1,l,mid,ll,rr,kk));

    if(rr>mid)

		ans=min(ans,houji(x<<1|1,mid+1,r,ll,rr,kk));

    return ans;

}

int main()

{

	n=read(),m=read();

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

		a[i]=read(),mx=max(a[i],mx),mn=min(mn,a[i]);

	build(1,1,n);

	while(m--)

	{

		int o=read();

		if(o==1)

		{//cout<<"paiming"<<endl;

			int l=read(),r=read(),k=read();

			printf("%d\n",paiming(1,1,n,l,r,k-1)+1);

		}

		else if(o==2)

		{//cout<<"shu"<<endl;

			int ll=read(),rr=read(),k=read(),l=mn,r=mx;

			while(l<=r)

			{

				int mid=(l+r)>>1;//cout<<mid<<endl;

				if(paiming(1,1,n,ll,rr,mid)<k)

					l=mid+1;

				else

					r=mid-1;

			}

			printf("%d\n",l);

		}

		else if(o==3)

		{//cout<<"gai"<<endl;

			int p=read(),k=read();

			gai(1,1,n,p,k);

			a[p]=k;

		}

		else if(o==4)

		{//cout<<"qianqu"<<endl;

			int l=read(),r=read(),k=read();

			printf("%d\n",qianqu(1,1,n,l,r,k-1));

		}

		else

		{//cout<<"houzhui"<<endl;

			int l=read(),r=read(),k=read();

			printf("%d\n",houji(1,1,n,l,r,k+1));

		}

	}

	return 0;

}

巴特西

bzoj 3196 Tyvj 1730 二逼平衡树【线段树套 splay】

最新文章

热门文章

巴特西

bzoj 3196 Tyvj 1730 二逼平衡树【线段树 套 splay】

最新文章

热门文章

bzoj 3196 Tyvj 1730 二逼平衡树【线段树套 splay】