[BZOJ1146]CTSC2008网络管理|树上带批改K大

[BZOJ1146]CTSC2008网络管理|树上带修改K大

  树上带修改K大,太可怕。。写了树链剖分+线段树套平衡树+二分和dfs+主席树两种,每种都是写+调试花了将近5个小时!!我实在是太弱了。。

1.   树链剖分+线段树套平衡树+二分

最显然的做法了,没啥好多说的,不过写起来真是麻烦(我太弱),

一不小心就会把线段树和平衡树的节点的域弄混,犯了超级多傻逼错误。。写这题的时候还把自己树链剖分的风格改了一下,以前的实在是太麻烦了。。查询的时候二分答案,统计比当前的k大的数有多少个就行了。。

2.   dfs+主席树

 考虑不带修改,那么可以对每个节点维护一颗权值线段树记录它到root的数,类型区间K大的,每个点的新树可以由父节点更新log n个节点来得到,所以初始化是ONlog N),查询只要把这两个点和lca的权值权值线段树拉出来,二分答案像上面一样搞就行。。如果这两个点是xylcapUi表示i节点的权值线段树,答案就是Ux+Uy-2*Up再加上p的权值。。

     再来想带修改,大思路还是要把树转化成线性序列来搞。。那么就想到dfs序,若修改一个节点的权值,只会改变它的子树上的各点的权值线段树,而这些点再dfs序中又对应的是一段区间,那就有办法了。。用树状数组来维护所有的修改,若点ia被修改为bL[i]表示idfs序中出现的位置,R[i]表示i的子树上的节点在dfs中出现的最后位置,那么先将L[i]-na减去1b加上1,再讲R[i]+1-na加上1b减去1,那么就完成的对子树区间的修改。。具体查询的时候只要把dfs序当做区间k大那样做就行了,记得要加上原来未修改时的权值线段树。。

树剖+线段树套平衡树+二分:

#include<cstdio>
#include<iostream>
#define N 80005
#define NN 1600020
#define ls c[x][0]
#define rs c[x][1]
using namespace std;
struct edge{
	int e,next;
}ed[N*2];
int n,Q,s,e,ne=0,i,nd=0,cnt=0,rt,k,x,y,maxq=0,a[N],q[N],q1[N],fa[N],sz[N],top[N],son[N],d[N],xu[N],root[N*4],l[N*4],r[N*4],lc[N*4],rc[N*4],c[NN][2],size[NN],num[NN],same[NN],pre[NN];
void add(int s,int e)
{
	ed[++ne].e=e;
	ed[ne].next=a[s];a[s]=ne;
}
//处理size 选出son 
void dfs1(int x)
{
	int to,ms=0;
	sz[x]=1;son[x]=0;
	for (int j=a[x];j;j=ed[j].next)
		if (ed[j].e!=fa[x])
		{
			to=ed[j].e;d[to]=d[x]+1;
			fa[to]=x;dfs1(to);
			sz[x]+=sz[to];
			if (ms<sz[to]) ms=sz[to],son[x]=to;
		}
}
//链剖 
void dfs2(int x,int tp)
{
	xu[x]=++cnt;q1[cnt]=q[x];top[x]=tp;
	if (son[x]) dfs2(son[x],tp);
	for (int j=a[x];j;j=ed[j].next) if (ed[j].e!=fa[x]&&ed[j].e!=son[x]) dfs2(ed[j].e,ed[j].e);
}
//splay
void print(int x)
{
	if (!x) return;
	print(ls);printf("%d^%d ",num[x],same[x]);print(rs);
}
void newnode(int &x,int fa,int k)
{
	x=++nd;pre[x]=fa;
	num[x]=k;size[x]=same[x]=1;
	ls=rs=0;
}
void update(int x){size[x]=size[ls]+size[rs]+same[x];}
void rot(int x,int kind)
{
	int y=pre[x],z=pre[y];
	pre[c[x][kind]]=y;c[y][!kind]=c[x][kind];
	pre[y]=x;c[x][kind]=y;
	pre[x]=z;if (z) c[z][c[z][1]==y]=x;
	update(y);update(x);
}
void splay(int x,int rt)
{
	int y,z,kind;
	while (pre[x])
	{
		int y=pre[x];
		if (!pre[y]) rot(x,c[y][0]==x);
		else
		{
			z=pre[y];kind=(c[z][0]==y);
			if (c[y][kind]==x) rot(x,!kind);else rot(y,kind);
			rot(x,kind);
		}
	}
	root[rt]=x;
}
void ins(int &x,int k,int rt,int fa)
{
	if (!x) {newnode(x,fa,k);splay(x,rt);return;}
	if (num[x]==k){size[x]++;same[x]++;splay(x,rt);return;}
	ins(c[x][num[x]<k],k,rt,x);update(x);
}
void merge(int c1,int c2,int rt)
{
	pre[c1]=0;
	while (c[c1][1]) c1=c[c1][1];
	splay(c1,rt);c[c1][1]=c2;pre[c2]=c1;
	update(c1);
	root[rt]=c1;
}
int find(int x,int k){return num[x]==k?x:find(c[x][num[x]<k],k);}
void del(int x,int k,int rt)
{
	x=find(x,k);
	splay(x,rt);
	if (same[x]>1) {same[x]--;size[x]--;return;}
	if (ls*rs==0) {root[rt]=ls+rs,pre[ls+rs]=0;return;}
	merge(ls,rs,rt);
}
//初始化树套树 
void build(int &x,int ll,int rr)
{
	x=++cnt;l[x]=ll;r[x]=rr;root[x]=0;
	ins(root[x],q1[ll],x,0);
	if (ll==rr)
	{
		lc[x]=rc[x]=0;
		return;
	}
	int mid=(ll+rr)>>1;
	for (int i=ll+1;i<=rr;i++) ins(root[x],q1[i],x,0);
	build(lc[x],ll,mid);build(rc[x],mid+1,rr);
}
void init()
{
	fa[1]=0;d[1]=0;size[0]=0;
	dfs1(1);dfs2(1,1);
	cnt=0;build(rt,1,n);
}
//修改&&询问
void change(int x,int ll,int k)
{
	if (!x) return;
	del(root[x],q1[ll],x);ins(root[x],k,x,0);//print(root[x]);printf("\n");printf("%d %d %d %d**\n",root[x],l[x],r[x],size[0]);
	if (ll>(l[x]+r[x])/2) change(rc[x],ll,k);else change(lc[x],ll,k);
}
int lca(int x,int y)
{
	if (d[top[x]]>d[top[y]]) swap(x,y);
	while (top[x]!=top[y])
	{
		y=fa[top[y]];
		if (d[top[x]]>d[top[y]]) swap(x,y);
	}
	return d[x]<d[y]?x:y;
}
int getsz(int x,int k)
{
	int ans=0;
	while (x)
	{//printf("here:%d %d %d %d\n",k,num[x],size[rs],same[x]);
		if (num[x]>k) ans+=size[rs]+same[x];
		else if (num[x]==k) return ans+size[rs];
		x=c[x][num[x]<k];
	}
	return ans;
}
int query(int x,int ll,int rr,int k)//查询比k大的数量 
{
	if (ll>r[x]||rr<l[x]) return 0;
	if (ll<=l[x]&&rr>=r[x])
	{
	//	print(root[x]);printf("*\n");
		return getsz(root[x],k);
	}
	return query(lc[x],ll,rr,k)+query(rc[x],ll,rr,k);
}
int sum(int x,int y,int k)
{
	int ans=0;
	while (top[x]!=top[y])
	{
		if (d[top[x]]>d[top[y]]) swap(x,y);
		ans+=query(rt,xu[top[y]],xu[y],k);//printf("$%d %d %d\n",xu[top[y]],xu[y],ans);
		y=fa[top[y]];
	}
	ans+=query(rt,min(xu[x],xu[y]),max(xu[x],xu[y]),k);
	return ans;
}   
void solve(int x,int y,int k)
{
	int p=lca(x,y),l=1,r=maxq,mid,t;
	if (d[x]+d[y]-2*d[p]+1<k) {printf("invalid request!\n");return;}
	while (l<r)
	{
		mid=(l+r)>>1;
		t=sum(x,y,mid);//printf("re:%d %d\n",mid,t);
		if (t>=k) l=mid+1;else r=mid;
	}
	printf("%d\n",l); 
}
int main()
{
	freopen("1146.in","r",stdin);
	scanf("%d%d",&n,&Q);
	for (i=1;i<=n;i++) scanf("%d",&q[i]),a[i]=0,maxq=max(maxq,q[i]);
	for (i=1;i<n;i++)
	{
		scanf("%d%d",&s,&e);
		add(s,e);add(e,s);
	}
	init();
//	for (i=1;i<=n;i++) printf("%d ",q1[i]);printf("\n");
	while (Q--)
	{
		scanf("%d%d%d",&k,&x,&y);
		if (!k) change(rt,xu[x],y),q1[xu[x]]=y,maxq=max(maxq,y);else solve(x,y,k);//printf("%d cao\n",size[0]);
	}
}

dfs序+主席树:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 80010
#define NN 8000010
using namespace std;
struct edge{
	int e,xu,next;
}ed[N*4];//兼并了图的边和询问lca点对 
struct node{
	int n,yuan;
	node(){}
	node(int n,int yuan):n(n),yuan(yuan){}
}num[2*N];
int n,Q,i,ne=0,nd=0,tim=0,cnt=0,tot=0,s,e,sum[2],d[N],a[N],L[N],R[N],fa[N],pre[N],size[NN],lc[NN],rc[NN],lca[N],k[N],x[N],y[N],u[N],h[N],q[N],newq[2*N],root[N],c[N],use[N][2];
int lowbit(int x){return x&-x;}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void add(int s,int e)
{
	ed[++ne].e=e;ed[ne].next=a[s];a[s]=ne;
}
void add2(int s,int e,int xu)
{
	ed[++ne].e=e;ed[ne].xu=xu;ed[ne].next=h[s];h[s]=ne;
} 
bool cmp(node a,node b) {return a.n<b.n;}
int update(int l,int r,int last,int k,int del)
{
	int x=++nd,mid=(l+r)>>1;
	size[x]=size[last]+del;
	lc[x]=rc[x]=0;
	if (l==r) return x;
	if (k<=mid) lc[x]=update(l,mid,lc[last],k,del),rc[x]=rc[last];else rc[x]=update(mid+1,r,rc[last],k,del),lc[x]=lc[last];
	return x;
}
void dfs(int x)
{
	fa[x]=x;L[x]=++tim;u[x]=0;
	root[x]=update(1,tot,root[pre[x]],q[x],1);
	for (int j=a[x];j;j=ed[j].next)
		if (ed[j].e!=pre[x])
		{
			d[ed[j].e]=d[x]+1;pre[ed[j].e]=x;
			dfs(ed[j].e);fa[ed[j].e]=x;
		}
	R[x]=tim;u[x]=1;
	for (int j=h[x];j;j=ed[j].next)
		if (u[ed[j].e]) lca[ed[j].xu]=getfa(ed[j].e);
}
void change(int x,int k,int del)
{
	for (int i=x;i<=n;i+=lowbit(i)) c[i]=update(1,tot,c[i],k,del);
}
void get(int x,int kind)
{
	for (int i=x;i;i-=lowbit(i)) use[++sum[kind]][kind]=c[i];
}
int calc(int kind)
{
	int ans=0;
	for (int i=1;i<=sum[kind];i++) ans+=size[rc[use[i][kind]]];
	return ans;
}
void next(int kind,int dir)
{
	for (int i=1;i<=sum[kind];i++) use[i][kind]=dir?rc[use[i][kind]]:lc[use[i][kind]];
}
void query(int p,int x,int y,int k)
{
	if (d[x]+d[y]-2*d[p]+1<k) {printf("invalid request!\n");return;}
	sum[0]=sum[1]=0;
	get(L[x],1);get(L[y],1);get(L[p],0);
	int ux=root[x],uy=root[y],up=root[p];
	int l=1,r=tot,mid,now;
	bool f=true;
	while (l<r)
	{
		mid=(l+r)>>1;
		now=size[rc[ux]]+calc(1)+size[rc[uy]]-2*(calc(0)+size[rc[up]]);
		if (f)now+=(q[p]>mid);
		if (now>=k) 
		{
			next(1,1);next(0,1);ux=rc[ux];uy=rc[uy];up=rc[up];
			l=mid+1;
		}
		else 
		{
			next(1,0);next(0,0);ux=lc[ux];uy=lc[uy];up=lc[up];
			if (q[p]>mid) f=false;
			r=mid,k-=now;
		}
	}
	printf("%d\n",newq[l]);
}
int main()
{
	scanf("%d%d",&n,&Q);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&q[i]);
		num[++cnt]=node(q[i],i);
		a[i]=h[i]=c[i]=0;
	}
	for (i=1;i<n;i++)
	{
		scanf("%d%d",&s,&e);
		add(s,e);add(e,s);
	}
	for (i=1;i<=Q;i++)
	{
		scanf("%d%d%d",&k[i],&x[i],&y[i]);
		if (!k[i])num[++cnt]=node(y[i],n+i);else add2(x[i],y[i],i),add2(y[i],x[i],i);
	}
	sort(num+1,num+1+cnt,cmp);
	for (i=1;i<=cnt;i++)
	{
		if (num[i].n!=num[i-1].n) newq[++tot]=num[i].n;
		if (num[i].yuan>n) y[num[i].yuan-n]=tot;else q[num[i].yuan]=tot;
	}
	d[(n+1)/2]=0;pre[(n+1)/2]=0;root[0]=0;lc[0]=rc[0]=0;size[0]=0;
	dfs((n+1)/2);
	for (i=1;i<=Q;i++)
	if (k[i]) query(lca[i],x[i],y[i],k[i]);
	else 
	{
		change(L[x[i]],q[x[i]],-1);change(R[x[i]]+1,q[x[i]],1);
		change(L[x[i]],y[i],1);change(R[x[i]]+1,y[i],-1);
		q[x[i]]=y[i];
	}
}