洛谷P6877 長いだけのネクタイ

传送门

题目描述

JOI 公司发明了一种领带，一共有 N+1N+1 条领带，编号为 11 到 N+1N+1，第 ii 条领带的长度为 A_iA
i
​
。

JOI 公司开了一个派对，派对中有 NN 名员工，第 jj 名员工刚开始戴了长度为 B_jB
j
​
的领带。

派对这样举行：

首先，JOI 公司的老板 JOI 君选出一条领带拿走。
然后，每个员工选一条领带，保证没有两名员工选了相同的领带。
最后，他们取下最先戴的领带，戴上选择的领带。
如果一名员工刚开始戴的领带长度为 bb，选择的领带长度为 aa，那么他就会产生 \max{a-b,0}max{a−b,0} 的奇怪感，整场派对的奇怪程度为所有员工的奇怪感的最大值。

于是 JOI 君定义 C_kC
k
​
为他选出第 kk 条领带后的最小奇怪程度。

JOI 君想知道 C_kC
k
​
的具体值。

输入格式

第一行一个整数 NN 代表员工数。
第二行 N+1N+1 个整数 A_iA
i
​
代表每个领带的长度。
第三行 NN 个整数 B_jB
j
​
代表每个人最开始戴的领带的长度。

输出格式

一行 N+1N+1 个整数 C_kC
k
​
代表选出每个领带后的最小奇怪程度。

输入输出样例

输入 #1复制
3
4 3 7 6
2 6 4
输出 #1复制
2 2 1 1
输入 #2复制
5
4 7 9 10 11 12
3 5 7 9 11
输出 #2复制
4 4 3 2 2 2

说明/提示

样例 1 解释
让我们假设 JOI 君选择了第 44 条领带，那么员工们可以这么选择：

第 11 名员工选择第 11 条领带，产生奇怪感 22
第 22 名员工选择第 22 条领带，产生奇怪感 00
第 33 名员工选择第 33 条领带，产生奇怪感 33
奇怪程度为 33。

但我们还可以继续减小奇怪程度：

第 11 名员工选择第 22 条领带，产生奇怪感 11
第 22 名员工选择第 33 条领带，产生奇怪感 11
第 33 名员工选择第 11 条领带，产生奇怪感 00
奇怪程度为 11。

因此 C_4=1C
4
​
=1。

数据规模与约定

本题采用捆绑测试。

Subtask 1（1 pts）：N \le 10N≤10。
Subtask 2（8 pts）：N \le 2000N≤2000。
Subtask 3（91 pts）：无特殊限制。
对于 100%100% 的数据：

1 \le N \le 2 \times 10^51≤N≤2×10
5
。
1 \le A_i \le 10^91≤A
i
​
≤10
9
。
1 \le B_j \le 10^91≤B
j
​
≤10
9
。

上代码：

#include
#include
#include
#define R register int
#define N 200005
#define ll long long
using namespace std;
int n,tree1[N<<2],tree2[N<<2],num[N],c1[N],c2[N],b[N];
struct arr{int x,id;}a[N];
int max(int a,int b) {return a>b?a:b;}
int min(int a,int b) {return a<b?a:b;}
void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
bool cmp(arr x,arr y) {return x.x>y.x;}
bool cmp1(int x,int y) {return x>y;}
void build1(int u,int l,int r)
{
	if (l==r) {tree1[u]=c1[l];return;}
	int mid=l+r>>1;build1(u<<1,l,mid);build1(u<<1|1,mid+1,r);
	tree1[u]=max(tree1[u<<1],tree1[u<<1|1]);
}
void build2(int u,int l,int r)
{
	if (l==r) {tree2[u]=c2[l];return;}
	int mid=l+r>>1;build2(u<<1,l,mid);build2(u<<1|1,mid+1,r);
	tree2[u]=max(tree2[u<<1],tree2[u<<1|1]);
}
int find1(int u,int l,int r,int x,int y)
{
	if (l>=x && r<=y) return tree1[u];
	int mid=l+r>>1,res=0;
	if (x<=mid) res=max(res,find1(u<<1,l,mid,x,y));if (y>mid) res=max(res,find1(u<<1|1,mid+1,r,x,y));
	return res;
}
int find2(int u,int l,int r,int x,int y)
{
	if (l>=x && r<=y) return tree2[u];
	int mid=l+r>>1,res=0;
	if (x<=mid) res=max(res,find2(u<<1,l,mid,x,y));if (y>mid) res=max(res,find2(u<<1|1,mid+1,r,x,y));
	return res;
}
int main()
{
	read(n);
	for (R i=1;i<=n+1;++i)
		read(a[i].x),a[i].id=i;
	for (R i=1;i<=n;++i)
		read(b[i]);
	sort(a+1,a+1+n+1,cmp);sort(b+1,b+1+n,cmp1);
	for (R i=1;i<=n+1;++i)
		num[a[i].id]=i;
	for (R i=1;i<=n;++i)
		c1[i]=max(a[i].x-b[i],0),c2[i]=max(a[i+1].x-b[i],0);
	build1(1,1,n);build2(1,1,n);
	for (R i=1;i<=n+1;++i)
	{
		if (num[i]==1) printf("%d ",find2(1,1,n,1,n));
		else if (num[i]==n+1) printf("%d ",find1(1,1,n,1,n)); 
		else printf("%d ",max(find1(1,1,n,1,num[i]-1),find2(1,1,n,num[i],n)));
	}
	printf("\n");
	return 0;
}
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