10707. Count on a tree II - #include <Seter> - using namespace Orz;

10707. Count on a tree II

Seter posted @ 2012年4月07日 07:31 in SPOJ with tags Classical ChairAlgorithm , 5572 阅读

http://www.spoj.pl/problems/COT2/

ID DATE USER PROBLEM RESULT TIME MEM LANG
6808392 2012-04-08 13:39:25 Seter Count on a tree II accepted
edit  run
30.84 18M

C++

4.0.0-8

YY了个做法。。。但是感觉写起来会飘。。。所以先发个题解吧。。。这个东西强制在线的话复杂度实际上会不对。。。所以BZOJ上那个对不住大家了。。。

麻。。。由于是YY的。。。不保证细节正确性。。。希望大家发现错误后告诉我。。。


首先如果在一条链上的话,做法就很多了。最简单的做法是离线询问,然后从左到右加入点Ai时就是处理出Ai的上次出现位置j然后给j+1...i加上1,然后处理所有右端点为i的询问。

放到树上的话可以发现,如果这棵树像一条链,可能就可以用上述方法了。否则这棵树的高度一定不会太高,就可以暴力。

具体做法如下:

预处理:称一次操作为去除所有叶子,执行A=sqrtN次操作,显然第i次操作删去的叶子数大于等于第i+1次,然后观察此时的叶子数K,如果K>=N/A,那么已经删去的节点数就是O(KA)=O(N)级别,树高就是O(A)级别,暴力之,否则继续。

我们将删去的点集记作S,剩下的树记为T。容易发现S是一个由一些高为A的树们组成的森林,且根连到T上。

开始对于询问(u,v)分情况讨论。

1.u,v在S中的同一棵树上。由于树高为A,暴力之。

2.u,v都在T中。可以证明,一定存在某个叶子,当以这个叶子为根时,根...u...v是一条链。由于叶子最多只有N/A=aqrtN个于是我们可以枚举叶子,然后每次用dfs在NlgN时间内离线弄出这些答案。

3.u,v都在S中,但不在同一棵树上。那么就可以表示为u...U...V...v,其中U,V分别是u,v向上碰到的第一个在T中的点。由于u...U,V...v的长度是O(A)的,我们可以在处理出U...V的答案后对于这两条尾巴上的每一个数暴力弄。

可以发现加入一个数的时候如果U...V上没有出现过这个数且在之前没有加入过,则答案+1,这个在DFS的时候可以顺便弄出来,只需要记录每个数上次在哪里出现就可以了那么我们只要处理出U...V上各个数出现次数就可以了,这里我用了主席树。。。(我懒得改了)。

4.u,v一个在S中,一个在T中。这个和上面那个一样。

然后来分析复杂度。暴力的复杂度是O(MA),否则复杂度是O((N/A)NlgN+MA)=O((NlgN+M)sqrtN)。

可以让理论复杂度再优一点么?可以发现暴力的那个总是会快(因为暴力需要原图满足特殊性质),所以我们只要考虑后面那个就可以了。令(N/A)NlgN=MA,解得A=sqrt(N^2lgN/M),总复杂度就是O(sqrt(N^2lgNM))=O(5e7),可以承受。

标程为了在线,用主席树存下所有叶子为根时的东西。为了不MLE,没有将K的阈值设为N/A而是设为了20。这会导致一个点上连出20条长链时复杂度退化为O(NM),但是只要不是树和询问都针对它精心构造的话还是很快的。

我搞了半天,各种TLE,最后消去200次K的阈值设为50终于过了,囧,SPOJ太慢了。


可以发现这个算法非常NB。。。在一条链上可以搞出来且支持快速在头尾加一个数的东西都可以在这个上面做,不过由于要离线询问,可能难以支持修改。。。嘛,大家可以想想树上小Z的袜子怎么弄。。。(当然曼哈顿MST也能做。。)

对了。。。我们给这个算法起个牛X点的名字。。。就叫主席算法好了。。。ChairAlgorithm。。。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define N 40000
struct EDGE{EDGE*next;int y;};
inline int getint(){
	int re;char ch;
	while(!isdigit(ch=getchar()));re=ch-48;
	while(isdigit(ch=getchar()))re=re*10+ch-48;
	return re;
}using namespace std;
int n,m,num[N],que[N];bool v[N];
namespace COT2{
	EDGE*map[N],st[N<<1],*stp=st;
	int a[N];
	inline void ADDEDGE(int x,int y){
		stp->next=map[x];num[(map[x]=stp++)->y=y]++;
		stp->next=map[y];num[(map[y]=stp++)->y=x]++;
	}inline void Init(){
		int i=n=getint();m=getint();
		static pair<int,int>R[N];
		for(i=-1;++i!=n;)R[i]=make_pair(getint(),i);
		sort(R,R+n);
		for(a[R[0].second]=i=0;++i!=n;)a[R[i].second]=a[R[i-1].second]+(R[i].first!=R[i-1].first);
		while(--i)ADDEDGE(getint()-1,getint()-1);
	}
}namespace Prep{
	int f[N],d[N];
	void Init(int x){for(EDGE*p=COT2::map[x];p;p=p->next)if(f[x]!=p->y)d[p->y]=d[f[p->y]=x]+1,Init(p->y);}
	inline int Stupid(int x,int y){
		if(d[x]>d[y])swap(x,y);
		int px=x,py=y,ans=0;
#define Jump(x) ans+=!v[COT2::a[x]],v[COT2::a[x]]=1,x=f[x]
		while(d[x]!=d[y])Jump(y);
		while(x!=y)Jump(x),Jump(y);
		ans+=!v[COT2::a[x]];
		while(px!=x)v[COT2::a[px]]=0,px=f[px];
		while(py!=y)v[COT2::a[py]]=0,py=f[py];
		return ans;
	}
}namespace BIT{
	int a[N];
	inline void I(int x,int y){for(;x;x-=x&-x)a[x]+=y;}
	inline int S(int x){int ans=0;for(;x<=n;x+=x&-x)ans+=a[x];return ans;}
}namespace CT{
	struct ChairTree{ChairTree*c[2];int v;}*T[N],sT[N*18],*stt=sT,*tmp;
	ChairTree*Build(int l,int r){
		ChairTree*ND=stt++;
#define mid (l+r>>1)
		if(l+1!=r)ND->c[0]=Build(l,mid),ND->c[1]=Build(mid,r);
		return ND;
	}ChairTree*I(ChairTree*R,int l,int r,int x){
		ChairTree*ND=stt++;ND->v=R->v+1;if(l+1==r)return ND;
		if(x<mid)ND->c[0]=I(R->c[0],l,mid,x),ND->c[1]=R->c[1];
		else ND->c[0]=R->c[0],ND->c[1]=I(R->c[1],mid,r,x);
		return ND;
	}inline int Q(ChairTree*R,int x){
		int l=0,r=n;
		while(l+1!=r)if(x<mid)r=mid,R=R->c[0];
		else l=mid,R=R->c[1];
		return R->v;
	}
}namespace Solve{
	struct QUE{QUE*next;int u,v,ans;}*Q[N],sq[100000],*stq=sq;
	int f[N],d[N],D[N],b[N];
	inline int fa(int x){while(x!=f[x])x=f[x];return x;}
	inline void ADDQUERY(int u,int v){
		int fu=fa(u),fv=fa(v);
		if(fu==fv){stq++->ans=Prep::Stupid(u,v);return;}
		if(d[v])swap(u,v),fv=fu;stq->u=u;stq->v=v;stq->next=Q[fv];Q[fv]=stq++;
	}inline int Calc(int x,int U,int V){
		int a=0;
		while(d[x]){
			a+=(!v[COT2::a[x]])&&(CT::Q(CT::T[U],COT2::a[x])==CT::Q(CT::T[V],COT2::a[x]))&&(COT2::a[x]!=COT2::a[U]);
			v[COT2::a[x]]=1;x=f[x];
		}return a;
	}inline void Clean(int x){while(d[x])v[COT2::a[x]]=0,x=f[x];}
	void GO(int x,int fx){
		int px=b[COT2::a[x]];BIT::I(px,-1);BIT::I(b[COT2::a[x]]=D[x]=fx==-1?1:D[fx]+1,1);
		for(QUE*p=Q[x];p;p=p->next)if(!p->ans){
			int fu=fa(p->u);if(!D[fu])continue;
			p->ans=BIT::S(D[fu])+Calc(p->u,fu,x)+Calc(p->v,fu,x);
			Clean(p->u);Clean(p->v);
		}for(EDGE*p=COT2::map[x];p;p=p->next)if(!d[p->y]&&p->y!=fx)CT::T[p->y]=CT::I(CT::T[x],0,n,COT2::a[p->y]),GO(p->y,x);
		BIT::I(b[COT2::a[x]]=px,1);BIT::I(D[x],-1);D[x]=0;
	}inline bool Run(){
		int i=n,b=-1,e=0;
		while(i--)if(num[f[i]=i]==1)d[que[e++]=i]=1;
		while(d[que[++b]]&&b!=e)for(EDGE*p=COT2::map[que[b]];p;p=p->next)if(num[p->y]!=1&&--num[f[que[b]]=p->y]==1){
			que[e++]=p->y;
			if(d[que[b]]!=200)d[p->y]=d[que[b]]+1;
		}if(e==b||e-b>50)return 1;
		for(i=m;i--;)ADDQUERY(getint()-1,getint()-1);
		while(e--!=b)CT::stt=CT::tmp,CT::T[que[e]]=CT::I(CT::sT,0,n,COT2::a[que[e]]),GO(que[e],-1);
		while(++i!=m)printf("%d\n",sq[i].ans);
		return 0;
	}
}
int main(){
	COT2::Init();Prep::Init(0);
	CT::Build(0,n);CT::tmp=CT::stt;if(Solve::Run())while(m--)printf("%d\n",Prep::Stupid(getint()-1,getint()-1));
	return 0;
}
By Seter
  • 无匹配
fotile 说:
2012年4月07日 14:45

噗..好像又开了新tag

fotile 说:
2012年4月07日 14:47

顺带一提STD基本就是这个方法

MyIdea 说:
2012年5月18日 10:01

感觉是树块剖分上的函数式线段树

MyIdea 说:
2012年5月19日 10:19

这个题好像不需要用主席树.......还有树上莫队算法已经有了......您可以参考一下.......roosephu已经用莫队算法过了COT2........不过我用的是主席算法.......但是好像不需要主席树?

fotile13 说:
2012年5月19日 10:48

树上离线当然可以各种搞..
但请注意在内存允许的情况下这个方法是可以在线的..

Avatar_small
Seter 说:
2012年5月19日 13:34

的确不需要。。。我写着写着突然忘了。。傻缺了。。。

Avatar_small
Seter 说:
2012年5月19日 13:36

我写这篇blog的时候还记得的,所以写了个“这个在DFS的时候可以顺便弄出来”,结果写程序还以为自己弄错算法了,然后一想主席树也能弄,就傻缺了。。。

MyIdea 说:
2012年5月19日 14:17

您也是喜欢先写题解在码代码么

MyIdea 说:
2012年5月19日 15:07

那样的话是不是会多出一个log(n)?

Avatar_small
Seter 说:
2012年5月20日 11:45

只有这题是这样的。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee