uoj55 紫荆花之恋

Link

Solution

嗯。做法来自Po姐。

紫荆花之恋。我在WC 2014中出的题目，这个题目的核心在于可以意识到替罪羊树这一技巧，能够适用于一切依靠子树大小来维持平衡的结构。那么，它必然也可以被使用于点分治这一结构。那么我们就可以用替罪羊树来维护动态的点分治。当时觉得还挺有意思的，不过现在也已经不怎么研究数据结构了>_>。 --WJMZBMR

支持加点，实时维护$dis(i,j)\le r_i+r_j$的点对数目。 考虑不是动态加点的做法。 （口胡begin） 对树点分治，重心为$p$的一层内，问题变成$dis(i,p)+dis(j,p)\le r_i+r_j$，即$dis(i,p)-r_i \le r_j-dis(j,p)$ 维护一个有序的数组$a[]=\{dis(i,p)-r_i\}$，对于一个新分支，求出$b[]=\{r_j-dis(j,p)\}$。用双指针统计答案，然后把$b[]$取反，将两个表$std::merge$。 （如果我说的有问题欢迎指教。。） （口胡end） 加点的话，要想办法统计一个新的点对答案的贡献，即以从它一直到根节点为LCA的所有合法路径。这样，在每个重心处维护一个$Treap$维护$r_i-dis(i,p)$，然后查询值$dis(j,p)-r_j$在其中的排名即可。 然后复杂度会爆棚，于是借助替罪羊思想，如果一个点点分出来的某个分支的size过大，就重新点分治这棵子树。

Tips

• 在以$p$为重心的一层统计答案的时候要减去LCA不是$p$的点对。一开始想的是减去以$p$的子节点为LCA的路径，，然后发现不一定只有这样的不合法。。于是不可避免地要开两棵$Treap$，设$p$分出的一棵子树为$u$，$u$的另一棵记录的是$p$在$u$内产生的$r_i-dis(i,p)$。由此，统计答案的时候直接减去即可。
• 在重新分治的时候要把$Treap$重新赋值，用filltreap()实现。一开始这个函数的Treap::Insert()操作写在了遍历边的循环里，结果最顶上的点的值没有Insert()进去。。
• TreapNode::cnt++之后，没有立即$TreapNode::up()$
• 维护点分出来的分支的时候只能用平衡树，因为涉及节点的查找和删除操作。
• 千万不要把原树的father和点分分支的uplayer混淆。
• 点分中各种操作都严禁跑出当前一层的点集。
• 一开始的时候std::queue出了问题，调试的时候在那里挂掉。然后还真的研究了很长时间queue的问题。然而弃疗之后发现某个细节写错了，改了之后立即好了。。由此，崩溃的位置不一定是bug的位置。。
• 在Rebuild中，一开始我的filltreap(DyNode::anti)是写在遍历边的循环里的，结果和上面的一样，最顶上的点没有把anti赋值。
• 于是学习Po姐的代码，发现在Rebuild之前可以直接保留这棵子树的anti，因为anti不会随着树的结构改变。于是开心地效仿了，发现立即崩溃。研究了好久才顿悟——在Rebuild之前有垃圾回收，里面的TreapNode等同于已经被析构了，再调用必死啊。还是语言逻辑不好啊。。
• 于是又把代码改成在每层的一开始处理本层的anti，结果崩。苦想，明白了问题：Rebuild(pos)，pos我传的是替罪羊树中的节点编号。它和它的上一层不一定是父子关系。这样filltreap的值就是错的。所以pos应该传这棵子树在原树上的节点编号。
• 倍增LCA支持动态加点操作。
• 替罪羊树只需检测每次加了点的分支。
• 一开始T了，加了fread优化T的更厉害，然后加了fwrite优化，调整了替罪羊树的$\alpha$值，才卡过去。如果看出我的代码复杂度写错，或者有常数的缺陷，欢迎指教。看到BZOJ上%jvcb%跑的那么快简直BUG一样。 upd：发现替罪羊树写错了，改过来之后T飞了，然后有各种卡常数改$\alpha$，结果最后发现是点分治写错了。太愚蠢了。

  Code

  //Code by Lucida
  #include<bits/stdc++.h>
  //#define red(x) scanf("%d",&x)
  #define debug(x) printf(#x"=%d\n",x)
  template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
  template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
  typedef long long LL;
  using std::swap;
  using std::queue;
  using std::set;
  const int MAXN=1e5+100,P=1e7;
  LL last=0;int r[MAXN];
  //IO begin
  const int INBUF=1e7;
  char inbuf[INBUF],*iptr=inbuf,*iptrend=inbuf;
  #define getc() (iptr==iptrend && (iptrend=(iptr=inbuf)+fread(inbuf,1,INBUF,stdin),iptr==iptrend)?EOF:*iptr++)
  inline void red(int &x)
  {
  	static int flag;
  	static char ch;
  	flag=1;
  	while(!isdigit(ch=getc())) if(ch=='-') flag=-1;
  	x=ch-'0';
  	while(isdigit(ch=getc()))
  		(x*=10)+=ch-'0';
  	x*=flag;
  }
  const int OUTBUF=1e7;
  char outbuf[OUTBUF],*optr=outbuf;
  inline void white(LL x)
  {
  	if(x<0) *optr++='-';
  	if(x==0) *optr++='0';
  	if(x)
  	{
  		static char stack[100],*top;
  		for(top=stack;x;x/=10)
  			*top++=(x%10)+'0';
  		while(top!=stack)
  			*optr++=*--top;
  	}
  	*optr++='\n';
  }
  //IO end
  //LCA begin
  namespace fullgraph
  {
  	const int LOG=20;
  	struct Edge{int to,v,pre;}e[MAXN<<1];int id[MAXN],ec=0;
  	inline void Adde(int f,int t,int v)
  	{
  		if(!f || !t) return;//1 0...
  		e[++ec].to=t;e[ec].v=v;e[ec].pre=id[f];id[f]=ec;
  		e[++ec].to=f;e[ec].v=v;e[ec].pre=id[t];id[t]=ec;
  	}
  	int dep[MAXN],dis[MAXN],fa[MAXN][LOG];
  }
  inline void AddNode(int pos,int father,int c)
  {
  	using namespace fullgraph;
  	fa[pos][0]=father;
  	for(int j=1;j<=LOG-1;j++)
  		fa[pos][j]=fa[fa[pos][j-1]][j-1];
  	dep[pos]=dep[father]+1;
  	dis[pos]=dis[father]+c;
  	Adde(pos,father,c);
  }
  inline int LCA(int p1,int p2)
  {
  	using namespace fullgraph;
  	if(dep[p1]<dep[p2]) swap(p1,p2);
  	for(int j=LOG-1;~j;j--)
  		if(dep[fa[p1][j]]>=dep[p2]) p1=fa[p1][j];
  	if(p1==p2) return p1;
  	for(int j=LOG-1;~j;j--)
  		if(fa[p1][j]!=fa[p2][j]) p1=fa[p1][j],p2=fa[p2][j];
  	return fa[p1][0];
  }
  inline int Dist(int p1,int p2)
  {
  	using namespace fullgraph;
  	return dis[p1]+dis[p2]-2*dis[LCA(p1,p2)];
  }
  //LCA END
  //Treap BEGIN
  struct Treap
  {
  	struct TreapNode
  	{
  		TreapNode *son[2];
  		int key,v,sz,cnt;
  		TreapNode(){key=P;}
  		inline void up()
  		{
  			sz=cnt;
  			if(son[0]) sz+=son[0]->sz;
  			if(son[1]) sz+=son[1]->sz;
  		}
  		inline int mkyson()
  		{
  			if(!son[0] && !son[1]) return -1;
  			else return (son[0]?son[0]->key:P)<(son[1]?son[1]->key:P)?0:1;
  		}
  	};
  	static queue<TreapNode*> trash;
  	TreapNode *root;
  	Treap(){root=0;}
  	inline int size(){return root?root->sz:0;}
  	inline TreapNode *newTreapNode(int v)
  	{
  		static TreapNode *cur,*ME=new TreapNode[MAXN<<5],*END=ME+(MAXN<<5);
  		//if(0)
  		if(!trash.empty())
  		{
  			cur=trash.front();
  			trash.pop();
  		}
  		else
  		{
  			if(ME==END)
  				END=(ME=new TreapNode[MAXN<<5])+(MAXN<<5);
  			cur=++ME;
  		}
  		cur->son[0]=cur->son[1]=0;
  		cur->key=rand()%P;cur->v=v;cur->cnt=cur->sz=1;
  		return cur;
  	}
  	inline void deleteTreapNode(TreapNode *cur){trash.push(cur);}
  	inline void trans(TreapNode *&pos,int d)
  	{
  		TreapNode *s=pos->son[d];
  		pos->son[d]=s->son[!d];
  		s->son[!d]=pos;
  		pos->up(),s->up();
  		pos=s;
  	}
  	inline int adjust(TreapNode *&pos)
  	{
  		int mks=pos->mkyson();
  		if((~mks) && pos->key>pos->son[mks]->key)
  		{
  			trans(pos,mks);
  			return !mks;
  		}
  		else return -1;
  	}
  	void Insert(TreapNode *&pos,int v)
  	{
  		if(pos==0) pos=newTreapNode(v);
  		else if(pos->v==v) pos->cnt++,pos->up();//pos->up....??.
  		else
  		{
  			Insert(pos->son[pos->v<v],v),pos->up();
  			adjust(pos);
  		}
  	}
  	inline void Insert(int v){Insert(root,v);}
  	inline int Rnk(int v)//返回不含等于的
  	{
  		TreapNode *pos=root;
  		int res=0;
  		while(pos)
  		{
  			if(pos->v<v)
  			{
  				res+=(pos->son[0]?pos->son[0]->sz:0)+pos->cnt;
  				pos=pos->son[1];
  			}
  			else pos=pos->son[0];
  		}
  		return res;
  	}
  	inline int Access(int v){return size()-Rnk(v);}
  	void clear(TreapNode *&pos)
  	{
  		if(!pos) return;
  		clear(pos->son[0]);
  		clear(pos->son[1]);
  		deleteTreapNode(pos);
  		pos=0;
  	}
  	inline void Clear(){clear(root);}
  };
  queue<Treap::TreapNode*> Treap::trash;
  //Treap END
  //DC BEGIN
  struct DynamicTree
  {
  	static const double lambda=0.88;
  	struct DyNode
  	{
  		Treap rec,anti;
  		set<int> son;
  		int orgroot,node;
  		inline int size(){return rec.size();}
  		//只需检测每次添加了节点的分支。
  	}*tree[MAXN];
  	static queue<DyNode*> recv;
  	inline DyNode *newDyNode(int node,int root)
  	{
  		DyNode *cur;
  		if(!recv.empty()) 
  			cur=recv.front(),recv.pop();
  		else
  		{
  			static DyNode *ME=new DyNode[MAXN<<1];
  			cur=++ME;
  		}
  		cur->node=node;
  		cur->orgroot=root;
  		cur->son.clear();
  		cur->rec.Clear();
  		cur->anti.Clear();
  		return cur;
  	}
  	inline void deleteDyNode(DyNode *cur){recv.push(cur);}
  
  	int f[MAXN],sz[MAXN],tol,uplayer[MAXN];
  	void calcsize(int pos,int from)
  	{
  		using namespace fullgraph;
  		sz[pos]=1;
  		for(int i=id[pos];i;i=e[i].pre)
  		{
  			int u=e[i].to;
  			if(u==from || tree[u]) continue;
  			calcsize(u,pos);
  			sz[pos]+=sz[u];
  		}
  	}
  	int DP(int pos,int from)
  	{
  		using namespace fullgraph;
  		int rs=pos,mi=-1;f[pos]=0;
  		for(int i=id[pos];i;i=e[i].pre)
  		{
  			int u=e[i].to;
  			if(u==from || tree[u]) continue;
  			rs=DP(u,pos);
  			mi=(mi==-1 || f[mi]>f[rs])?rs:mi;
  			chkmx(f[pos],sz[u]);
  		}
  		chkmx(f[pos],tol-sz[pos]);
  		return (mi==-1 || f[mi]>f[pos])?pos:mi;
  	}
  	inline int GC(int root)
  	{
  		using namespace fullgraph;
  		calcsize(root,0);
  		tol=sz[root];
  		return DP(root,0);
  	}
  
  	void filltreap(int pos,Treap &cur,int from,int dist)
  	{
  		using namespace fullgraph;
  		cur.Insert(r[pos]-dist);
  		for(int i=id[pos];i;i=e[i].pre)
  		{
  			int u=e[i].to;
  			if(u==from || tree[u]) continue;
  			filltreap(u,cur,pos,dist+e[i].v);
  		}
  	}
  	int DC(int origin,int from)
  	{
  		using namespace fullgraph;
  		Treap temp;
  		if(from) 
  			filltreap(origin,temp,from,Dist(origin,from));//origin and from gotta be father son
  		int gc;DyNode *cur=newDyNode(gc=GC(origin),origin);
  		tree[gc]=cur;
  		uplayer[gc]=from;
  		cur->anti=temp;
  		cur->rec.Insert(r[gc]);
  		for(int i=id[gc];i;i=e[i].pre)
  		{
  			int u=e[i].to;
  			if(u==from || tree[u]) continue;
  			filltreap(u,cur->rec,gc,e[i].v);
  			cur->son.insert(DC(u,gc));
  		}
  		return gc;
  	}
  	void recycle(DyNode *&cur)
  	{
  		for(set<int>::iterator it=cur->son.begin();it!=cur->son.end();++it)
  			recycle(tree[*it]);
  		deleteDyNode(cur);
  		cur=0;
  	}
  	inline int Rebuild(int pos)
  	{
  		int up=uplayer[pos],org=tree[pos]->orgroot;
  		if(up) tree[up]->son.erase(pos);
  		recycle(tree[pos]);
  		int cur=DC(org,up);
  		if(up) tree[up]->son.insert(cur); 
  		return cur;
  	}
  	void Insert(int pos,int father)
  	{
  		DyNode *cur=newDyNode(pos,pos);
  		tree[pos]=cur;
  		if(father)
  			tree[father]->son.insert(pos);
  		uplayer[pos]=father;
  		int reb=0;
  		for(int i=pos,pre=0;i;pre=i,i=uplayer[i])
  		{
  			int d=Dist(pos,i);
  			last+=tree[i]->rec.Access(d-r[pos]);
  			tree[i]->rec.Insert(r[pos]-d);
  			if(pre)
  			{
  				last-=tree[pre]->anti.Access(d-r[pos]);
  				tree[pre]->anti.Insert(r[pos]-d);
  			}
  			if(pre && ( ((double)tree[pre]->size()/tree[i]->size()) >lambda)) 
  				reb=i;
  		}
  		if(reb)
  			Rebuild(reb);
  	}
  }Tree;
  queue<DynamicTree::DyNode*> DynamicTree::recv;
  //DC END
  void Adjust(int pos,int father,int c)
  {
  	AddNode(pos,father,c);
  	Tree.Insert(pos,father);
  }
  int main()
  {
  	srand(0x1f1f1f1f);
  	int n;red(n),red(n);
  	const int P=1e9;
  	for(int i=1;i<=n;i++)
  	{
  		int a,c;red(a),red(c),red(r[i]);
  		a=a^(last%P);
  		Adjust(i,a,c);
  		white(last);
  	}
  	fwrite(outbuf,1,optr-outbuf,stdout);
  	return 0;
  }