uoj 122 树的计数

发表于 | 更新于

Link

给定 序和 序，求同时满足的期望树高 首先重标号，把 序变成bfs[i]==ibfs[i]==i的形式 序上的一个区间对应着树的一层，相当于在 序上切几下，构成满足 序的树

Solution 形象的复杂做法

可以发现， 序上相邻的两个点的关系是不会影响其它点之间的关系的，所以就只需要看每对相邻点a,ba,b对答案的贡献即可。记点pp在 序中的对应位置为ref[p]ref[p] aa和bb要么是同一层，要么aa在bb的上一层 如果aa在bb的上一层则有两种情况 否则也有两种情况 讨论

  1. ref[a]>ref[b]ref[a]>ref[b]，则dep[a]+1==dep[b]dep[a]+1==dep[b] 如果aa,bb在同一层，那么一定有ref[a]<ref[b]ref[a]< ref[b]
  2. ref[a]<ref[b]ref[a]< ref[b] 1.ref[a]+1==ref[b]ref[a]+1==ref[b] 可以看出，两种深度关系都存在符合的情况，那就只看会对答案产生影响的dep[a]+1==dep[b]dep[a]+1==dep[b]的情况 首先排除掉Case #2，那么只需要探究Case #1的成立条件即可 还是把Case #1画得更具体一些吧 aa是上层的最后一个点，bb是下层的第一个点，且bb是aa的子节点 那么ref[a]ref[a]之前的点的深度都≤dep[a]\le dep[a]，ref[b]ref[b]之后的所有比bb深的点与bb的LCA必然是aa，即对于bb与∀p,dep[p]≥dep[b]\forall p,dep[p]\ge dep[b]，ref[b],ref[p]ref[b],ref[p]之间没有和aa深度相同的点。 当然，这两个条件对于depdep相等的Case #1同时适用，所以对答案的贡献是0.50.5。 2.ref[a]+1<ref[b]ref[a]+1< ref[b]，则dep[a]==dep[b]dep[a]==dep[b] 假设dep[a]+1==dep[b]dep[a]+1==dep[b]，只能是Case #1。而Case #1中a,ba,b在 序中也一定相邻，所以不符合

Code 第一种实现

最值使用ST表查询，用二分查找来寻找最后一个比bb大的数字，复杂度O(nlogn)O(n\log n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define putd(x) printf("%.3lf",x)
typedef long long int64;
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;}
const int MAXN=2e5+11,LOG=20,INF=0x1f1f1f1f;
using std::max;
using std::min;
namespace _SparseTable_
{
	struct Node
	{
		int mx,mn;
		Node(){mx=-INF,mn=INF;}Node(int mx,int mn):mx(mx),mn(mn){}
		Node &operator =(int x){mx=mn=x;return *this;}
	}f[MAXN][LOG];
	Node operator +(Node a,Node b){return Node(max(a.mx,b.mx),min(a.mn,b.mn));}
	int log_2[MAXN];
	void ST(int a[],int n)
	{
		log_2[0]=-1;
		for(int i=1;i<=n;++i)
		{
			f[i][0]=a[i];
			log_2[i]=log_2[i>>1]+1;
		}
		for(int j=1;j<=log_2[n];++j)
			for(int i=1;i+(1<<j)-1<=n;++i)
				f[i][j]=f[i][j-1]+f[i+(1<<j>>1)][j-1];
	}
	Node RMQ(int l,int r)
	{
		if(l>r) return Node();
		int lo=log_2[r-l+1];
		return f[l][lo]+f[r-(1<<lo)+1][lo];
	}
	int Find(int x,int l,int r)
	{
		int L=l-1,R=r;
		while(L!=R)
		{
			int Mid=(L+R+1)>>1;
			if(RMQ(Mid,r).mx>x) L=Mid;
			else R=Mid-1;
		}
		return L==l-1?-1:L;
	}
}using namespace _SparseTable_;
int main()
{
	static int ref[MAXN],dfs[MAXN],bfs[MAXN];
	int n;get(n);
	for(int i=1;i<=n;++i) get(dfs[i]);
	for(int i=1;i<=n;++i) get(bfs[i]);
	double Ans;
	if(n==1)
		Ans=1;
	else
	{
		Ans=2;
		for(int i=1;i<=n;++i) ref[bfs[i]]=i;
		for(int i=1;i<=n;++i) dfs[i]=ref[dfs[i]],bfs[i]=i;
		for(int i=1;i<=n;++i) ref[dfs[i]]=i;
		ST(dfs,n);
		for(int i=2;i<n;++i)
		{
			int a=i,b=i+1;
			if(ref[a]>ref[b]) 
				Ans+=1;
			else if(ref[a]+1==ref[b] && RMQ(1,ref[a]).mx<=a && RMQ(ref[b],Find(b,ref[b],n)).mn>a) 
				Ans+=0.5;
		}	
	}
	//putd(Ans-0.001),putchar('\n');
	putd(Ans),putchar('\n');
	//putd(Ans+0.001),putchar('\n');
	return 0;
}

Code 第二种实现

aa是上层的最后一个点，bb是下层的第一个点，且bb是aa的子节点

条件的另一种判断方法： 序中bb之后的所有点，在 序中组成恰好连续的一段，那么也完全可以不受bb的影响。 首先这个结论是正确的，然后假设存在不连续的一段且可以不受bb的影响，则有 看了一节课不明白 以后再研究吧。 见黄学长的提交here

Solution 抽象的简单做法

根据一些类似的分析可以得到下面三个约束条件

  1. 节点11单独一层
  2. 对于连续的一层，在 序列中对应一段，在 序列中ref[l]<ref[l+1]<...<ref[r]ref[l]< ref[l+1]< ...< ref[r]
  3. dep[dfs[i+1]]≤dep[dfs[i]]+1dep[dfs[i+1]]\le dep[dfs[i]]+1

把dep[]dep[]差分一下得到数组d[]d[]，可以把以上三个条件重新写出来

  1. d[1]==1,d[2]==1d[1]==1,d[2]==1
  2. ref[i]>ref[i+1]ref[i]> ref[i+1],则d[i+1]==1d[i+1]==1
  3. dfs[i+1]>dfs[i]dfs[i+1]> dfs[i]，则∑j=dfs[i]+1dfs[i+1]d[j]≤1\sum\limits_{j=dfs[i]+1}^{dfs[i+1]}d[j]\le 1

前两个很好处理,现在看第三个 如果取值为00，那么dfs[i]+1...dfs[i+1]dfs[i]+1...dfs[i+1]都是一层的。这个条件不需要任何前提就可以满足，所以不用管。 如果取值为11，那就看这些变量里有没有被限制为11的，如果有，其它的只能为00，否则，其它的都是0.50.5 被限制为11的只会有一个，因为dfs[i]dfs[i]和dfs[i+1]dfs[i+1]的深度相差最多为11，中间一段连续的 序的深度变化也至多为11。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define putd(x) printf("%.3lf",x)
typedef long long int64;
using std::partial_sum;
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;}
const int MAXN=2e5+11;
const double eps=1e-7;
inline int fcmp(const double &x){return -eps<x && x<eps?0:(x<0?-1:1);}
int main()
{
	freopen("input","r",stdin);
	static int ref[MAXN],dfs[MAXN],bfs[MAXN],limit[MAXN],tag[MAXN];
	static double d[MAXN];
	int n;get(n);
	for(int i=1;i<=n;++i) get(dfs[i]);
	for(int i=1;i<=n;++i) get(bfs[i]);
	for(int i=1;i<=n;++i) ref[bfs[i]]=i;
	for(int i=1;i<=n;++i) dfs[i]=ref[dfs[i]],bfs[i]=i;
	for(int i=1;i<=n;++i) ref[dfs[i]]=i;	
	d[1]=d[2]=1;
	for(int i=3;i<=n;++i)
		if(ref[i-1]>ref[i])
			d[i]=1;
	partial_sum(d+1,d+1+n,limit+1);
	for(int i=2;i<=n;++i)
		if(dfs[i-1]<dfs[i] && limit[dfs[i]]-limit[dfs[i-1]])
			tag[dfs[i-1]+1]++,tag[dfs[i]+1]--;
	partial_sum(tag+1,tag+1+n,tag+1);
	for(int i=1;i<=n;++i)
		if(!fcmp(d[i]) && !tag[i]) 
			d[i]=0.5;
	partial_sum(d+1,d+1+n,d+1);
    //putd(d[n]-0.001),putchar('\n');
	putd(d[n]),putchar('\n');
    //putd(d[n]+0.001),putchar('\n');
	return 0;
}