扫描线

本文介绍扫描线的几个题目

二维偏序

E. World of Darkraft: Battle for Azathoth

题意

给定一些武器和防具，每个武器有攻击力，花费,每个防具有防御力和花费

给定一些怪物，每个怪物有攻击力，防御力，价值

你只可以选择一个武器和一个防具，可以获得攻击力小于武器并且防御力小于防具的所有怪物的价值，求最大收益

思路

  1. 将武器和怪物按照攻击力排序，防具自己排序，并且按照防具的防御力防具顺序（id）建立下标线段树
  2. 双指针i指向武器，j指向怪物，当i指针向右边移动1个，j指针只会向右边移动，且以后的i一定可以选到当前的怪物j，所以当前的j造成的贡献会一直保留。所以将j的贡献加到线段树中即可
  3. 对于每一个武器i算最大价值，详细见代码

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct A{
	ll g;
	ll c;
	bool operator<(const A&a)const{
		return g<a.g;
	}
}a[N];//gong
struct B{
	ll f;
	ll c;
	bool operator<(const B&b)const{
		return f<b.f;
	}
}b[N];//fang
struct C{
	ll g,f;
	ll c;
	bool operator<(const C&c)const{
		return g<c.g;
	}
}c[N];//monster

ll maxn[N<<2];
ll tag[N<<2];

void pushup(int u){
	ll lx=u<<1;
	ll rx=u<<1|1;
	maxn[u]=max(maxn[lx],maxn[rx]);
}
void pushdown(int u){
	ll lx=u<<1;
	ll rx=u<<1|1;
	if(tag[u]){
		maxn[lx]+=tag[u];
		maxn[rx]+=tag[u];
		tag[lx]+=tag[u];
		tag[rx]+=tag[u];
	}
	tag[u]=0;
}
void build(int u,int l,int r){
	if(l==r){
		maxn[u]=-b[l].c;
		return;
	}
	ll mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void add(int u,int l,int r,int L,int R,ll x){
	if(L<=l&&R>=r){
		maxn[u]+=x;
		tag[u]+=x;
		return;
	}
	pushdown(u);
	ll mid=l+r>>1;
	if(L<=mid){
		add(u<<1,l,mid,L,R,x);
	}
	if(R>mid){
		add(u<<1|1,mid+1,r,L,R,x);
	}
	pushup(u);
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int n,m,p;
	cin>>n>>m>>p;
    //输入武器属性
	for(int i=1;i<=n;i++){
		cin>>a[i].g>>a[i].c;
	}
    //输入防具属性
	for(int i=1;i<=m;i++){
		cin>>b[i].f>>b[i].c;
	}
    //输入怪物属性
	for(int i=1;i<=p;i++){
		cin>>c[i].g>>c[i].f>>c[i].c;
	}
    //排序
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	sort(c+1,c+1+p);
	build(1,1,m);
    
	int j=1;
	ll ans=-1e18;
	for(int i=1;i<=n;i++){
        //暴力加入怪物的价值
		while(j<=p&&c[j].g<a[i].g){
			int l=1,r=m;
			int pos=m+1;
			while(l<=r){
				int mid=l+r>>1;
				if(b[mid].f>c[j].f){
					pos=mid;
					r=mid-1;
				}
				else{
					l=mid+1;
				}
			}
            //[pos,m]下标中所有防具需要加上c价值
			if(pos<=m){//update
				add(1,1,m,pos,m,c[j].c);
			}
			++j;
		}
        //计算选择当前武器的答案
		ans=max(ans,maxn[1]-a[i].c);
	}
	cout<<ans<<endl;
    return 0;
}

E. Number of Groups

题意

给一些线段[x,y]，每个线段有一个颜色（0或者1），如果两个不同颜色的线段有交集，那他们在同一组，问有多少不同的组

思路

  1. 将一个线段的x，y看成时间（time），将插入和删除看成时间（event），显然，一个线段的x是插入，y是删除，这是典型的扫描线想法
  2. 按照(time,event)排序，对于插入操作，我们需要知道可以和哪些线段合并，同时自己要记录自己在那个集合中
  3. 显然并查集

步骤

  1. 开两个集合，存每种颜色的线段右端点即可
  2. 按照（time，event）排序后，遍历所有点对，如果是插入操作，查询谁跟他一组，暴力合并，如果是删除操作，删除这个点对即可。但是此时会超时，因为每个线段都可以被合并很多次，复杂度不可以保证。
  3. 考虑贪心，若两个0颜色线段在同一个集合中，此时他们肯定都没有删除，此时遍历到第i个点对，那么，如果是插入操作，此时只需要和最后一个合并即可（如果可以的话），因为合并的前提是当前点对的time，也就是另一个线段的左端点<=一个线段的左端点要<=另一个线段的右端点，所以贪心即可，边合并边删除即可，具体看代码
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll n;

struct A{
	int col;
	int l,r;
}a[N];
struct B{
	int pos;
	bool in;//是否需要插入
	int id;
	bool operator<(const B&b)const{
		if(pos!=b.pos)return pos<b.pos;
		if(in!=b.in)return in>b.in;
		return id<b.id;
	}
};
int f[N];
int find(int x){
	if(x==f[x])return x;
	return f[x]=find(f[x]);
}

void solve()
{
	
	vector<B>v;
	cin>>n;
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i].col>>a[i].l>>a[i].r;
		v.push_back({a[i].l,1,i});
		v.push_back({a[i].r,0,i});
	}
	sort(v.begin(),v.end());
	set<pair<int,int>>p[2];//0表示第一个集合，1表示第二个集合
	//pos,id
	for(auto qq:v){
		int id=qq.id;//id
		bool in=qq.in;//in
		int pos=qq.pos;//pos
		int col=a[id].col;//col
		if(in){
			//插入到本集合中
			p[col].insert(make_pair(a[id].r,id));
			//匹配另外一个集合的元素，并且保留最后一个
			while(p[col^1].size()>1){
				f[find(id)]=find(p[col^1].begin()->second);
				p[col^1].erase(p[col^1].begin());
			}
            //最后一个还没验证是否可以合并呢
			if(p[col^1].size()==1){
				f[find(id)]=find(p[col^1].begin()->second);
			}
		}
		else{
			p[col].erase(make_pair(a[id].r,id));
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(find(i)==i)ans++;
	}
	cout<<ans<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

P4137 Rmq Problem / mex

题意

给定一个序列，多次询问，区间mex是多少

思路

  1. 莫队秒了
  2. 权值线段树扫描线，扫描序列，到达第i个位置的时候，处理以第i个位置为右端点的所有询问。转化为求最小的x，满足$pos[x]<l$,x就是第id个询问的答案,显然可以用线段树二分。
  3. 只需要将权值x当成下标就可以，支持更新pos[x]，和区间查询即可
  4. 注意权值从0开始

代码

莫队

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2e5 + 5;

int minn[N << 2];

int n, m;
int a[N];
vector<pair<int, int>>v[N];
void pushup(int u) {
	minn[u] = min(minn[u << 1], minn[u << 1 | 1]);
}

//修改pos为x
void modify(int u, int l, int r, int pos, int x) {
	if (l == r) {
		minn[u] = x;
		return;
	}
	int mid = l + r >> 1;
	if (pos <= mid) {
		modify(u << 1, l, mid, pos, x);
	}
	else {
		modify(u << 1 | 1, mid + 1, r, pos, x);
	}
	pushup(u);
}

//在L到R内查询比tar小的最小的下标（pos[x]<tar,最小的x)
int ask(int u, int l, int r, int L, int R, int tar) {
	if (l == r) {
		if (minn[u] < tar)
			return l;
		else return n + 1;
	}
	int mid = l + r >> 1;
	if (L <= l && R >= r) {
		int ans = n + 1;
		if (minn[u << 1] < tar) {
			return ask(u << 1, l, mid, L, R, tar);
		}
		if (minn[u << 1 | 1] < tar) {
			return ask(u << 1 | 1, mid + 1, r, L, R, tar);
		}
		return ans;
	}
	int ans = n + 1;
	if (minn[u << 1] < tar && L <= mid) {
		ans = min(ans, ask(u << 1, l, mid, L, R, tar));
	}
	if (minn[u << 1 | 1]<tar && R>mid) {
		ans = min(ans, ask(u << 1 | 1, mid + 1, r, L, R, tar));
	}
	return ans;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] = min(a[i], n + 1);
	}

	for (int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		v[r].push_back({ l,i });
	}

	vector<int>ans(m + 1, 0);
	for (int i = 1; i <= n + 1; i++) {
		modify(1, 0, n + 1, a[i], i);
		for (auto que : v[i]) {
			int l = que.first;
			int id = que.second;
			ans[id] = ask(1, 0, n + 1, 0, i, l);
		}
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}
算法 > 扫描线
#算法
扫描线
http://example.com/2023/12/01/算法/扫描线/
作者
Mrxiad
发布于
2023年12月1日
许可协议