Codeforces Round #406 (Div. 2) D. Legacy 线段树建图求最短路

有 n 个点,初时没有边,m 次操作,操作分为三种

1、加一条从 u 到 v 的权值为 val 的边

2、加一条从 u 到 [ql,qr] 区间所有点的权值为 val 的边

3、加一条从 [ql,qr] 到 u 区间所有点的权值为 val 的边

最后求一个单源最短路。

        

1、显然暴力建边会超时,那么我们考虑分块,将它分为  个 块,每块长度为 ,然后发现时间复杂度为 ,由于常数太大,应该会超时。

2、分块超时一定是分块不够优雅,考虑线段树的 build 过程,将整个区间分为了 nlogn 个区间,并且区间修改的复杂度是 logn ,看起来有点香。

3、考虑将所有线段树的区间看成一个点,那么当我们进行 2 操作的时候,一个点走向一个区间的点,就意味着这个点向这个区间连边.

4、考虑 一个点走向一个区间 和 一个区间走向一个点,第一种,一个点能走到这个区间,说明他能走到所有这个区间的子区间,第二种,一个区间的点都能走到 一个点,说明所有能走到覆盖这个区间的点都能走到 一个点,这两种状态是不同的,所以考虑建两颗线段树,一颗自上到下建单向边,一颗自下到上建单向边,第一棵树维护操作2,第二颗树维护操作3就可以了。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1;
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXN_DOT = 3e5 + 5;
struct edge
{
	int to;
	ll w;
	int nex;
}e[MAXN * 68];
int head[MAXN_DOT], tot;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
}
void add(int u, int v, ll w)
{
	e[tot] = edge{ v,w,head[u] };
	head[u] = tot++;
}
struct segment
{
	int l;
	int r;
	int flag;
}que_up[MAXN * 4], que_down[MAXN * 4];
int tot_dot;
int n, q, s;
int ql, qr;
ll val;
//从上到下建边
void build_up(int left = 1, int right = n, int k = 1, int fa = 0)
{
	que_up[k].l = left;
	que_up[k].r = right;
	if (left == right)
	{
		que_up[k].flag = left;
		add(fa, left, 0);
		return;
	}
	if (fa)
		add(fa, tot_dot, 0);
	int u = tot_dot;
	que_up[k].flag = tot_dot++;

	imid;
	build_up(lson, u);
	build_up(rson, u);
}
void update_up(int left = 1, int right = n, int k = 1, int u = 0)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		add(u, que_up[k].flag, val);
		return;
	}
	imid;
	update_up(lson, u);
	update_up(rson, u);
}
//从下到上建边
void build_down(int left = 1, int right = n, int k = 1, int fa = 0)
{
	que_down[k].l = left;
	que_down[k].r = right;
	if (left == right)
	{
		que_down[k].flag = left;
		add(left, fa, 0);
		return;
	}
	if (fa)
		add(tot_dot, fa, 0);
	int u = tot_dot;
	que_down[k].flag = tot_dot++;

	imid;
	build_down(lson, u);
	build_down(rson, u);
}
void update_down(int left = 1, int right = n, int k = 1, int u = 0)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		add(que_down[k].flag, u, val);
		return;
	}
	imid;
	update_down(lson, u);
	update_down(rson, u);
}
#define Pair pair<ll,int>
ll dis[MAXN_DOT];
bool vis[MAXN_DOT];
void dij(int s, int n)
{
	for (int i = 0; i < MAXN_DOT; i++)
		dis[i] = 1e18 + 7;
	priority_queue<Pair, vector<Pair>, greater<Pair> > q;
	dis[s] = 0;
	q.push(Pair{ 0,s });
	while (!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = true;
		for (int i = head[u]; i + 1; i = e[i].nex)
		{
			int to = e[i].to;
			if (dis[u] + e[i].w < dis[to])
			{
				dis[to] = dis[u] + e[i].w;
				q.push(Pair{ dis[to],to });
			}
		}
	}
	for (int i = 1; i <= n; i++)
		pr("%lld%c", dis[i] == 1e18 + 7 ? -1 : dis[i], i == n ? '\n' : ' ');
}
int main()
{
	init();
	sc("%d%d%d", &n, &q, &s);
	tot_dot = n + 1;
	build_up();
	build_down();
	while (q--)
	{
		int op;
		sc("%d", &op);
		if (op == 1)
		{
			sc("%d%d%lld", &ql, &qr, &val);
			add(ql, qr, val);
		}
		else
		{
			int u;
			sc("%d%d%d%lld", &u, &ql, &qr, &val);
			if (op == 2)
				update_up(1, n, 1, u);
			else
				update_down(1, n, 1, u);
		}
	}
	dij(s, n);
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
06-21 11:33
昨天是学校最后一场招聘会,鼠鼠去参加了,全场只有一个招聘java的岗位,上来先做一份笔试题,做完后他拿张纸对答案,然后开始问简历上的问题,深圳小厂,6-8k(题目如下),后面还有两轮面试。然后我就在招聘现场逛呀逛,看到有公司招聘电商运营,给的比上年的小厂还多,鼠鼠就去了解了下,然后hr跟鼠鼠要了份简历,虽然我的简历上面全是求职Java开发相关的内容,但是hr还是鼓励我说没关系,她帮我把简历给老板看看,下周一会给我通知。招聘会结束后鼠鼠想了一段时间,也和朋友聊了聊,发现我可能是不太适合这个方向,然后就跟爸爸说回家了给我发条微信,我有些话想跟他说说。晚上爸爸到家了,跟我发了条微信,我立马跑出图书馆跟他打起了电话,这个通话长达一个小时,主要是跟爸爸坦白说我不想找这行了,是你的儿子太没用了,想试试其他行业。然后爸爸也跟我说了很多,说他从来没有希望我毕业后就赚大钱的想法,找不到就回家去,回家了再慢慢找,实在找不到就跟他干(帮别人装修房子,个体户),他也知道工作不好找,让我不要那么焦虑,然后就是聊一些家常琐事。对于后面的求职者呢我有点建议想提一下,就是如果招实习的时间或者秋招开始,而你的简历又很差的情况下,不要说等做好项目填充完简历之后再投,那样就太晚了,建议先把熟悉的项目写上简历,然后边投边面边完善,求职是一个人进步的过程,本来就比别人慢,等到一切都准备好后再投岂不是黄花菜都凉了。时间够的话还是建议敲一遍代码,因为那样能让你加深一下对项目的理解,上面那些说法只是针对时间不够的情况。当然,这些建议可能没啥用,因为我只是一个loser,这些全是建立在我理想的情况下,有没有用还需其他人现身说法。上篇帖子没想到学校被人认了出来,为了不丢脸只能匿名处理了。
KPLACE:找研发类或技术类,主要还是要1.多投 2.多做准备,很多方面都要做准备 3.要有心理准备,投累了就休息一两天,再继续,要相信自己能找到
投递58到家等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务