[CJOJ2425][SYZOI Round1]滑稽的树

cjoj

sol

子树转化成dfs序上的区间。

所以就变成了：区间Kth，区间内[a,b]范围内的数有多少个，单点修改

裸的树套树啊。

code

#include<cstdio>

#include<algorithm>

using namespace std;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 3e4+5;

struct segment_tree{int ls,rs,v;}t[N*150];

int n,m,a[N],to[N<<1],nxt[N<<1],head[N],cnt,dfn[N],low[N],rt[N],tot,t1,t2,tmp1[20],tmp2[20];

void link(int u,int v){to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;}

void dfs(int u,int f)

{

	dfn[u]=++cnt;

	for (int e=head[u];e;e=nxt[e])

		if (to[e]!=f) dfs(to[e],u);

	low[u]=cnt;

}

void Modify(int &x,int l,int r,int p,int v)

{

	if (!x) x=++tot;t[x].v+=v;

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

	if (p<=mid) Modify(t[x].ls,l,mid,p,v);

	else Modify(t[x].rs,mid+1,r,p,v);

}

int Query(int l,int r,int k)

{

	if (l==r) return l;

	int mid=l+r>>1,sum=0;

	for (int i=1;i<=t1;++i) sum+=t[t[tmp1[i]].ls].v;

	for (int i=1;i<=t2;++i) sum-=t[t[tmp2[i]].ls].v;

	if (k<=sum)

	{

		for (int i=1;i<=t1;++i) tmp1[i]=t[tmp1[i]].ls;

		for (int i=1;i<=t2;++i) tmp2[i]=t[tmp2[i]].ls;

		return Query(l,mid,k);

	}

	else

	{

		for (int i=1;i<=t1;++i) tmp1[i]=t[tmp1[i]].rs;

		for (int i=1;i<=t2;++i) tmp2[i]=t[tmp2[i]].rs;

		return Query(mid+1,r,k-sum);

	}

}

int PreQuery(int l,int r,int k)

{

	t1=t2=0;

	for (int i=r;i;i-=i&-i) tmp1[++t1]=rt[i];

	for (int i=l-1;i;i-=i&-i) tmp2[++t2]=rt[i];

	return Query(1,10000,k);

}

int Sum(int x,int l,int r,int ql,int qr)

{

	if (!x||l>=ql&&r<=qr) return t[x].v;

	int mid=l+r>>1;

	if (qr<=mid) return Sum(t[x].ls,l,mid,ql,qr);

	if (ql>mid) return Sum(t[x].rs,mid+1,r,ql,qr);

	return Sum(t[x].ls,l,mid,ql,qr)+Sum(t[x].rs,mid+1,r,ql,qr);

}

int main()

{

	n=gi();

	for (int i=1;i<=n;++i) a[i]=gi();

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

	{

		int u=gi(),v=gi();

		link(u,v);link(v,u);

	}

	cnt=0;dfs(1,0);

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

		for (int j=dfn[i];j<=n;j+=j&-j)

			Modify(rt[j],1,10000,a[i],1);

	m=gi();

	while (m--)

	{

		int opt=gi(),u=gi();

		if (opt==1)

		{

			int k=gi();

			printf("%d\n",PreQuery(dfn[u],low[u],k));

		}

		if (opt==2)

		{

			int l=gi(),r=gi(),ans=0;

			for (int j=low[u];j;j-=j&-j) ans+=Sum(rt[j],1,10000,l,r);

			for (int j=dfn[u]-1;j;j-=j&-j) ans-=Sum(rt[j],1,10000,l,r);

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

		}

		if (opt==3)

		{

			for (int j=dfn[u];j<=n;j+=j&-j) Modify(rt[j],1,10000,a[u],-1);

			a[u]=gi();

			for (int j=dfn[u];j<=n;j+=j&-j) Modify(rt[j],1,10000,a[u],1);

		}

	}

	return 0;

}