天梯赛选拔-线段树辅助建图

本文最后更新于：2024年9月13日 早上

背景： 天梯赛选拔赛被打爆了. . .
复盘发现是由于在两道题上浪费了太多时间并且最后没修出来。
一道暴力题我最开始就没想到裸暴力能过便死在了繁杂的优化上，还有一道就是这道题。
我考试中有想到过大体的方向，就是把区间缩点，和正解大致思路是相同的
(所以我感觉我的方向是对的就几乎把时间全花在这上面了)
但我当时不知道有线段树辅助建图的这个方法，于是自己用了一种十分繁杂的办法排列建图区间的左右端点然后再扫一遍端点确定缩点的范围来建图. . .
然后改细节改到心态崩溃
最后一直在这两道题之间反复横跳(因为感觉自己能打就差一点)。
下来后HS说这玩意他用线段树秒了。便学习了这个算法。

先看一下题目吧。

题目描述

给定一个 n 个点的无向图。开始时图中没有边，之后yxh将进行 m 次加边操作，其中第 i 次操作具体描述如下：
每个操作的描述包含两个在 [1, n] 范围内的互不相同的整数 $l_i$, $r_i$，和一个正整数 $c_i$，对于所有满足$l_i$ ≤ s < t ≤ $r_i$ 的点对 (s, t)，都在点 s 和点 t 之间加上一条长度为 $c_i$ 的无向边。
在所有加边操作完成后，yxh要求你计算出从节点 1 到节点 n 的最短路径。如果不存在任何从 1 到n 的路径，则输出 −1。

输入格式 Input Format

第一行包含两个个正整数 n, m(2 ≤ n, m ≤ $10^5$)，含义如上所示。
接下来的 m 行，每行都包含三个整数 $l_i$, $r_i$(1 ≤ $l_i$ < $r_i$ ≤ n), $c_i$(1 ≤ $c_i$ ≤ $10^9$)，含义如上所示。

输出格式 Output Format

输出包含一行，代表从节点 1 到节点 n 的最短路径。如果不存在任何从 1 到 n 路径，则输出 −1。

输入：

4 3
1 3 2
2 4 3
1 4 6

输出：

5

想法

我自己考试时候的想法已经在背景里大致说了，感觉应该可以搞但是麻烦到现在都不想打. . .只讲一下线段树辅助建图吧。
我们可以根据题意将其简化为一个模型，
就是将每个区间连边操作都当作新建两个新节点(入节点和出节点)，然后保证这个区间里的所有点与入节点都能有一条权值为v的路，以及出节点与区间内所有点都能有一条权值为0的路，入节点和出节点连一条单向权值为0的边。
我们可以用线段树来简化这个操作，建两棵线段树，一棵由入节点组成且树上的边为指向父亲的权值为0的单向边；另一棵由出节点组成且树上的边为指向儿子的权值为0的单向边。
这样我们直接在树上进行连边操作即可。令一个线段树上的点代表其所属区间所有的集合，有新的区间建边操作时，在入节点线段树上找到属于该区间的所有小区间，并令这些小区间的代表点与新建的“操作点”连权值为v的边，出节点线段树的操作和入节点线段树上的操作几乎一样，只不过连的边相反并且边权均为0。
显然，每一次区间操作后连的边的期望为$log(区间长度)$,最终连的边数就是mlogn。
求最短路部分就用正常最短路算法即可，这里用的是堆优化的dj。

总结

这个方法本质上使用线段树的性质是用一点来表示整个区间，从而不需要区间里的每个节点都进行连边，最终达到了简化的目的。
我感觉这也正是线段树优化的本质：即用一个节点来记录囊括所有子节点的所需的相关信息，在询问相关问题时就可以用一个节点直接返回答案，减少对子节点的重复访问。
这道题为每个节点附上了代表一处区间的含义，然后用大节点来减少小结点的重复访问(建边)。这实际上是对以往区间操作的认知(区间加减乘除)的一个拓展，也是对以后再看到区间相关的题目的一种启发。
这个算法目前我打的还是直球版本，由于入节点和出节点的线段树所有操作相同，所以获得两棵线段树之间的联系后应该还可以继续优化。

update 2021/4/8

之前一直没提交，然后今天发现OJ上的提交通道开放了，便提交了一下，然后Wa了 . . .
然后改改wawa，wawa改改，最后改回了原样，结果就过了

然后发现自己在修改的第二个版本加了个打表一直没有删. . .第一遍没过是因为没用long long。第四遍修改时把所有int改成了longlong，这个版本就应该过了，但是打表没删就一直卡着 . . .
菜且星际QAQ

代码

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
#include<bits/stdc++.h>
using namespace std;
struct ss
{
    int x,y,next,v;
}e[100010];
struct tree
{
    int ll,rr,num;
};
struct node {
    int u,d;
    bool operator <(const node& rhs) const{return d>rhs.d;}
};
priority_queue<node>Q; 
long long Link[100010],jkl=0,pointnum,n,m,tree1fa,tree2fa;
tree point1[100010],point2[100010];//point1是入点线段树，point2为出点线段树
inline int insert(int xx,int yy,int vv)
{
    e[++jkl].next=Link[xx];e[jkl].x=xx;e[jkl].y=yy;e[jkl].v=vv;Link[xx]=jkl;
}
inline int build1(int ll,int rr)
{
    long long mid=(ll+rr)/2,nowpoint=++pointnum;
    point1[nowpoint].num=pointnum;
    if(ll==rr)
    {
        point1[nowpoint].rr=point1[nowpoint].ll=ll;
        insert(ll,nowpoint,0);
        return point1[nowpoint].num;
    }
    point1[nowpoint].ll=build1(ll,mid);
    point1[nowpoint].rr=build1(mid+1,rr);
    insert(point1[nowpoint].ll,nowpoint,0);//在入点线段树上建立0边
    insert(point1[nowpoint].rr,nowpoint,0);
    return point1[nowpoint].num;
}
inline int build2(int ll,int rr)
{
    long long mid=(ll+rr)/2,nowpoint=++pointnum;
    point2[nowpoint].num=pointnum;
    if(ll==rr)
    {
        point2[nowpoint].rr=point2[nowpoint].ll=ll;
        insert(nowpoint,ll,0);
        return point2[nowpoint].num;
    }
    point2[nowpoint].ll=build2(ll,mid);
    point2[nowpoint].rr=build2(mid+1,rr);
    insert(nowpoint,point2[nowpoint].ll,0);//在出点线段树上建立0边
    insert(nowpoint,point2[nowpoint].rr,0);
    return point2[nowpoint].num;
}
inline void edge_in(int ll,int rr,int vv,int nowll,int nowrr,int nowpoint)
{
    long long mid=(nowll+nowrr)/2;
    if(ll<=nowll&&rr>=nowrr)
    {
        insert(nowpoint,pointnum,vv);//入点线段树与区间节点建边
        return ;
    }
    if(ll>nowrr||rr<nowll)return ;
    edge_in(ll,rr,vv,nowll,mid,point1[nowpoint].ll);edge_in(ll,rr,vv,mid+1,nowrr,point1[nowpoint].rr);
    return ;
}
inline void edge_out(int ll,int rr,int vv,int nowll,int nowrr,int nowpoint)
{
    if(ll>nowrr||rr<nowll)return ;
    long long mid=(nowll+nowrr)/2;
    if(ll<=nowll&&rr>=nowrr)
    {
        insert(pointnum,nowpoint,0);//区间节点与出点线段树建边
        return ;
    }
    
    edge_out(ll,rr,vv,nowll,mid,point2[nowpoint].ll);edge_out(ll,rr,vv,mid+1,nowrr,point2[nowpoint].rr);
    return ;
}
long long dis[100010];
inline void dj(int st)
{
    for (int i=0;i<=pointnum;i++) dis[i]=100000000000ll;
	dis[st]=0;
	node minpoint;
	minpoint.u=st;minpoint.d=0;
    Q.push(minpoint);
	while(Q.size())
	{
        minpoint=Q.top();Q.pop();
        int u=minpoint.u,d=minpoint.d;
		if (dis[u]!=d) continue ;
		//cout<<u<<' '<<d<<endl;
        //if (d!=dis[u]) continue;
		for(int j=Link[u];j;j=e[j].next)//用最近的点来更新其他点的最近距离
		{//保证了前一步找最近的点时找到的就是该点的最短路
			if(dis[e[j].y]>d+e[j].v)
			{
				dis[e[j].y]=d+e[j].v;
                Q.push((node){e[j].y,dis[e[j].y]});
			}
		}
	}
}
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    cin>>n>>m;
    pointnum=n;
    tree1fa=build1(1,n);tree2fa=build2(1,n);
    for(int i=1,ll,rr,vv;i<=m;i++)  
    {
        cin>>ll>>rr>>vv;
        pointnum++;
        edge_in(ll,rr,vv,1,n,tree1fa);
        edge_out(ll,rr,vv,1,n,tree2fa);
    }
    /*for(int i=1;i<=pointnum;i++)
    {
        cout<<i<<':';
        for(int j=Link[i];j;j=e[j].next)cout<<e[j].y<<' ';cout<<endl;
    }*/
    dj(1);
	//cout<<n<<endl;
	//for (int i=1;i<=n;i++) printf("%d ",dis[i]);
    if(dis[n]!=dis[0])cout<<dis[n]<<endl;
    else cout<<-1<<endl;
    return 0;
}