基础

不写了。

优化建图

线段树优化建图

点 →\to 区间：直接线段树查询。

区间 →\to 区间：建虚点再连虚点。

CF786B & P6348 就是基本的两棵线段树优化建图，注意区间连点时线段树方向向上，点连区间时线段树方向向下。用两棵线段树时下面的子节点要逐一相连，因为他们本质是一样的。

例题：P3588

考虑建出线段树，对于每个给定区间，用他给的数分割这些区间，建立虚点连向这些被分割的区间，边权为 00，然后将给定的点连向虚点，边权为 11，然后拓扑排序模拟差分约束即可。

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
// Problem: P3588 [POI2015] PUS
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3588
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
struct line{
	int link,to,w;
}E[40000001];
int head[2000001],deg[4000005],vi[4000005],tot,cnt;
void addE(int u,int v,int w){
	E[++tot].link=head[u];
	E[tot].to=v;
	E[tot].w=w;
	deg[v]++;
	head[u]=tot;
	//cerr<<"     "<<u<<" "<<v<<' '<<w<<"\n";
	return;
}
int n,q,m,id[2000005],ans[2000005];
unordered_map<int,int> mp;
void bulid(int now,int l,int r){
	vi[now]=1;
	if(l==r){
		mp[now]=l;
		id[l]=now;
		cnt=max(cnt,now);
		return;
	}
	int mid=(l+r)/2;
	addE(now,now<<1,0);
	addE(now,now<<1|1,0);
	bulid(now<<1,l,mid);
	bulid(now<<1|1,mid+1,r);
	return;
}
void add(int now,int l,int r,int sl,int sr,int st){
	if(l==sl&&r==sr){
		addE(st,now,0);
		return;
	}
	int mid=(l+r)/2;
	if(sl<=mid)add(now<<1,l,mid,sl,min(sr,mid),st);
	if(sr>mid)add(now<<1|1,mid+1,r,max(sl,mid+1),sr,st);
	return;
}
int dis[4000005];
bool vis[4000005];
void topo(){
	queue<int> q;
	for(int i=1;i<=cnt;i++)if(ans[i])dis[i]=ans[i];else dis[i]=1e9;
	//for(int i=1;i<=cnt;i++)cerr<<dis[i]<<" "<<deg[i]<<" "<<vi[i]<<"\n";
	for(int i=1;i<=cnt;i++){
		if(vi[i]&&deg[i]==0)q.push(i);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop(); 
		//cerr<<u<<"\n";
		if(ans[u]&&dis[u]<ans[u]){
			cout<<"NIE";
			exit(0);
		}
		if(dis[u]<1){
			cout<<"NIE";
			exit(0);
		}
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=E[i].link){
			//cerr<<deg[E[i].to]<<" "<<E[i].to<<"\n";
			deg[E[i].to]--;
			dis[E[i].to]=min(dis[E[i].to],dis[u]-E[i].w);
			if(deg[E[i].to]==0){
				q.push(E[i].to);
			}
		}
	}
	//cout<<"topo ended.\n";
	for(int i=1;i<=cnt;i++){
		if(vi[i]&&!vis[i]){
		//	cout<<i<<"\n";
			cout<<"NIE";
			exit(0);
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>q>>m;
	bulid(1,1,n);
	int o;
	for(int i=1;i<=q;i++){
		cin>>o;
		cin>>ans[id[o]];
	}
	int x,y,z,u;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		int pos=x;
		cnt++;
		vi[cnt]=1;
		for(int j=1;j<=z;j++){
			cin>>u;
			addE(id[u],cnt,1);
			if(pos<=u-1)add(1,1,n,pos,u-1,cnt);
			pos=u+1;
		}
		if(pos<=y)add(1,1,n,pos,y,cnt);
	}
	topo();
	cout<<"TAK\n";
	for(int i=1;i<=n;i++)cout<<dis[id[i]]<<" ";
	return 0;
}

例题：P5025

考虑这道题暴力连边的话就是计算该点能达到的区间。

使用线段树优化建图，tarjan 缩点之后，发现每个点内的所有子点的区间就是所有子点能达到的最远区间，预处理时记录线段树每个节点的区间即可。

然后一遍 dfs 求出从这个点出发能达到的所有点的最大区间，与原来的点的最大区间合并，然后就得到了点内所有子点的答案，即 ri−li+1r_i-l_i+1。

最后统计答案即可。

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
// Problem: P5025 [SNOI2017] 鐐稿脊
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5025
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct line{
	int to,link;
}E[6000001],scc[6000001];
int head[2000001],tot;
int headscc[2000001],totscc,w[2000001];
int ll[2000001],rr[2000001];
int sccl[2000001],sccr[2000001];
int id[2000001];
bool isex[2000001];
void addE(int u,int v){
	E[++tot].link=head[u];
	E[tot].to=v;
	head[u]=tot;
//	cerr<<u<<" -> "<<v<<"\n";
	return;
}
void addscc(int u,int v){
	scc[++totscc].link=headscc[u];
	scc[totscc].to=v;
	headscc[u]=totscc;
	return;
}
int ccnt;
void bulid(int now,int l,int r){
	ll[now]=l;
	rr[now]=r;
	isex[now]=1;
	if(l==r)return id[l]=now,ccnt=max(now,ccnt),void();
	int mid=(l+r)/2;
	addE(now,now<<1);
	addE(now,now<<1|1);
	bulid(now<<1,l,mid);
	bulid(now<<1|1,mid+1,r);
	return;
}
void mdf(int now,int l,int r,int sl,int sr,int st){
	if(l==sl&&r==sr)return addE(st,now),void();
	int mid=(l+r)/2;
	if(sl<=mid)mdf(now<<1,l,mid,sl,min(sr,mid),st);
	if(sr>mid)mdf(now<<1|1,mid+1,r,max(sl,mid+1),sr,st);
	return;
}
int scccnt,belong[2000001];
int dfncnt,dfn[2000001],low[2000001];
bool instack[2000001];
stack<int> s;
void tarjan(int u){
//	cerr<<u<<"\n";
	dfn[u]=low[u]=++dfncnt;
	s.push(u);
	instack[u]=1;
	for(int i=head[u];i;i=E[i].link){
		if(!dfn[E[i].to]){
			tarjan(E[i].to);
			low[u]=min(low[u],low[E[i].to]);
		}
		else if(instack[E[i].to])low[u]=min(low[u],dfn[E[i].to]);
	}
//	cout<<low[u]<<" "<<dfn[u]<<" hanghang\n";
	if(low[u]==dfn[u]){
		scccnt++;
		sccl[scccnt]=1e9;
		sccr[scccnt]=0;
		int temp=s.top();
		do{
			temp=s.top();
			//cout<<temp<<" "<<scccnt<<"\n";
			instack[temp]=0;
			belong[temp]=scccnt;
			sccl[scccnt]=min(sccl[scccnt],ll[temp]);
			sccr[scccnt]=max(sccr[scccnt],rr[temp]);
			s.pop();
		}while(temp!=u);
	}
	return;
}
int n;
int X[500001],R[500001];
int sx[500001];
bool vi[2000001];
void dfs(int u){
	vi[u]=1;
	for(int k=headscc[u];k;k=scc[k].link){
		if(!vi[scc[k].to])dfs(scc[k].to);
		sccl[u]=min(sccl[u],sccl[scc[k].to]);
		sccr[u]=max(sccr[u],sccr[scc[k].to]);
	}
	return;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	bulid(1,1,n);
	for(int i=1;i<=n;i++){
		cin>>X[i]>>R[i];
		sx[i]=X[i];
	}
	for(int i=1;i<=n;i++){
		int lef=lower_bound(X+1,X+n+1,X[i]-R[i])-X;
		int righ=upper_bound(X+1,X+n+1,X[i]+R[i])-X-1;
		mdf(1,1,n,lef,righ,id[i]);
//		cout<<lef<<" "<<righ<<"\n";
	}
	tarjan(1);
	for(int i=1;i<=ccnt;i++){
		if(isex[i]){
			for(int k=head[i];k;k=E[k].link){
				if(belong[i]!=belong[E[k].to])addscc(belong[i],belong[E[k].to]);
			}
		}
	}
	for(int i=1;i<=scccnt;i++){
		if(!vi[i])dfs(i);
	}
//	for(int i=1;i<=n;i++)cout<<belong[id[i]]<<"\n";
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=1ll*i*(sccr[belong[id[i]]]-sccl[belong[id[i]]]+1)%1000000007ll;
		ans%=1000000007ll;
	//	cout<<(sccr[belong[id[i]]]-sccl[belong[id[i]]]+1)<<"\n";
	}
	cout<<ans;
	
	return 0;
}

塔杨写挂了，然后调了很久，看来需要进行 tarjan 的复习了。