发表更新题解37 分钟读完 (大约5499个字)

杂题选做（2023.9.25 - 2023.9.26）

杂题选做（2023.9.25 - 2023.9.26）

GYM100837F Controlled Tournament

题目描述：

有 nn 个人进行淘汰赛，已知 Ri,jR_{i,j} 表示第 ii 个人和第 jj 个人比赛的胜负情况。

每一时刻内可以安排任意多场比赛，但是一个人一个时刻最多只能打一场比赛。

给定 mm，要求在花费时间最小的前提下，使得 mm 获胜的方案数。

也就是说，如果在花费时间最小的时候，不存在任意一种方案使得 mm 可以获胜，则答案为 00。

题目分析：

既然花费时间最小，也就是肯定是 ⌈log⁡n⌉\lceil \log n \rceil 个时刻。

所以不妨假设 f[i][j][S]f[i][j][S] 表示考虑了前 ii 个时刻，考虑了 SS 内的人，获胜者为 jj 的方案数。

转移其实就是考虑是哪两个状态合并到这个状态的。

直接做的话复杂度会比较高，但是如果使用记忆化搜索的方式就能少掉很多无用的状态，就可以通过此题了。

需要注意的一点细节就是：nn 不一定可以表示为 2k2^k 的形式，所以我们单独的一个人，可能可以在任意一个时刻被加入到 dpdp 中，这个也就是 dpdp 的初值。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 17;
int n,m,dp[6][N][1<<N],tot[1<<N];
int R[N][N];
void add(int &a,int b){
	a = (a + b);
}
int get(int x,int y,int S){
	if(~dp[x][y][S])	return dp[x][y][S];
	if((1<<x) < tot[S])	return dp[x][y][S] = 0;
	if(S == (1<<(y-1)))	return dp[x][y][S] = 1;
	int tmp = 0;
	for(int i=1; i<=n; i++){
		if(!R[y][i])	continue;
		for(int T=S; T; T=(T-1)&S){
			if(((T >> (y-1)) & 1) && (((S^T) >> (i-1)) & 1))
				tmp += get(x-1,y,T) * get(x-1,i,S^T);
		}
	}
	return dp[x][y][S] = tmp;
}
signed main(){
//	freopen("f.in","r",stdin);
//	freopen("f.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			scanf("%d",&R[i][j]);
		}
	}
	
	for(int i=0; i<(1<<n); i++)	tot[i] = __builtin_popcount(i);
	memset(dp,-1,sizeof(dp));
	int t = ceil(log2(n));
	get(t,m,(1<<n)-1);
	if(dp[t][m][(1<<n)-1] == -1)	dp[t][m][(1<<n)-1] = 0;
	printf("%d\n",dp[t][m][(1<<n)-1]);
	return 0;
}

[NOI2021] 轻重边

题目描述

小 W 有一棵 nn 个结点的树，树上的每一条边可能是轻边或者重边。接下来你需要对树进行 mm 次操作，在所有操作开始前，树上所有边都是轻边。操作有以下两种：

  1. 给定两个点 aa 和 bb，首先对于 aa 到 bb 路径上的所有点 xx（包含 aa 和 bb），你要将与 xx 相连的所有边变为轻边。然后再将 aa 到 bb 路径上包含的所有边变为重边。
  2. 给定两个点 aa 和 bb，你需要计算当前 aa 到 bb 的路径上一共包含多少条重边。

【数据范围】

对于所有测试数据：T≤3T \le 3，1≤n,m≤1051 \le n, m \le {10}^5。

题目分析：

可以考虑将对链 (a,b)(a,b) 的修改，变成将链 (a,b)(a,b) 染上一个之前从未出现过的颜色。

这样一条重边也就是意味着连接的两个点颜色相同，一条轻边也就是连接的两个点颜色不同。

可以使用树链剖分维护，因为树链剖分是将一条树上的路径剖分为了若干个儿子到祖先的链，所以可以直接维护 (sum,l,r)(sum,l,r) 表示这条链的重链个数，左右端点的颜色，就可以支持高效合并了。

以及注意当我们树剖开始划分 lcalca 所在链的时候，要注意区间左右端点的交换问题，因为我们一直默认同一条儿子到祖先的链中 depdep 小的为左端点。

代码：

点击查看代码 
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
const int INF = 1e9 + 5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
struct node{
	int l_col,r_col,sum;
}T[4 * N];
node operator + (node a,node b){
	node c;
	c.l_col = a.l_col;
	c.r_col = b.r_col;
	c.sum = a.sum + b.sum + (a.r_col == b.l_col);
	return c;
}
int n,m,cnt,tot,head[N],dep[N],fa[N],dfn[N],son[N],sz[N],top[N],tag[4 * N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs1(int now,int fath){
	dep[now] = dep[fath] + 1;
	fa[now] = fath;sz[now] = 1;son[now] = 0;
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs1(to,now);
		if(sz[to] > sz[son[now]])	son[now] = to;
		sz[now] += sz[to];
	}
}
void dfs2(int now,int topf){
	top[now] = topf;dfn[now] = ++tot;
	if(son[now])	dfs2(son[now],topf);
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(to == fa[now] || to == son[now])	continue;
		dfs2(to,to);
	}
}

void build(int now,int now_l,int now_r){
	T[now].l_col = -now_l;//赋成这个值就是为了避免认为初值相等，也是重边 
	T[now].r_col = -now_r;
	T[now].sum = 0;
	tag[now] = 0;
	if(now_l == now_r)	return;
	int mid = (now_l + now_r)>>1;
	build(now<<1,now_l,mid);build(now<<1|1,mid+1,now_r);
}
void update(int now,int now_l,int now_r,int col){
	T[now].l_col = T[now].r_col = col;
	T[now].sum = now_r - now_l;
	tag[now] = col;
}
void pushdown(int now,int now_l,int now_r){
	if(!tag[now])	return;
	int mid = (now_l + now_r) >> 1;
	update(now<<1,now_l,mid,tag[now]);
	update(now<<1|1,mid+1,now_r,tag[now]);
	tag[now] = 0;
}
void modify(int now,int now_l,int now_r,int l,int r,int col){
	if(l <= now_l && now_r <= r){
		update(now,now_l,now_r,col);
		return;
	}
	pushdown(now,now_l,now_r);
	int mid = (now_l + now_r)>>1;
	if(l <= mid)	modify(now<<1,now_l,mid,l,r,col);
	if(r > mid)		modify(now<<1|1,mid+1,now_r,l,r,col);
	T[now] = T[now<<1] + T[now<<1|1];
}
node query(int now,int now_l,int now_r,int l,int r){
	if(l <= now_l && now_r <= r)	return T[now];
	pushdown(now,now_l,now_r);
	int mid = (now_l + now_r)>>1;
	if(r <= mid)	return query(now<<1,now_l,mid,l,r);
	else if(l > mid)	return query(now<<1|1,mid+1,now_r,l,r);
	return query(now<<1,now_l,mid,l,r) + query(now<<1|1,mid+1,now_r,l,r);
}
int query(int x,int y){
	node L,R;
	L.l_col = -INF;
	L.r_col = -INF+2;  //赋成这个值就是为了避免认为初值相等，也是重边 
	R.l_col = -INF+3;
	R.r_col = -INF+4;
	L.sum = R.sum = 0;
	
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])	swap(x,y),swap(L,R);
		L = query(1,1,n,dfn[top[x]],dfn[x]) + L;
		x = fa[top[x]];
	}
	if(dep[x] < dep[y])	swap(x,y),swap(L,R);
	L = query(1,1,n,dfn[y],dfn[x]) + L;
	swap(R.l_col,R.r_col);
	L = R + L;
	return L.sum;
}
void modify(int x,int y,int col){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]])	swap(x,y);
		modify(1,1,n,dfn[top[x]],dfn[x],col);
		x = fa[top[x]];
	}
	if(dep[x] < dep[y])	swap(x,y);
	modify(1,1,n,dfn[y],dfn[x],col);
}
int main(){
//	freopen("edge.in","r",stdin);
//	freopen("edge.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1; i<n; i++){
			int u,v;scanf("%d%d",&u,&v);
			add_edge(u,v);
			add_edge(v,u);
		}
		dfs1(1,0);
		dfs2(1,1);
		
		build(1,1,n);
		
		int col = 0;   //最开始的颜色默认为 0 
		
		while(m--){
			int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
			if(opt == 1){
				modify(x,y,++col);
			}
			else{
				printf("%d\n",query(x,y));
			}
		}
		
		cnt = 0,tot = 0;
		memset(head,0,sizeof(head));
	}
	return 0;
}

[COCI2018-2019#1] Strah

题目描述：

Mirko 最害怕的是寻找合适的土地来种植草莓。他的土地可以用一个 N×MN \times M 的矩阵来表示。土地中有些田地适合种植草莓，而有些不适合，因为那里杂草丛生。

Mirko 正在寻找一块合适矩形。当土地中有一块矩形区域包含的所有田地均适合种植草莓，则该矩形被称为合适矩形。

Mirko 还对所有田地的潜力值感兴趣。一块田地的潜力值定义为包含该田地的合适矩形的个数。

求 Mirko 所有田地的潜力值之和。

对于 100%100\% 的数据，1≤N,M≤20001 \le N,M \le 2000。

题目分析：

首先做一步转化：最终的答案等于所有合法矩形的面积和。

先考虑一些暴力的方法观察一下贡献。
枚举下边界 dd，左边界 ll，右边界 rr，设 uu 表示符合条件的矩形的最高高度。

则答案为：

(r−l+1)×∑i=1u−d+1i(r-l + 1) \times \sum_{i=1}^{u-d+1} i

所以想要快速维护一个想法就是不枚举左边界，要快速维护难算的只有 uu，而可以发现如果我们直接维护一个单调栈，那么对于单调栈内相邻两个点中间的区间，其 uu 必然是相同的，所以就很好计算了。

就是当 aa 插入单调栈的时候，找到第一个小于它的位置，访问过的位置的 uu 都被 aa 所限制，其贡献形如：

∑i=1p∑j=1qi×j\sum_{i=1}^p \sum_{j=1}^q i \times j

可以拆开，就是两个等差数列求和，然后再相乘。

可是对于 aa 插入到的位置的左边这些位置，依旧可以产生合法的矩形，但是我们如果暴力扫一遍单调栈复杂度就爆了，所以可以考虑在前面的位置打标记，当弹出前面这些位置的时候，就统计以前面这些位置为左边界，以打过标记的点为右边界的矩形面积之和。

如果两个右边界与对应的位置的距离分别为 u,vu,v，那么这两个右边界在对应位置打标记之后，弹出这个位置时额外的贡献其实就是：

∑i=1p[(i+u)+(i+v)]∑j=1qj\sum_{i=1}^p [(i+u) + (i+v)] \sum_{j=1}^q j

这个东西也是类似于两个等差数列数列求和，再相乘，也可以快速维护。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2005;
char s[N][N];
int U[N][N],a[N],top,sum[N],sz[N];
pair<int,int> st[N];
int get(int l,int r){
	return (l + r) * (r - l + 1) / 2;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++)	scanf("%s",s[i]+1);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(s[i][j] == '#')	U[i][j] = 0;
			else	U[i][j] = U[i-1][j] + 1;
		}
	}
	
	int ans = 0;
	for(int i=1; i<=n; i++){  //枚举下边界
		top = 0;
		st[++top] = {-1,0}; 
		for(int j=1; j<=m; j++) a[j] = U[i][j];
		for(int j=1; j<=m; j++){  //枚举右边界 
			while(top && a[j] <= st[top].first){
				sum[top-1] += sum[top];sz[top-1] += sz[top];
				if(sz[top])	ans += ((sum[top] - sz[top] * st[top].second) * (st[top].second - st[top-1].second) + get(1,st[top].second - st[top-1].second) * sz[top]) * get(1,st[top].first);
				--top;
			}
			ans += get(1,j - st[top].second) * get(1,a[j]);
			sum[top] += j,sz[top] ++;
			
			++top;st[top] = {a[j],j};sum[top] = sz[top] = 0;
			
		}
		for(int j=top; j>1; j--){
			sum[j-1] += sum[j];sz[j-1] += sz[j];
			if(sz[j])	ans += ((sum[j] - sz[j] * st[j].second) * (st[j].second - st[j-1].second) + get(1,st[j].second - st[j-1].second) * sz[j]) * get(1,st[j].first);
		}
	}
	
	printf("%lld\n",ans);
	return 0;
}

CF1879E Interactive Game with Coloring

题目描述：

本题为交互题。

给定一棵 nn 个点的有根树，节点 11 为根，要求你对每一条边进行染色。

交互库会有点 xx，你可以知道点 xx 周围连边的颜色数的情况，你可以每次选择一种颜色，使得 xx 沿着对应颜色的边走一步，如果有多条边为所选择的颜色，则会任意选择一条边走。

设点 xx 的深度为 dd，则你必须在 dd 步之内将 xx 移动到根节点，也就是必须每一步都移动向父亲节点。

询问一种合法的染色方案，并且要求所用的颜色数最小。
你还要与交互库交互，使得 xx 可以在 dd 步之内移动到根节点。

题目分析：

首先我们必须在任何一个节点都可以判断出其父边是哪一条，而且父边的颜色必须不和其它的边颜色一样。

一个想法就是按对应的深度作为颜色，这样父亲边就是深度最小的那一条边，但是这样明显颜色数量过多。

可以发现我们不用将所有的深度记录下来，我们只需要记录深度模 33 就可以根据颜色判断父边了。

这样其实就是我们可以构造答案为 33 的了，那么 11 和 22 的怎么办呢。

对于答案为 11 也就是所有的边都是一种颜色，这必然要满足最深的节点的深度不超过 11，不然一步肯定走不出。

对于答案为 22 因为我们要求父边与其它连边颜色不同，所以本质就是对于节点 11 的每一棵子树分别二分图黑白染色。

可以发现的一点就是，如果一个点 xx 的儿子个数不低于 22 个，那么其所连边中颜色数量最少的那种边就是父边，也就是这种点不会对我们黑白染色的情况产生影响。

而如果一个点 xx 的儿子数量为 00，那么其只有父边，也不会对我们的黑白染色情况产生影响。

如果一个点 xx 的儿子数量为 11，我们就无法根据数量和颜色来判断正确的决策是什么，就必须钦定一种决策，比如父边必须为黑边，这样就可以了，所以只有这一种边会对黑白染色产生限制。

所以可以直接根据限制倒推出来每一条边应该为什么颜色，就做完了。

这里我采取的写法就是，将所有的限制向上传递，传递到与 11 直接相连的边上，当然如果与 11 相连的这棵子树内没有限制，那么这一条边随便染一个颜色即可，这样就可以直接从 11 开始向下传递限制，就会好写很多。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,dep[N],a[N],fa[N],deg[N],ans[N],col[N];
vector<int> son[N];
void pushup(int now,int tmp){
	if(now == 1)	return;
	col[now] = tmp;
	pushup(fa[now],tmp == 1 ? 2 : 1);
}
void pushdown(int now,int tmp){
	for(auto to : son[now]){
		col[to] |= (tmp == 1 ? 2 : 1);
		pushdown(to,col[to]);
	}
}
bool check(){
	for(int i=2; i<=n; i++){
		if(deg[i] != 1)	continue;
		col[i] |= 1;
		for(auto j : son[i])	col[j] |= 2;
	}
	for(int i=2; i<=n; i++)	if(col[i])	pushup(i,col[i]);
	
	for(auto i : son[1]){
		if(!col[i])	col[i] = 1;
	}
	
	for(int i=2; i<=n; i++){
		pushdown(i,col[i]);
	}

	for(int i=2; i<=n; i++){
		if(deg[i] == 1 && deg[fa[i]] == 1 && (deg[fa[fa[i]]] == 1 || fa[fa[i]] == 1))	return false;
		if(col[i] == 3)	return false;
	} 
	return true;
}
int main(){
	scanf("%d",&n);
	int mx = 0;
	dep[1] = 0;
	for(int i=2; i<=n; i++){
		scanf("%d",&fa[i]);deg[fa[i]]++;
		son[fa[i]].push_back(i);
		dep[i] = (dep[fa[i]] + 1) % 3;
		mx = max(mx,dep[fa[i]] + 1);
	}
	if(mx != 1 && check()){
		printf("2\n"),fflush(stdout);
		for(int i=2; i<=n; i++)	printf("%d ",col[i]),fflush(stdout);
		while(1){
			int opt;scanf("%d",&opt);
			if(opt == 1 || opt == -1)	break;
			int tot = 0;
			for(int i=1; i<=2; i++)	scanf("%d",&a[i]),tot += a[i];
			if(tot == 1){
				for(int i=1; i<=2; i++){
					if(a[i])	printf("%d\n",i),fflush(stdout);
				}
			}
			else{
				if(a[1] == 1 && a[2] == 1)	printf("%d\n",1),fflush(stdout);
				else{
					if(a[1] == 1)	printf("%d\n",1),fflush(stdout);
					else	printf("%d\n",2),fflush(stdout);
				}
			}
		}
		return 0;
	}
	printf("%d\n",mx),fflush(stdout);
	for(int i=2; i<=n; i++)	printf("%d ",dep[fa[i]] + 1),fflush(stdout);
	while(1){
		int opt;scanf("%d",&opt);
		if(opt == 1 || opt == -1)	break;
		for(int i=1; i<=mx; i++)	scanf("%d",&a[i]);
		int tot = 0;
		for(int i=1; i<=mx; i++)	if(a[i] != 0)	++tot;
		
		if(tot == 1){
			for(int i=1; i<=mx; i++){
				if(a[i])	printf("%d\n",i),fflush(stdout);
			}
		}
		else{
			if(a[1] && a[2])	printf("1\n"),fflush(stdout);
			if(a[2] && a[3])	printf("2\n"),fflush(stdout);
			if(a[3] && a[1])	printf("3\n"),fflush(stdout);
		}
		fflush(stdout);
	}
	return 0;
}

CF1879F Last Man Standing

题目描述：

有 nn 个人，每个人有一个血量 hih_i 和护甲值 aia_i。

我们可以钦定一个数 xx 表示攻击力，攻击会进行多轮，直到所有的人 hh 均为 00，在每一轮攻击中如果 x<aix < a_i，则将 aia_i 减去 xx，否则将 hih_i 减 11 并将 aia_i 恢复为一开始的值。

定义一个人的得分为其独自存活的轮数，要求得出当 x∈[1,∞)x \in [1,\infty) 每个人得分的最大值是多少。

多测 1≤t≤101 \le t \le 10，1≤n,hi,ai≤2⋅1051 \le n,h_i,a_i \le 2\cdot 10^5

题目分析：

做题的第一步先看数据范围，观察到 hi,ai≤2⋅105h_i,a_i \le 2 \cdot 10^5 也就是说有用的 xx 只需要枚举到 max⁡ai=2⋅105\max a_i = 2\cdot 10^5 即可，因为再高了就是每个人都是一刀破防，就情况相同了。

显然的一点就是如果给定 xx，那么第 ii 个人存活的轮数就是：

h×⌈aix⌉h \times \left\lceil \frac{a_i}{x} \right\rceil

既然可以枚举 xx 那么显然的想法就是用 xx 的倍数将序列分段，这样每一段内的 ⌈aix⌉\lceil \frac{a_i}{x} \rceil 都相同，而我们只关心存活轮数中的最大值和次大值，所以这个东西就可以使用 ST 表快速维护。

因为 ST 表在求解的时候区间会有交集，所以如果最大值在交集的部位就可能被统计两次从而作为次大值出现，因为我们肯定在维护值的同时还会维护位置，所以直接对于最大值和次大值直接去重，然后对于剩下的寻找一下即可。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 5e5+5;
PII st1[N][20],st2[N][20],b[5];
int h[N],a[N],L[N],R[N];
long long ans[N];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void get(int l,int r){
	int len = log2(r - l + 1);
	b[1] = st1[l][len],b[2] = st1[r-(1<<len)+1][len];
	b[3] = st2[l][len],b[4] = st2[r-(1<<len)+1][len];
	PII tmp1 = {0,0},tmp2 = {0,0};
	for(int j=1; j<=4; j++){
		if(b[j] > tmp1)	swap(tmp1,tmp2),tmp1 = b[j];
		else if(b[j] != tmp1 && b[j] > tmp2)	tmp2 = b[j];
	}
	b[1] = tmp1,b[2] = tmp2;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;T=read();
	while(T--){
		int n;n=read();
		for(int i=1; i<=n; i++)	h[i]=read();
		int mx = 0;
		for(int i=1; i<=n; i++){
			a[i]=read();mx = max(mx,a[i]);
			if(st1[a[i]][0].first < h[i]){
				swap(st1[a[i]][0],st2[a[i]][0]);
				st1[a[i]][0] = {h[i],i};
			}
			else if(st2[a[i]][0].first < h[i]) st2[a[i]][0] = {h[i],i};
		}
		
		for(int i=1; i<=18; i++){
			for(int j=1; j+(1<<i)-1 <= mx + 1; j++){
				b[1] = st1[j][i-1],b[2] = st1[j+(1<<(i-1))][i-1];
				b[3] = st2[j][i-1],b[4] = st2[j+(1<<(i-1))][i-1];
				for(int k=1; k<=4; k++){
					if(b[k] > st1[j][i])	swap(st1[j][i],st2[j][i]),st1[j][i] = b[k];
					else if(b[k] > st2[j][i])	st2[j][i] = b[k];
				}
			}
		}
		
		for(int x=1; x<=mx+1; x++){
			int tot = 0;
			int nl = 1,nr = x;
			while(nr <= mx + 1){
				++tot;
				L[tot] = nl;R[tot] = nr;
				nl = nr + 1;nr = nl + x - 1;
			}
			
			if(R[tot] != mx + 1)	++tot,L[tot] = R[tot-1] + 1,R[tot] = mx + 1;
			
			pair<long long,int> ans1 = {0,0},ans2 = {0,0};
			for(int i=1; i<=tot; i++){
				get(L[i],R[i]);
				for(int j=1; j<=2; j++){
					if(1ll * b[j].first * i > ans1.first)	swap(ans1,ans2),ans1 = b[j],ans1.first = 1ll * ans1.first * i;
					else if(1ll * b[j].first * i > ans2.first)	ans2 = b[j],ans2.first = 1ll * ans2.first * i;
				}
			}
			
			ans[ans1.second] = max(ans[ans1.second],ans1.first - ans2.first);
		}
		
		for(int i=1; i<=n; i++)	printf("%lld ",ans[i]),ans[i] = 0;
		printf("\n");
		
		for(int i=0; i<=mx+1; i++){
			for(int j=0; j<=18; j++){
				st1[i][j] = st2[i][j] = {0,0};
			}
		}
	}
	return 0;
}

[COCI2018-2019#2] Sunčanje

题目描述：

Slavko 做了一个不寻常的梦。在一个晴朗的早上，NN 个白色的矩形一个接着一个爬上了 Slavko 家的屋顶，并在屋顶上晒太阳。每个矩形在屋顶都选定了一个位置，使得它的边与屋顶的棱角平行。有些矩形可能会覆盖在其它矩形所在的位置上。每个矩形的长、宽分别为 Ai,BiA_i,B_i，其与屋顶左方和下方的棱角的距离分别为 Xi,YiX_i,Y_i。

日落后，矩形们从屋顶上下来，并睡了一觉。次日，它们发现，有些矩形变成了黄色，而有些仍为白色。变为黄色的矩形都是完全暴露在阳光下的。

请判断每个矩形是否变为了黄色。

对于 100%100\% 的数据，1≤N≤1051 \le N \le 10^5，0≤Xi,Yi≤1090 \le X_i,Y_i \le 10^9，1≤Ai,Bi≤1091 \le A_i,B_i \le 10^9。

题目分析：

其实就是要求对于每一个矩形，判断比它出现时间晚的矩形中有没有可以覆盖它的。

做法一：

一个想法就是直接维护矩形加矩形求和，但是这样未免太大材小用了，我们只需要判断是否存在，而不用得知具体的值。

所以我们可以使用线段树套 set，在外层线段树维护 xx 这一维，然后使用 set 维护 x∈[l,r]x \in [l,r] 时，哪些 yy 被覆盖了，就是一个类似的区间染色。

然后你如果愿意打暴力的话，会发现如果你直接将 set 换成 vector 对于每一个节点暴力存所有染色的区间，然后每次查询暴力遍历每一个可能的区间，就可以获得最优解的好成绩。

做法二：

我们可以考虑容斥判断与当前矩形不交的矩形个数。

这个分讨是很简单的，就是完全在上面、下面、左面、右边的矩形个数，减去在左上角、右上角、右下角、左下角的矩形个数。

就是四遍二维偏序，四遍三维偏序，可以通过。

CF1635F Closest Pair

题目描述：

  • 给定 n(2≤n≤3×105)n(2 \le n \le 3\times 10^5) 个二元组 (xi,wi)(x_i,w_i)，其中 ∣xi∣≤109|x_i|\le 10^9，1≤wi≤1091\le w_i \le 10^9。
  • 输入中二元组按照 xix_i 严格递增排序给出。
  • 给出 q(1≤q≤3×105)q(1\le q \le 3\times 10^5) 次询问，每次询问给出 l,r(1≤l<r≤n)l,r(1\le l<r \le n)，你需要输出：

min⁡l≤i<j≤r∣xi−xj∣⋅(wi+wj)\min_{l\le i<j\le r} |x_i-x_j| \cdot (w_i+w_j)

题目分析：

这东西看上去就有一种支配对的感觉，所以我们就考虑若 i<j<ki < j < k，那么这个支配关系是怎么样的。

因为匹配是可以双向匹配的，但是我们可以强制让它变成单向匹配，这样显然是不劣的，也就是若 ii 匹配 jj 则必然满足 wi≥wjw_i \ge w_j。

如果要使得 j,kj,k 均为 ii 可以匹配的数，即满足 wi≥max⁡(wj,wk)w_i \ge \max(w_j,w_k)，考虑由匹配 jj 变成匹配 kk 贡献的变化，如果这个东西大于 00 则显然 (i,j)(i,j) 更优，否则如果小于 00 看似是 (i,k)(i,k) 更优，但是我们可以让 (j,k)(j,k) 这样是一组比 (i,k)(i,k) 优的答案，所以我们只需要对于每一个 ii 找到 ii 左边/右边第一个满足 wj≤wiw_j \le w_i 的点然后匹配即可。

这样的话对于一个询问 [l,r][l,r] 就相当于询问包含于 [l,r][l,r] 的匹配的权值的最小值，相当于一个二维偏序，按左端点从大到小排序之后，只需要满足右端点小于询问的右端点即可。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N = 2e6+5;
const int INF = 4e18+5;
struct node{
	int l,r,opt,val;
	node(){}
	node(int _l,int _r,int _opt,int _val){
		l = _l,r = _r,opt = _opt,val = _val;
	}
}a[N];
int n,q,mn[N],x[N],w[N],ans[N],L[N],R[N];
int calc(int l,int r){
	if(x[l] < x[r])	return (x[r] - x[l]) * (w[l] + w[r]);
	return (x[l] - x[r]) * (w[l] + w[r]);
}
bool cmp(node a,node b){
	if(a.l != b.l)	return a.l > b.l;
	return a.opt > b.opt;
}
int lowbit(int x){
	return x & (-x);
}
void modify(int x,int val){
	for(;x <= n; x += lowbit(x))	mn[x] = min(mn[x],val);
}
int query(int x){
	int ans = INF;
	for(;x; x -= lowbit(x))	ans = min(ans,mn[x]);
	return ans;
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1; i<=n; i++)	scanf("%lld%lld",&x[i],&w[i]);
	stack<PII> st;
	while(!st.empty())	st.pop();
	
	st.push({0,0});
	for(int i=1; i<=n; i++){
		while(!st.empty() && st.top().second > w[i])	st.pop();
		L[i] = st.top().first;st.push(make_pair(i,w[i])); 
	}
	while(!st.empty())	st.pop();
	
	st.push({n+1,0});
	for(int i=n; i>=1; i--){
		while(!st.empty() && st.top().second > w[i])	st.pop();
		R[i] = st.top().first;st.push(make_pair(i,w[i]));
	}
	
	int tot = 0;
	for(int i=1; i<=q; i++){
		int l,r;scanf("%lld%lld",&l,&r);
		a[++tot] = node(l,r,1,i);
	}
	
	for(int i=1; i<=n; i++){
		if(L[i])		a[++tot] = node(L[i],i,2,calc(L[i],i));
		if(R[i] <= n)	a[++tot] = node(i,R[i],2,calc(i,R[i]));
	}
	
	memset(mn,0x3f,sizeof(mn));
	
	sort(a+1,a+tot+1,cmp);
	for(int i=1; i<=tot; i++){
		if(a[i].opt == 1){
			ans[a[i].val] = query(a[i].r);
		}
		else if(a[i].opt == 2){
			modify(a[i].r,a[i].val);
		}
	}
	
	for(int i=1; i<=q; i++)	printf("%lld\n",ans[i]);
	return 0;
}

杂题选做（2023.9.25 - 2023.9.26）

http://linyihdfj.github.io/2023/09/27/practice-2023-9-23-9-25-26/

作者

linyihdfj

发布于

2023-09-27

更新于

2023-09-27

许可协议

×