免费自建网站工具在线工具seo

U525376信号干扰

题目描述

有 $n$ 座信号塔，第 $i$ 座信号塔的信号将覆盖区间 $[l_i,r_i]$。

若某个点被超过一座信号塔的信号覆盖，则在该点会产生信号干扰。

对于信号塔区间 $[a,b]$，若建造这些信号塔不会产生信号干扰，则称其为无干扰区间。对于所有 $i\in [1,n]\cap \mathbb{N}$，你需要求出 $a=i$ 时，使区间 $[a,b]$ 为无干扰区间的 $b$ 的最大值。

输入格式

第一行一个正整数 $n$，表示信号塔数量。

接下来 $n$ 行，每行两个正整数 $l_i,r_i$，表示信号塔的信号范围。

输出格式

输出一行 $n$ 个整数，第 $i$ 个正整数表示当 $a=i$ 时，使区间 $[a,b]$ 为无干扰区间的 $b$ 的最大值。

样例 #1

样例输入 #1

7
1 1
1 1000
1 3
3 3
4 6
2 3
1 1

样例输出 #1

1 2 3 5 7 7 7

提示

$1\le n\le 2\times 10^5$。$1\le l_i\le r_i\le 10^9$。

在本题中，约定区间的左右端点可以相等。

思路

定义结构体node储存区间，重载bool operator<(const nd& other)const{return r<other.l;}
然后用一个set<node>存区间，区间在其中自动排序，对于一个新区间a与set中的区间都不重合，则有s.find(a) == s.end() 成立，否则说明a与set中存的区间有重合部分。
原理大概是:如果b是与set中与a有重合部分的最左侧的区间，那么find在判断时会发现a不小于b，b不小于a，则认为a等于b，即找到目标，就会返回b的迭代器而不是end()；

代码：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
typedef long long ll;
using namespace std;struct nd{int l,r;nd(int L=0,int R=0){l=L,r=R;}bool operator<(const nd& other)const{return r<other.l;}
}a[200005];
set<nd> s;signed main() {cin.tie(0)->ios::sync_with_stdio(0);int n;cin>>n;for(int i=1;i<=n;i++){int l,r;cin>>l>>r;a[i]=nd(l,r);}int cnt = 0;for(int i=1;i<=n;i++){while(cnt<n && s.find(a[cnt+1]) == s.end()){s.insert(a[cnt+1]);cnt++;}cout<<cnt<<" ";s.erase(a[i]);}return 0;
}