【二分 树状数组】North America Championship 2020 G.ICPC Camp
2021-08-20 19:14:00 # ACM

题链

题目解析

设题给的两个数组为 $a,b$，二分答案，相当于对每一个 $a_i$ 能在 $b$ 数组中选择的值加了限制，将 $a,b$ 数组排序之后，对于每一个 $a_i$ 在 $b$ 数组中能选择的范围就是一个区间了；

所以解决一个子问题，有 $n$ 个区间 $[l,r]$，每个区间需要选择一个数字，全部选择完后最多能有多少个不重复的数字；

对于 $n$ 个区间按照右端点 $r$ 从小到大排序，若相同则对左端点 $l$ 从小到大排序，对于每一个 $r$ 都选择大于等于它对应的 $l$ 的最小的未被选过的值，也就是大于等于 $l$ 的 $mex$，若无法选择则跳过这个区间；

用二分加树状数组查找大于等于 $l$ 的 $mex$；

如何查找

在 $[l,r]$ 中二分一个 $mid$，查找 $[l,mid]$ 中有多少个被选择的值，若小于区间长度则 $mex$ 在 $[l,mid]$ 内；

代码实现

复杂度 $O(nlogmlognlogn)$，$m$ 是值域…竟然跑完了；

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
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
    #define Pair pair<LL ,LL >
    #define ls rt<<1
    #define rs rt<<1|1
    #define PI acos(-1.0)
    #define eps 1e-13
    #define mod 998244353
    #define MAXN 2e9
    #define MS 200005
    
int n,m1,m2,l,r,h;
int a[MS], b[MS];
struct node{
	int l,r;
}p[MS];
int tot;
LL tr[MS<<2];

bool cmp(node t1,node t2){
	if(t1.r == t2.r) return t1.l < t2.l;
	return t1.r < t2.r;
}

int lowbit(int x){
	return x&(-x);
}

void add(int pos,int val){
	for(;pos<MS;pos+=lowbit(pos)) tr[pos] += val; 
}

LL query(int pos){
	LL ans = 0;
	for(;pos;pos-=lowbit(pos)) ans += tr[pos];
	return ans;
} 

int cal(){
	int cnt = 0;
	for(int i=1;i<=m1;i++){
		int tl = p[i].l;
		int tr = p[i].r;
		int t = -1;
		while(tl <= tr){
			int m = tl+tr>>1;
			if(query(m) - query(p[i].l-1) < m-p[i].l+1){
				t = m;
				tr = m-1;
			}
			else tl = m+1;
		}
		if(t != -1){
			cnt++;
			add(t,1);
		}
	}
	return cnt;
}

int jdg(int x){
	// 记录区间 
	for(int i=1;i<=m1;i++){
		if(h-a[i] < a[i]-x){
			p[i] = {0,-1};
			continue;
		}
		int L = min(a[i]-x,h-a[i]);
		int R = min(a[i]+x,h-a[i]);
		p[i].l = lower_bound(b+1,b+m2+1,L) - b;
		p[i].r = upper_bound(b+1,b+m2+1,R) - b - 1;
	}
	sort(p+1,p+m1+1,cmp);
	memset(tr,0,sizeof tr);
	// 计算能选择的最多不重复数字 
	int cc = cal();
	return cc >= n;
}

inline void solve(){
    cin >> n >> m1 >> m2 >> h; r = h;
    for(int i=1;i<=m1;i++) cin >> a[i];
    for(int i=1;i<=m2;i++) cin >> b[i];
    sort(a+1,a+m1+1); sort(b+1,b+m2+1);
    int ans = -1;
    while(l <= r){
    	int mid = l+r>>1;
    	if(jdg(mid)){
    		ans = mid;
    		r = mid-1;
		}
		else l = mid+1;
	}
	cout << ans << "\n";
} 

int main() {
    ios::sync_with_stdio(false);
//	srand((unsigned)time(0));
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
    int ce = 1;
//    cin >> ce;
//    scanf("%d",&ce);
    while(ce--) solve();
    
    return 0;
}
/*


*/
Prev
2021-08-20 19:14:00 # ACM
Next