Reincarnation

正因为梦易碎，才格外美好。

扫描线

发表于 更新于 分类于 ，
本文字数： 13k 阅读时长 ≈ 12 分钟

光赐予苦，暗生汝乐。

扫描线

扫描线，一种十分抽象的技巧，用于部分数据结构问题中会出现奇效。一般而言，用于解决多维问题，在固定一维的前提下，处理出其它维度对当前维的贡献，而这一维则需要枚举，这个操作称之为对该维作扫描线。

在静态情况下可以配合一些数据结构直接做，而在带修情况下可能需要结合一些分治算法进行使用。

静态

园丁的烦恼

题目简介

题目名称：园丁的烦恼
题目来源：上海省选 具体不详

评测链接：https://www.luogu.com.cn/problem/P2163

形式化题意：在二维平面中有 个点，共 次询问，每次询问以 为左下角， 为右上角的矩阵中有多少个点。

数据范围：

考虑矩阵是不好做的，所以转化成二维前缀和。把每个询问拆成 个部分来做。

这样的话，我们需要处理的所有插入与询问都是以点对形式存在了。

将插入点与询问离线存储，按照 从小到大依次处理。因为现在是处理前缀和，所以横坐标比 小的点才会对询问产生贡献，所以这样不会重复计算，也不会遗漏。然后考虑对于固定的 ，我们相当于还是对 再做一次前缀和，可以直接使用 进行维护。

具体操作，可以理解为把一个长度为 的 延数轴从 到 移动，然后遇到所有 的点就将其加入到 中，遇到询问为 的也及时处理，这里每一个询问都拆成了两个 两个 的前缀和处理，当 走到 的时候，所有点都被统计，那所有询问也都被处理了。

这道题好像有点卡常，如果将 离散化后会时间超限两个点，然后如果不离散化也会超限一个点，但开 后都可以过。

AC Code
 
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
// ----- Eternally question-----
// Problem: P2163 [SHOI2007] 园丁的烦恼
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2163
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-15 14:55:43
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10,MAXM=1e7+10;
int N,M,Q,Cnt,ans[MAXN];
struct Node
{
	int opt,x,y,id,val;
	bool operator<(const Node &_) const
	{ return x==_.x?opt<_.opt:x<_.x; }
	inline void print(){ write(opt,' ',x,' ',y,' ',id,' ',val,'\n'); }
}Qry[MAXN<<3];
struct BIT
{
	int Tre[MAXM];
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x,int v){ for(;x<=M;x+=lowbit(x)) Tre[x]+=v; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
	inline int get(int l,int r){ return query(r)-query(l-1); }
}Tre;
std::vector<int>Nums;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1,x,y;i<=N;++i)
	{
		read(x,y);++x,++y;
		Nums.emplace_back(y);
		Qry[++Cnt]=(Node){0,x,y,0,0};
	}
	for(int i=1,l,r,x,y;i<=Q;++i)
	{
		read(l,r,x,y);++l,++r,++x,++y;
		Nums.emplace_back(r-1),Nums.emplace_back(y);
		Qry[++Cnt]=(Node){1,l-1,r-1,i,1},Qry[++Cnt]=(Node){1,x,y,i,1};
		Qry[++Cnt]=(Node){1,l-1,y,i,-1},Qry[++Cnt]=(Node){1,x,r-1,i,-1};
	}
	std::sort(Nums.begin(),Nums.end());
	Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
	M=MAXM-10;//Nums.size();
	// for(int i=1;i<=Cnt;++i) Qry[i].y=std::lower_bound(Nums.begin(),Nums.end(),Qry[i].y)-Nums.begin()+1;
	std::sort(Qry+1,Qry+Cnt+1);
	for(int i=1;i<=Cnt;++i)
	{
		auto q=Qry[i];
		if(!q.opt) Tre.add(q.y,1);
		else
		{
			int id=q.id;
			ans[id]+=q.val*Tre.query(q.y);
		}
	}
	for(int i=1;i<=Q;++i) write(ans[i],'\n');
	return 0;
}
/*

*/

World of Darkraft: Battle for Azathoth

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1320/C

形式化题意：勇士有 把剑，第 把剑的伤害为 ；勇士有 个盾，第 个盾的防御为 ，荒野中有 只怪物，第 只怪物的血量为 ，伤害为 ，勇士可以打败所有怪物血量低于剑的伤害，怪物伤害低于盾的防御的怪物。

第 把剑的价格为 ，第 个盾的价格为 ，杀死第 只怪物能得到赏金 。勇士只能且必须携带一把剑和一个盾，求勇士最后得到的钱。

数据范围：

我们以伤害作为 轴，防御作为 轴建立二维平面，把剑视作 的怪物，赏金为 ；盾视作 的怪物，赏金为 。

那么问题转化为二维平面上存在一些带权点，求一个以 为左下角的矩阵的权值最大值。

那我们同样对 轴作扫描线，对 轴维护一个线段树，那么点 会对 产生 的贡献，那么每次求全局最大值即可。

需要注意的是，可能会存在没有任何剑盾能够杀死一只怪物的情况，所以可以考虑加入一只 的怪物作为边界。

不需要离散化，直接做即可，时间复杂度 。

AC Code
 
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
130
// ----- Eternally question-----
// Problem: C. World of Darkraft: Battle for Azathoth
// Contest: Codeforces - Codeforces Round 625 (Div. 1, based on Technocup 2020 Final Round)
// URL: https://codeforces.com/problemset/problem/1320/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-08-15 15:32:15
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10,MAXM=1e6+10;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int S=1e6+1;
int N,M,P;
ll Atk[MAXM],Def[MAXM],ans=-INF;
struct Monster
{
	ll atk,def,cost;
	bool operator<(const Monster &x) const
	{ return atk<x.atk; }
}Mon[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r;
	ll val,tag;
}Tr[MAXM<<2];
inline void pushUp(int p)
{ Tr[p].val=std::max(Tr[ls].val,Tr[rs].val); }
inline void upDate(int p,ll v)
{
	Tr[p].val+=v,Tr[p].tag+=v;
	return ;
}
inline void pushDown(int p)
{
	if(!Tr[p].tag) return ;
	upDate(ls,Tr[p].tag),upDate(rs,Tr[p].tag);
	Tr[p].tag=0;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val=-Def[l],void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyAdd(int p,int l,int r,ll v)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return upDate(p,v);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyAdd(ls,l,r,v);
	if(mid<r) modifyAdd(rs,l,r,v);
	pushUp(p);
}
ll queryMax(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	ll res=-INF;
	if(l<=mid) checkMax(res,queryMax(ls,l,r));
	if(mid<r) checkMax(res,queryMax(rs,l,r));
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,P);
	std::memset(Atk,0x3f,sizeof(Atk)),
	std::memset(Def,0x3f,sizeof(Def));
	for(int i=1,x;i<=N;++i){ ll c;read(x,c),checkMin(Atk[x],c); }
	for(int i=1,x;i<=M;++i){ ll c;read(x,c),checkMin(Def[x],c); }
	for(int i=1;i<=P;++i) read(Mon[i].atk,Mon[i].def,Mon[i].cost),++Mon[i].def,++Mon[i].atk;
	Mon[++P]=(Monster){1,1,0};
	std::sort(Mon+1,Mon+P+1);
	build(1,1,S);
	for(int i=S;i>=1;--i) checkMin(Atk[i],Atk[i+1]);
	for(int i=1;i<=P;++i)
	{
		auto q=Mon[i];
		modifyAdd(1,q.def,S,q.cost);
		checkMax(ans,queryMax(1,1,S)-Atk[q.atk]);
	}
	write(ans);
	return 0;
}
/*

*/

小卡与落叶

题目简介

题目名称：小卡与落叶
题目来源：第四届传智杯初赛 题

评测链接：https://www.luogu.com.cn/problem/P8844

形式化题意：给定一棵以 为根的树（），初始所有结点为绿色，维护 次操作：

  • 将整棵树染绿后将深度大于 的点染黄；
  • 求以 为根的子树中颜色为黄色的结点个数。

数据范围：

容易发现所有的询问仅和距离它最近的修改有关，且修改与修改间独立，所以并不是真正意义上的带修。那我们记当前询问的深度为 。

那么，所有符合要求的点一定满足 。显然前面是一个偏序关系，考虑如何限制在子树内，想到使用 序，记录以 为根结点的子树的 区间为 。

以 序为 轴，以 为 轴，每次询问相当于求以 为左下角， 为右上角的矩阵中点 的个数。这个是好做的，直接用 维护即可。

AC Code
 
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
// ----- Eternally question-----
// Problem: P8844 [传智杯 #4 初赛] 小卡与落叶
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8844
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-15 20:20:44
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,Q;
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Dfn[MAXN],Bck[MAXN],Lst[MAXN],Rst[MAXN],Dep[MAXN],Cnt;
void dfsTree(int x,int last)
{
	Lst[x]=Dfn[x]=++Cnt;
	Dep[x]=Dep[last]+1,Bck[Cnt]=x;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
	}
	Rst[x]=Cnt;
}
int ans[MAXN],Idx,Tot;
struct Query
{
	int opt,id,x,y,val;
	bool operator<(const Query &_) const
	{ return x==_.x?opt<_.opt:x<_.x; }
}Qry[MAXN<<3];
struct BIT
{
	int Tre[MAXN],Siz;
	inline int lowbit(int x){ return x&(-x); }
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline void add(int x,int v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;	
	}
	inline int get(int l,int r){ return query(r)-query(l-1); }
}Tre;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q),Tre.build(N+1);
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	dfsTree(1,0);
	int Lim=N+1;
	for(int i=1,opt,qx;i<=Q;++i)
	{
		read(opt,qx);
		if(opt==1) Lim=qx;
		else
		{
			++Tot;
			Qry[++Idx]=(Query){1,Tot,Lst[qx]-1,Lim-1,1};
			Qry[++Idx]=(Query){1,Tot,Lst[qx]-1,N+1,-1};
			Qry[++Idx]=(Query){1,Tot,Rst[qx],Lim-1,-1};
			Qry[++Idx]=(Query){1,Tot,Rst[qx],N+1,1};
		}
	}
	for(int i=1;i<=N;++i) Qry[++Idx]=(Query){0,0,Dfn[i],Dep[i],0};
	std::sort(Qry+1,Qry+Idx+1);
	for(int i=1;i<=Idx;++i)
	{
		auto q=Qry[i];
		if(!q.opt) Tre.add(q.y,1);
		else ans[q.id]+=q.val*Tre.query(q.y);
	}
	for(int i=1;i<=Tot;++i) write(ans[i],'\n');
	return 0;
}
/*

*/

动态

rprmq1

详见 成外集训题解。

相关文章