BZOJ 1146 网络管理

Link

小时候写过树状数组套主席树的版本，时空$O(n\log^2n)$。众所周知，这个空间复杂度是非常不友好的。 今天翻到jcvb巨神的博客，发现他给了一种非常interesting的做法：值域线段树套区间平衡树。研究一番，写完之后感觉很不错。

树状数组套主席树维护DFS序

Solution

众所周知，序列上的主席树可以利用可持久化实现时空$O(n\log n)$的前缀和，从而解决区间K值问题。 放到树上，如果不带修改，那就可以直接用序列的可持久化线段树方法，从根节点DFS下去，在节点$u$的值域线段树的$[l,r]$区间，维护$u$到$root$路径上值在$[l,r]$的节点个数。这样，两点$u,v$的路径上，值在$[l,r]$的节点个数$c(u,v)$，就是$c(u)+c(v)-c(lca)-c(fa[lca])$。套用序列的方法查询即可。 现在有了修改，显然不可能暴力重建主席树，因为一次修改会影响子树的所有的点。 等等，一次修改影响子树所有的点？不禁让人思考能否进行区间操作？然后就联想到了DFS序。没错，DFS序就是一个满足子树的所有点是一个区间的序列。 区间操作的两种办法：用兹瓷区间修改的数据结构打标记；或者差分，把区间修改变成单点修改。待修改的树上主席树是通过套一个树状数组，绝对化相对的方法来实现的。这样，线段树就不需要可持久化了，因为本来可持久化是要维护前缀和，但现在树状数组就维护了前缀和。一次修改，会修改$O(\log n)$个线段树，每个线段树修改的时间是$O(\log n)$。一个点的值至多将在$O(\log n)$个线段树出现，粗略地估计总次数，绝对不会超过$O(\log n)$。所以得到了一个时空$O(n\log ^2n)$的优秀做法。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;
#define S(X,NUMO) seg[X].son[NUMO]
	

const int MAXN=80010;
const int MAXLOGN=18;
const int MAXRG=MAXN*2;
const int MAXLOGRG=20;
const int INF=522133279;
const int MAXP=12000000;

int nset[MAXN*2],nc=0;

inline int Get(int x)
{
	return lower_bound(nset+1,nset+nc,x)-nset;
}
int T[MAXN];int N,Q;
int e[MAXN*2],pre[MAXN*2],id[MAXN],ec=0;
int l2(int x)//log x 取下整
{
	int i=0;
	while((1<<i)<=x)
		++i;
	return i-1;
}
void adde(int _f,int _t)
{
	e[++ec]=_t;pre[ec]=id[_f];id[_f]=ec;
	e[++ec]=_f;pre[ec]=id[_t];id[_t]=ec;
}
int dfs[MAXN],dep[MAXN],dc=0,lin[MAXN],rout[MAXN],fa[MAXN];//BIT用
int mdfs[MAXN*2],ml[MAXN],mr[MAXN],mdc=0;//ST用
	//每条边访问一次,而每访问一条边加入2个点 所以总共是2n级别的
void DFS(int pos,int d)
{
	dep[pos]=++d;
	dfs[++dc]=pos;
	mdfs[++mdc]=pos;
	lin[pos]=rout[pos]=dc;
	ml[pos]=mr[pos]=mdc;
	for(int i=id[pos];i;i=pre[i])
		if(fa[pos]!=e[i])
		{
			fa[e[i]]=pos;
			DFS(e[i],d);
			rout[pos]=max(rout[pos],rout[e[i]]);		
			mdfs[++mdc]=pos;
			mr[pos]=max(mr[pos],mdc);
		}
	
}
int f[MAXN*2][20];//i到i+(2^j)-1 [i开始长度为2^j]的最浅点
void outst()
{
	for(int j=0;j<=l2(mdc);j++)
	{
		printf("2^%d:",j);
		for(int i=1;i<=mdc;i++)
			printf("%d-%d  ",i,f[i][j]);
		puts("");
	}
}
void ST()
//dfs
{
	for(int i=1;i<=mdc;i++)
		f[i][0]=mdfs[i];
	int endj=l2(mdc),endi,pl,pr,t;	
	for(int j=1;j<=endj;j++)
	{
		endi=mdc-(1<<j)+1;
		for(int i=1;i<=endi;i++)
		{
			pl=f[i][j-1];
			pr=f[i+(1<<j)-(1<<j>>1)][j-1];
			f[i][j]=dep[pl]<dep[pr]?pl:pr;
		}
	}
}

int LCA(int p1,int p2)
{
	p1=ml[p1],p2=ml[p2];
	if(p1>p2) swap(p1,p2);
	int j=l2(p2-p1+1),ans=-1;
	p1=f[p1][j],p2=f[p2-(1<<j)+1][j];
	return dep[p1]>dep[p2]?p2:p1;
}
int inp[MAXN][3];

struct SegNode
{
	int son[2],cnt;
};

struct BIT
{
	int root[MAXN],pc,n;
	SegNode seg[MAXP];int TL,TR;//1,N
	inline int lowbit(int x){return x&(-x);}
	BIT(){pc=0;}
	inline void valup(int pos)
	{
		seg[pos].cnt=0;
		if(S(pos,0)) seg[pos].cnt+=seg[S(pos,0)].cnt;
		if(S(pos,1)) seg[pos].cnt+=seg[S(pos,1)].cnt;
	}
	int Acs(int pos,int L,int R,int l,int r)
	{
		if(!pos)
			return 0;
		if(L==l && R==r)
			return seg[pos].cnt;
		else
		{
			int MID=(L+R)>>1;
			if(r<=MID)
				return Acs(S(pos,0),L,MID,l,r);
			else if(MID+1<=l)
				return Acs(S(pos,1),MID+1,R,l,r);
			else
				return Acs(S(pos,0),L,MID,l,MID)+Acs(S(pos,1),MID+1,R,MID+1,r);
		}
	}
	int Edit(int pos,int L,int R,int goal,int v)
	{
		int pres=pos?pos:++pc;
		seg[pres]=seg[pos];
		if(L==R)
			seg[pres].cnt+=v;
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID)
				S(pres,0)=Edit(S(pos,0),L,MID,goal,v);
			else
				S(pres,1)=Edit(S(pos,1),MID+1,R,goal,v);
			valup(pres);
		}
		return pres;
	}
	int Sum(int pos,int l,int r)
	//得到树上pos位置的线段树[l,r]区间的cnt
	{
		if(!pos)
			return 0;
		int ans=0;
		pos=lin[pos];
		for(;pos;pos-=lowbit(pos))	
			ans+=Acs(root[pos],TL,TR,l,r);
		return ans;
	}
	int add(int pos,int goal,int v)
	//修改dfs序列中的pos对应的树
	{
		for(;pos<=n;pos+=lowbit(pos))
			root[pos]=Edit(root[pos],TL,TR,goal,v);
	}
	int Add(int pos,int goal,int v)
	//修改pos(树上编号)应的子树的区间
	{
		add(lin[pos],goal,v);
		if(rout[pos]<n)
			add(rout[pos]+1,goal,-v);
		
	}
	int Que(int p1,int p2,int K)
	{
		int lca=LCA(p1,p2);
		K=dep[p1]+dep[p2]-dep[lca]*2+1-K+1;
		if(K<=0)
			return -INF;

		int L=TL,R=TR,MID=(L+R)>>1,sum;
		//int s1,s2,s3;	
		while(K)
		{
			if(L==R)
			{
					return nset[L];
			}
			MID=(L+R)>>1;
			sum=Sum(p1,L,MID)+Sum(p2,L,MID)-Sum(lca,L,MID)-Sum(fa[lca],L,MID);
			
			if(sum<K)
			{
				K-=sum;
				L=MID+1;
			}
			else R=MID;
		}
		return INF;
	}
	void Out()
	{
		for(int i=1;i<=n;i++)
			printf("%d ",Sum(i,TL,TR));
		puts("");
	}
	void OutS()
	{
		for(int i=1;i<=n;i++)
			printf("%d ",Acs(root[i],TL,TR,TL,TR));
		puts("");
	}
}B;
void InitSeg(int pos)
{
	B.Add(pos,Get(T[pos]),1);
	for(int i=id[pos];i;i=pre[i])
		if(e[i]!=fa[pos])
			InitSeg(e[i]);
}
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	scanf("%d%d",&N,&Q);
	B.n=N;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&T[i]);
		nset[++nc]=T[i];
	}
	int t1,t2,t3;
	for(int i=1;i<=N-1;i++)
	{
		scanf("%d%d",&t1,&t2);
		adde(t1,t2);
	}
	DFS(1,0);
	dep[0]=INF;
	ST();
	int *p;
	for(int i=1;i<=Q;i++)
	{
		p=inp[i];
		scanf("%d%d%d",&p[0],&p[1],&p[2]);
		if(!p[0])
			nset[++nc]=p[2];
	}
	sort(nset+1,nset+1+nc);
	nc=unique(nset+1,nset+1+nc)-nset-1;
	B.TL=1,B.TR=nc;
	InitSeg(1);
	for(int i=1;i<=Q;i++)
	{
		p=inp[i];
		if(!p[0])
		{
			B.Add(p[1],Get(T[p[1]]),-1);
			B.Add(p[1],Get(p[2]),1);
			T[p[1]]=p[2];
		}
		else
		{
			t1=B.Que(p[1],p[2],p[0]);
			if(t1!=-INF)
				printf("%d\n",t1);
			else
				puts("invalid request!");
		}
	}
	return 0;
}

线段树套平衡树维护括号序列

Solution

现在考虑优化的话，主要就是要考虑压缩空间，否则太不友好。注意到，空间之所以那么大，是因为把主席树建在了内层，一个点的权值可能出现在$O(\log n)$棵线段树中，出现一次就至多带来$O(\log n)$个节点，比较浪费。 那么考虑把值域线段树建在外层，那么这一部分的空间就是$O(n)$。考虑如何在内层维护整个树。 用DFS序列应该就不好弄了。。涉及到路径，DFS序似乎就无力了。。。 于是祭出大杀器：括号序！ 一个树的括号序，指的是每个点在进栈的时候放一个左括号，出栈的时候放一个右括号。 然后把一棵树的括号序写下来，会发现一个惊天大秘密：从第一个括号开始，到$pos$的左括号，把匹配的括号删掉，恰好可以得到从根节点到$pos$的路径！ 于是就可做了： 在值域线段树的每个节点$[l,r]$挂一个平衡树，平衡树维护所有值被$[l,r]$覆盖的点的左括号位置和右括号位置。左括号的权值为$1$，右括号为$-1$，这样做一下前缀和，就可以得到根节点到一个点的路径上有多少点的值在$[l,r]$之内了！然后就可以做了。 空间复杂度$O(n \log n)$。

Code

#include "lucida"
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;
const int MAXN=80000+11,INF=0x1f1f1f1f,MAXLOG=20;
int n,w[MAXN],nums[MAXN<<1],nc=0,dep[MAXN];
#define alloc(T,c) (T*)malloc((c)*sizeof(T))
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
namespace treap {
	struct Node *null,**rec,*Me;
	const int P=99929,SIZE=(MAXN<<1)*MAXLOG;
	struct Node {
		Node *son[2];
		int val,cnt,sz,py;
		Node():sz(0),py(P) {
			son[0]=son[1]=0;
			val=-INF;
		}
		Node(int val,int cnt):val(val),cnt(cnt),sz(cnt),py(rand()%P) {
			son[0]=son[1]=null;
		}
		void Up() {
			sz=son[0]->sz+son[1]->sz+cnt;
		}
		void *operator new(size_t) {
			return *rec?*rec--:Me++;
		}
		void operator delete(void *p) {
			*++rec=(Node*)p;
		}
	}**cer=rec=alloc(Node*,SIZE),*eM=Me=alloc(Node,SIZE),*llun=null=new Node;
	struct Treap {
		Node *root;
		void Trans(Node *&pos,int d) {
			Node *s=pos->son[d];
			pos->son[d]=s->son[!d];
			s->son[!d]=pos;
			pos->Up();
			(pos=s)->Up();
		}
		int Adjust(Node *&pos) {
			int d=pos->son[0]->py>pos->son[1]->py;
			return pos->py>pos->son[d]->py?(Trans(pos,d),!d):-1;
		}
		void Fall(Node *&pos) {
			int d=Adjust(pos);
			if(d==-1) {
				delete pos;
				pos=null;
			} else {
				Fall(pos->son[d]);
				pos->Up();
			}
		}
		void Delete(Node *&pos,int val) {
			if(pos->val==val) {
				pos->py=P;
				Fall(pos);
			} else {
				Delete(pos->son[pos->val<val],val);
				pos->Up();
			}
		}
		void Insert(Node *&pos,Node *goal) {
			if(pos==null)
				pos=goal;
			else {
				Insert(pos->son[pos->val<goal->val],goal);
				pos->Up();//adjust不一定会adjust啊...
				Adjust(pos);
			}
		}
		typedef Node *Iter;		
		Treap():root(null){}
		int Rank(int v) {
			Node *pos=root;int res=0;
			while(pos!=null) {
				if(pos->val<=v) {
					res+=pos->son[0]->sz+pos->cnt;
					pos=pos->son[1];
				} else
					pos=pos->son[0];
			}
			return res;
		}
		void Delete(int val) {
			Delete(root,val);
		}
		void Insert(int val,int cnt) {
			Insert(root,new Node(val,cnt));
		}

		
	};
}using treap::Treap;
namespace segtree {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		Treap idx;
		Node() {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Pool=alloc(Node,SIZE);
			return Pool++;
		}
	};
	struct SegTree {
		typedef Node *Iter;
		Node *root;
		int L,R;
		void Build(Node *&pos,int L,int R) {
			pos=new Node;
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
			}
		}
		void Point(Node *pos,int L,int R,int goal,int v,int cnt) {
			if(v>0) pos->idx.Insert(v,cnt);
			else pos->idx.Delete(-v);
			if(L!=R) {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Point(pos->son[0],L,Mid,goal,v,cnt);
				else
					Point(pos->son[1],Mid+1,R,goal,v,cnt);
			}
		}
		SegTree(){}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		void Insert(int pos,int idx,int cnt) {
			Point(root,L,R,pos,idx,cnt);
		}
		void Delete(int pos,int idx) {
			Point(root,L,R,pos,-idx,0);
		}
	};
}using segtree::SegTree;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
namespace _ST_ {
	int mdfs[MAXN<<1],lbd[MAXN],rbd[MAXN],mdc,log_2[MAXN<<1],f[MAXLOG][MAXN<<1];
	void ST() {
		log_2[0]=-1;
		for(int i=1;i<=mdc;++i) {
			f[0][i]=mdfs[i];
			log_2[i]=log_2[i>>1]+1;
		}
		for(int lg=1,elg=log_2[mdc];lg<=elg;++lg)
			for(int pl,pr,i=1,ei=mdc-(1<<lg)+1;i<=ei;++i)
				f[lg][i]=dep[pl=f[lg-1][i]]<dep[pr=f[lg-1][i+(1<<lg>>1)]]?pl:pr;
	}
	int LCA(int p1,int p2) {
		p1=lbd[p1],p2=lbd[p2];
		if(p1>p2) swap(p1,p2);
		int lg=log_2[p2-p1+1],pl,pr;
		return dep[pl=f[lg][p1]]<dep[pr=f[lg][p2-(1<<lg)+1]]?pl:pr;
	}
}
using _ST_::LCA;
int dfs[MAXN<<1],dc,lpt[MAXN],rpt[MAXN],fa[MAXN];
void DFS(int pos) {
	using namespace _ST_;
	dfs[++dc]=pos;lpt[pos]=dc;
	mdfs[++mdc]=pos;lbd[pos]=mdc;
	for(Edge *e=G[pos];e;e=e->pre)
		if(e->to!=fa[pos]) {
			fa[e->to]=pos;
			dep[e->to]=dep[pos]+1;
			DFS(e->to);
			mdfs[++mdc]=pos;
		}
	dfs[++dc]=pos;rpt[pos]=dc;
	rbd[pos]=mdc;
}
SegTree seg;
void Build() {
	DFS(1);
	new(&seg) SegTree(1,nc);
	_ST_::ST();
	for(int i=1;i<=n;++i) {
		seg.Insert(w[i],lpt[i],1);
		seg.Insert(w[i],rpt[i],-1);
	}
}
int Query(int p1,int p2,int K) {
	int lca=LCA(p1,p2);
	K=dep[p1]+dep[p2]-dep[lca]*2+1-K+1;
	if(K<=0)
		return 0;
	else {
		int L=1,R=nc;
		SegTree::Iter pos=seg.root;
		while(L!=R) {
			int Mid=(L+R)>>1;
			Treap &idx=pos->son[0]->idx;
			int d=idx.Rank(lpt[p1])+idx.Rank(lpt[p2])-idx.Rank(lpt[lca])-idx.Rank(lpt[fa[lca]]);
			if(K<=d) {
				R=Mid;
				pos=pos->son[0];
			} else {
				K-=d;
				L=Mid+1;
				pos=pos->son[1];
			}
		}
		return L;
	}
	return 23333;
}
void Change(int pos,int newv) {
	seg.Delete(w[pos],lpt[pos]);
	seg.Delete(w[pos],rpt[pos]);
	w[pos]=newv;
	seg.Insert(w[pos],lpt[pos],1);
	seg.Insert(w[pos],rpt[pos],-1);
}
int main() {
	freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int Q;is>>n>>Q;
	for(int i=1;i<=n;++i) {
		is>>w[i];
		nums[++nc]=w[i];//=i?????????w[i]????
	}
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
	}
	static struct {int k,a,b;}opt[MAXN];
	for(int i=1;i<=Q;++i) {
		is>>opt[i].k>>opt[i].a>>opt[i].b;
		if(!opt[i].k)
			nums[++nc]=opt[i].b;
	}
	sort(nums+1,nums+1+nc);
	nc=unique(nums+1,nums+1+nc)-nums-1;
	for(int i=1;i<=n;++i)
		w[i]=ref(w[i]);
	Build();
	for(int i=1;i<=Q;++i)
		if(opt[i].k) {
			int Ans=Query(opt[i].a,opt[i].b,opt[i].k);
			if(Ans) os<<nums[Ans]<<'\n';
			else os<<"invalid request!"<<'\n';
		} else {
			Change(opt[i].a,ref(opt[i].b));
		}
	return 0;
}