专栏首页wymE - Explorer

E - Explorer

给你 n 个点,m 条边,每条边给你一组数 (u, v, l, r) 代表如果你想从u点走到v点,你的身高需要满足范围 [ l , r ] ,问你从 1 走到 n 点,你有多少种身高可以选择。

解:先对所有的 l, r 离散化建线段树, 每个结点表示 大于等于当前点小于下一个点的 区间,比如有 1 5 两个点,线段树中就有一个结点表示区间 [1,4]。 建树如果当前边 能在该 结点表示的区间,就加入这条边。 于是对每种范围的区间 已经把所有的边加进去了。 接下来分治区间, 如果 [L,R] 区间所有的选择都行,就ans+=所有选择,

否则 就 [L,mid] 和 [mid+1,R] 考虑,由于并查集有撤销操作,不能压缩路径

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
typedef pair<int,int> P;
struct N{
	int l,r,u,v;
}a[maxn];
int n,m;
int dep[maxn],pre[maxn],ans,tot;
int b[maxn];
vector<int> tr[maxn<<2];
int getf(int t){
	while(t!=pre[t]){
		t = pre[t];
	}
	return pre[t];
}
void update(int rt,int l,int r,int L,int R,int k){
	if(L<=l&&R>=r){
		tr[rt].push_back(k); 
		return ;
	}
	int mid = (l+r)>>1;
	if(L<=mid)update(rt<<1,l,mid,L,R,k);
	if(R>mid)update(rt<<1|1,mid+1,r,L,R,k);
}
void dfs(int rt,int l,int r){
	int sz = tr[rt].size();
	vector<P> tmp;
	for(int i=0;i<sz;i++){
		int t = tr[rt][i];
		int u = a[t].u, v = a[t].v;
		u = getf(u);	v = getf(v);
		if(u==v)continue;
		if(dep[u]<dep[v])
			pre[u] =  v, tmp.push_back(P{u,0});
		else if(dep[v]<dep[u])
			pre[v] = u, tmp.push_back(P{v,0});
		else 
			pre[u] = v,dep[v]++,tmp.push_back(P{u,1}); 
	}
	if(getf(1)==getf(n)){
		ans+=b[r+1] - b[l];
	}else if(l<r){
		int mid = (l+r)>>1;
		dfs(rt<<1,l,mid);
		dfs(rt<<1|1,mid+1,r);
	} 
	sz = tmp.size();
	for(int i = sz-1;i>=0;i--){
		P o = tmp[i];
		dep[ pre[o.first] ]-=o.second;
		pre[ o.first ] = o.first;
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		pre[i] = i;
		dep[i] = 0;
	}
	for(int i=1;i<=m;i++){
		scanf("%d %d %d %d",&a[i].u,&a[i].v,&a[i].l,&a[i].r);
		b[2*i-1] = a[i].l;
		b[2*i] = a[i].r + 1;
	} 
	sort(b+1,b+1+2*m);
	tot = unique(b+1,b+1+2*m) - b - 1;
	for(int i=1;i<=m;i++){
		a[i].l = lower_bound(b+1,b+1+tot,a[i].l) - b;
		a[i].r = lower_bound(b+1,b+1+tot,a[i].r+1) - b - 1;
		update(1,1,tot,a[i].l,a[i].r,i);	
	}
	dfs(1,1,tot);
	printf("%d\n",ans);
	return 0;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • [USACO06JAN]牛的舞会 Tarjan模版

    用户2965768
  • 洛谷P4768 [NOI2018]归程(Kruskal重构树)

    哎,调了一上午也没调出来,只有72分,可以过所有的单个数据,但是一起跑就GG,而且我本机跑大数据会RE。

    attack
  • C++ 万字长文第一篇---拿下字节面试

    有些情况下,基类生成的对象是不合理的,比如动物可以派生出狮子、孔雀等,这些派生类显然存在着较大的差异。那么可以让基类定义一个函数,并不给出具体的操作内容,让派生...

    syy
  • 万字长文!位运算面试看这篇就够了!

    祝大家五一快乐。今天是小浩算法 “365刷题计划” 位运算超长 - 整合篇。估计五一期间,大家也没有什么心思好好做题。所以我就把之前已经出过的位运算系列,进行了...

    程序员小浩
  • HDU3440 House Man

    题意:有n栋房子,给出每栋房子的高度和开始时的相对位置,可以移动一些房子,但不能改变这些房子的相对位置,现在从最矮的房子开始,每次跳至比它高的第一栋房子, 而且...

    attack
  • 迷宫的最短路径

    题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

    杨鹏伟
  • Light oj 1112 - Curious Robin Hood(树状数组)

    有n个数,有m组操作,1 i表示将第i个数先输出,然后置0, 2 i v 表示给第i个数加上v, 3 i j 表示求i 到 j 的和,注意,这里数组是从0...

    xindoo
  • 搜索与回溯算法模板及其应用

    为了求得问题的解,先选择某一种可能情况向前探索,在探索的过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解...

    echobingo

扫码关注云+社区

领取腾讯云代金券