This is not the end.

0%

析合树

Posted on

定义 & 结构

连续段

  • 对于一个排列$A$，我们定义$[l,r]$是连续段，当且仅当这个区间的值域也是连续的一段。即，不存在$x,y,z$，$x,y\in [l,r]\wedge z\not\in [l,r]\wedge A_x < A_z < A_y$。也等价于$\max \{ A_k \mid k\in [l,r] \} - \min \{ A_k \mid k\in [l,r] \} = r-l$。
  • 连续段有一个很好的性质：考虑两个相交且不互相包含的连续段$x,y$，总有$x\cup y$、$x\cap y$、$x\setminus (x \cap y)$、$y\setminus (x\cap y)$是连续段。

本原连续段

  • 如果对于某一个连续段$[l,r]$，不存在另外任意一个连续段与它有交且不包含，那么我们称这个连续段为本原连续段。
  • 由定义可以看出来，所有的本原连续段构成树形结构，每一个点的父亲是包含它的、长度最短的本原连续段。

析点、合点

考虑某一个本原连续段的儿子集合：

  • 合点
    • 如果这些儿子中某相邻的两个拼起来是连续段，那么这点的任意若干个位置连续的儿子拼起来得到的一定是连续段。我们称这样的点是合点。
    • 合点至少有两个儿子。
    • 一种证明方法是这样的：
      • 假设儿子序列的长度为$n$，枚举这个序列的非平凡连续段（长度不为 $1$ 或者 $n$），那么所有的连续段的并一定是整个序列，并且序列中的每一个点都作为若干个非平凡连续段的交出现——否则就会出现非平凡本原连续段，这是不符合定义的。
      • 这也就意味着，$[1,n)$的每一个点至少是一个非平凡连续段的左端点，$(1,n]$的每一个点至少是一个非平凡连续段的右端点。
      • 证明 $[l,r]$ 是连续段：把以$l,l+1,l+2\cdots n-1$为左端点的非平凡连续段取并就得到$[l,n]$，把以$r,r-1,\cdots 2$为右端点的非平凡连续段取并得到$[r,1]$，再把$[l,n]$和$[1,r]$取交就可以了。
  • 析点
    • 任意两个相邻的儿子拼起来都不是连续段。我们称这样的点为析点。
    • 析点至少有四个儿子。
  • 特别地，叶子节点没有儿子，我们认为叶子节点是合点。整棵树一定恰好包含$n$个叶子节点。

另外还有一个结论：一个形态合法（包含$n$个叶子节点，点有析点和合点两种，析点至少有四个儿子，合点至少有两个儿子）的析合树唯一对应到一个集合$I$，$I$中所有的区间都是连续段并且不在$I$中的所有区间都不是连续段，并且一定可以构造出一个排列它的连续段集合是$I$。

构建方法 - 0

下面是一种空间 $O(n\log n)$，时间 $O(n\log n)$ 的构建方法。

从$[1,n]$开始递归建树。假设当前的区间是$[l,r]$，我们需要找出这个点的儿子是哪些区间，并且还需要判断这个点是析点还是合点。

首先，找出最大的$y\in [l,r)$满足$[l,y]$是连续段，找出最小的$x\in (l,r]$满足$x$是连续段。

如果$x\le y+1$，那么当前点是合点，否则，当前点是析点。

如果当前点是析点：$[l,y]$就是当前点的第一个儿子。然后再找$[y+1,r)$最靠右的$y’$满足$[y+1,y’]$是连续段段，则$[y+1,y’]$是第二个儿子。以此类推可以找出当前点所有的儿子。

如果当前点是合点：$[l,x-1]$是当前点的第一个儿子。然后找$[x’,y+1]$（注意边界不是$r$！）最靠左的$x’$满足$[x’,r]$是连续段，则$[x,x’-1]$是第二个儿子。以此类推。最后一个儿子是$[y+1,r]$。

最后还剩一个问题：如何对于$[l,r]$，找出最靠右的$x$满足$[l,x]$是连续段。

一个区间$[l,r]$是连续段等价于$\sum_{i\in [1,n)} [p_i \in [l,r] \vee p_{i+1} \in [l,r] ] = r-l $，其中$p_i$表示$i$这个值在排列中出现的位置。这个可以提前用扫描线+主席树预处理出来，查询的时候就是查询第$l$棵线段树上$r$左侧的最靠右的$1$的位置。

jzoj6202

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define PII pair<int,int>
#define MP make_pair
#define fir first
#define sec second
#define PB push_back
#define db long double
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=2e5+10,M=N*30;
template <class T> inline void cmax(T &x,T y) { if(y>x) x=y; }
template <class T> inline void cmin(T &x,T y) { if(y<x) x=y; }
int A[N>>1],P[N>>1],n;
struct Tree {
	int mi[M],tag[M];
	int ls[M],rs[M],ncnt;
	void init() { mi[0]=1e9; }
	void add(int c,int t) { mi[c]+=t,tag[c]+=t; }
	void push_up(int c) { mi[c]=min(mi[ls[c]],mi[rs[c]])+tag[c]; }
	int cpy(int c) {
		int u=++ncnt;
		ls[u]=ls[c],rs[u]=rs[c];
		mi[u]=mi[c],tag[u]=tag[c];
		return u;
	}
	int ql,qr,qt;
	void build(int l,int r,int &c) {
		c=++ncnt;
		if(l==r) return;
		int mid=l+r>>1;
		build(l,mid,ls[c]),build(mid+1,r,rs[c]);
	}
	void update(int l,int r,int c1,int &c2) {
		c2=cpy(c1);
		if(ql<=l&&qr>=r) return add(c2,qt);
		int mid=l+r>>1;
		if(ql<=mid) update(l,mid,ls[c1],ls[c2]);
		if(qr>mid) update(mid+1,r,rs[c1],rs[c2]);
		push_up(c2);
	}
	int query(int l,int r,int c,int tg) {
//		printf("%d %d\n",mi[c],tg);
		if(mi[c]+tg>1) return n+1;
		if(l==r) return l;
		int mid=l+r>>1; tg+=tag[c];
		if(mi[ls[c]]+tg>1) return query(mid+1,r,rs[c],tg);
		return query(l,mid,ls[c],tg);
	}
	int Query(int l,int r,int c,int tg) {
//		printf("%d %d %d\n",l,r,tg);
		if(ql<=l&&qr>=r) return query(l,r,c,tg);
		int mid=l+r>>1,ans=n+1; tg+=tag[c];
		if(ql<=mid) cmin(ans,Query(l,mid,ls[c],tg));
		if(qr>mid) cmin(ans,Query(mid+1,r,rs[c],tg));
		return ans;
	}
	int rt[N];
	int Q(int l,int r) { ql=l,qr=r; return Query(1,n,rt[r],0); }
	void predo() {
		init();
		build(1,n,rt[0]);
		for(int i=1;i<=n;++i) P[A[i]]=i;
		for(int i=1;i<=n;++i) { // r=i
			ql=1,qr=i,qt=1; update(1,n,rt[i-1],rt[i]);
			if(A[i]>1&&P[A[i]-1]<i) ql=1,qr=P[A[i]-1],qt=-1,update(1,n,rt[i],rt[i]);
			if(A[i]<n&&P[A[i]+1]<i) ql=1,qr=P[A[i]+1],qt=-1,update(1,n,rt[i],rt[i]);
		}
	}
}trl,trr;
int lv[N],rv[N],ty[N],ncnt;
int dep[N],p[N][19];
int pos[N];
int Q1(int l,int r) { int ans=n+1-trl.Q(n-r+1,n-l+1); return ans; }
int Q2(int l,int r) { int ans=trr.Q(l,r); return ans; }
void build(int l,int r,int f) {
	int c=++ncnt; p[c][0]=f; dep[c]=dep[f]+1;
	for(int j=1;j<=18;++j) p[c][j]=p[p[c][j-1]][j-1];
	lv[c]=l,rv[c]=r;
//	printf("%d: %d %d  fa = %d\n",c,l,r,f);
	if(l==r) {
		ty[c]=0; pos[l]=c;
		return;
	}
	int y=Q1(l,r-1),x=Q2(l+1,r); // [l,y], [x,r]
//	printf(" [l,y]: %d [r,x]: %d %d\n",y,x,y<x-1);
	if(y<x-1) {
		ty[c]=1; build(l,y,c);
		while(y<r) {
			int z=Q1(y+1,r); build(y+1,z,c);
			y=z;
		}
	}
	else {
		ty[c]=0; build(l,x-1,c);
		while(true) {
			int z=Q2(x+1,r);
			if(z==n+1||z>y+1) { build(x,r,c); break; }
			build(x,z-1,c);	x=z;
		}
	}
}
struct seg {
	int l,r;
	seg(int l=0,int r=0): l(l),r(r) {}
	friend bool operator < (seg A,seg B) { return A.r-A.l<B.r-B.l; }
};
seg Query(int l,int r) {
	if(l==r) return seg(l,r);
	int x=pos[l],y=pos[r];
	if(dep[x]<dep[y]) swap(x,y);
	for(int j=18;j>=0;--j) if(dep[x]-(1<<j)>=dep[y]) x=p[x][j];
	for(int j=18;j>=0;--j) if(p[x][j]!=p[y][j]) x=p[x][j],y=p[y][j];
	if(ty[p[x][0]]) return seg(lv[p[x][0]],rv[p[x][0]]);
	return max(seg(lv[y],rv[x]),seg(lv[x],rv[y]));
}
int main() {
//	freopen("interval1.in","r",stdin);
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	rd(n);
	for(int i=1;i<=n;++i) rd(A[i]);
	trr.predo();
	reverse(A+1,A+n+1);
	trl.predo();
//	int q; rd(q);
//	while(q--) {
//		int l,r; rd(l),rd(r);
//		printf("mxr = %d  minl =%d\n",Q1(l,r),Q2(l,r));
//	}
	
	
	build(1,n,0);
	int q,l,r; rd(q);
	while(q--) {
		rd(l),rd(r);
		seg ans=Query(l,r);
		printf("%d %d\n",ans.l,ans.r);
	}
	return 0;
}

构造方法 - 1

参考 OI-wiki

下面介绍一种空间 $O(n)$，时间 $O(n\log n)$ 的构造方法。

设 $L_i$ 为最小的 $l$ 满足 $[l,i]$ 为连续段。

增量法，用一个栈维护已经处理过的元素构成的析合树森林。具体来说，处理完前 $i$ 个元素之后，栈中存储了 $[L_i,i], [L_{L_i-1}, L_i - 1], [L_{L_{L_{L_i-1}}-1},L_{L_{L_i-1}}-1] \cdots$ 这些区间的析合树。

新加入一个结点（或者一个子树的根），可能的情况有：

  • 栈顶元素是合点，并且新加入的结点可以作为栈顶元素的儿子
    • 弹出栈顶元素，将新加入的点加入栈顶元素的儿子集合，再尝试插入栈顶元素
  • 新加入的结点和栈顶元素构成了合点
    • 弹出栈顶元素，新建一个合点，把新加入的结点和栈顶元素设置成它的儿子，再尝试插入新建的合点
  • 新加入的元素和栈顶部的若干个元素一起构成了析点
    • 弹出涉及到的栈中元素，新建一个析点，把新加入的结点和涉及到的栈中元素都设置成它的儿子，再尝试插入新建的析点
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// GalaxyOJ 2121. 简单数据结构题 (2020联测#6)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=3e5+10,mod=998244353;
int p[N],pos[N],n,K;
#define ls (c<<1)
#define rs (c<<1|1)
int mxv[N*4],tg[N*4];
void add(int c,int t) { mxv[c]+=t,tg[c]+=t; }
void push_down(int c) {	if(tg[c]) add(ls,tg[c]),add(rs,tg[c]),tg[c]=0; }
void push_up(int c) { mxv[c]=max(mxv[ls],mxv[rs]); }
void build(int l,int r,int c) {
	if(l==r) return (void)(mxv[c]=l);
	int mid=l+r>>1;
	build(l,mid,ls),build(mid+1,r,rs);
	push_up(c);
}
int ql,qr;
void upd(int l,int r,int c) {
	if(ql<=l&&qr>=r) return add(c,1);
	int mid=l+r>>1; push_down(c);
	if(ql<=mid) upd(l,mid,ls);
	if(qr>mid) upd(mid+1,r,rs);
	push_up(c);
}
int Q(int l,int r,int c) {
	//cout<<"Q:"<<l<<' '<<r<<' '<<c<<':'<<mxv[c]<<endl;
	if(r<=qr) {
		if(mxv[c]<qr) return 0;
		if(l==r) return l;
		int mid=l+r>>1; push_down(c);
		int tmp=Q(l,mid,ls);
		return tmp?tmp:Q(mid+1,r,rs);
	}	
	int mid=l+r>>1; push_down(c);
	if(qr<=mid) return Q(l,mid,ls);
	else {
		int tmp=Q(l,mid,ls);
		return tmp?tmp:Q(mid+1,r,rs);
	}
}
bool jud(int l,int r,int c) {
	if(mxv[c]<qr) return 0;
	if(l==r) return 1;
	int mid=l+r>>1; push_down(c);
	if(ql<=mid) return jud(l,mid,ls);
	else return jud(mid+1,r,rs);
}
bool jud(int x) {
	ql=x;
	return jud(1,n,1);
}

vector<int> son[N<<1];
void addson(int f,int x) {
	son[f].PB(x);
}
int st[N<<1],top,ncnt;
int lv[N<<1],rv[N<<1],typ[N<<1],hp[N<<1];
void build() {
	build(1,n,1);
	for(int i=1;i<=n;++i) {
	//	cerr<<i<<endl;
		if(p[i]>1&&pos[p[i]-1]<i) {
			ql=1,qr=pos[p[i]-1];
			upd(1,n,1);
		}
		if(p[i]<n&&pos[p[i]+1]<i) {
			ql=1,qr=pos[p[i]+1];
			upd(1,n,1);
		}
		qr=i; int lb=Q(1,n,1);
		int now=++ncnt;
		lv[now]=rv[now]=i,typ[now]=0;
	//	cout<<i<<' '<<lb<<endl;
		while(top&&lv[now]>lb) {
		//while(top&&lv[st[top]]>=lb) {
		//	cout<<now<<' '<<lb<<' '<<top<<endl;
			if(typ[st[top]]&&jud(hp[st[top]])) {
			//	cout<<"HERE 1 "<<endl;
				rv[st[top]]=i,addson(st[top],now);
				now=st[top--];
			}
			else if(jud(lv[st[top]])) {
			//	cout<<"HERE 2 "<<endl;
				int cur=++ncnt;
				typ[cur]=1,addson(cur,st[top]),addson(cur,now);
				lv[cur]=lv[st[top]],rv[cur]=i,hp[cur]=lv[now],
				top--,now=cur;
			}
			else {
			//	cout<<"HERE 3 "<<endl;
				int cur=++ncnt;
				addson(cur,now);
				do addson(cur,st[top]),lv[cur]=lv[st[top]];
				while(top&&!jud(lv[st[top--]]));
				typ[cur]=0,rv[cur]=i;		
				now=cur;
			}
		}
		st[++top]=now;
	}
}
namespace gao {
	vector<int> len;
	void ad(int x) { len.PB(x); }
	int sol() {
		int j=-1,tot=0,ans=0;
		for(int i=0;i<len.size();++i) {
			while(j+1<len.size()&&tot<K)
				++j,tot+=len[j];
			ans=(ans+1ll*((int)len.size()-1-j)*(len.size()-j)/2%mod*i%mod)%mod;
			tot-=len[i];
		}
		len.clear();
		return ans;
	}
}
int main() {
//	freopen("ex_data1.in","r",stdin);
	rd(n),rd(K);
	for(int i=1;i<=n;++i) rd(p[i]),pos[p[i]]=i;
	build();
//	cerr<<"OK"<<endl;
	int ans=0;
	for(int u=1;u<=ncnt;++u) if(typ[u]) {
		//printf("%d (%d, %d) : ",u,lv[u],rv[u]);
		for(int j=0;j<son[u].size();++j) gao::ad(rv[son[u][j]]-lv[son[u][j]]+1); //,printf("(%d, %d) ",lv[son[u][j]],rv[son[u][j]]);
		//puts("");
		ans=(ans+gao::sol())%mod;
	}
	ans=2ll*ans%mod;
	printf("%d",ans);
	return 0;
}

参考：https://www.cnblogs.com/Mr-Spade/p/10415180.html