题意简化
每次修改一个点的横坐标，求斜率最大值
如何思考
首先考虑，如果没有修改操作，只是单纯的问你任意两点之间的斜率，该怎么办？
暴力
这里有一个
的做法是任意点都算一遍求最大斜率但显然不可能。
优化
其实学过斜率优化的都知道可以先以横坐标为关键词排个序（可以理解为在坐标轴上画出来），然后要求的任意两点的斜率最大值就是是排序后相邻两点的斜率的最大值。
那没学过怎么办，这里来证明：
对于上面这张图，我们将要处理的点在坐标轴上描出来（在程序里体现为排序），显然直线
的斜率最大，在程序内部点都已经排好序，当处理到点
时发现前一个点和当前点的斜率大于当前已知的最大斜率，即
于是将当前的最大值更改。
接下来是疑点，为啥最大斜率一定是相邻两点的，图中可以看出 ，我们假设有三个点 那可以得出 ,。
通过计算可以得到若 , 就一定会有 。
所以得出以上结论。
该怎么用
其实加上修改之后我们发现每次修改真正影响到的只有两个点即前面的点和后面的点，于是我们可以预处理出不修改时的最大斜率，再每次和修改后的点产生的贡献（即修改后位置前后的斜率）对比取最大值，求解。
但有一个问题如果修改影响到最大值怎么办，其实只需要再处理出次大值就可以了。
注意不是直接求次大值，是要求和最大值没有公共点的次大值
最后判断一下即可，注意要判断修改到最前面和最后面的情况。
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
|
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=5e5+100;
int n,m;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int abs(int a){return a>0?a:-a;}
struct node{
int x,t;
int id;
bool operator < (const node s){
if(t!=s.t)return t < s.t;
return x < s.x;
}
}e[N];
int max_fir;
int max_sec;
int fro_fir;
int fro_sec;
int tim[N];
int find(int t){
int l=1;
int r=n;
if(t<e[1].t)return 0;
if(t>e[n].t)return n+1;
while(l<r){
int mid=(l+r)>>1;
if(e[mid].t>=t)r=mid;
else l=mid+1;
}
return l;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&e[i].x,&e[i].t);
tim[i]=e[i].t;
}
sort(e+1,e+n+1);
for(int i=2;i<=n;i++){
int d=abs(e[i].x-e[i-1].x)/abs(e[i].t-e[i-1].t);
if(d>max_fir){
if(fro_fir!=i-1){
max_sec=max_fir;
fro_sec=fro_fir;
}
max_fir=d;
fro_fir=i;
}
else if(d>max_sec){
if(fro_fir!=i-1){
max_sec=d;
fro_sec=i;
}
}
}
int ans;
for(int i=1;i<=m;i++){
int u,v;
ans=0;
scanf("%d%d",&u,&v);
u=tim[u];
int d=find(u);
int tmp=find(v);
int tx=e[d].x;
int d1=0;
int d2=0;
if(tmp==0){
int www=abs(v-e[tmp].t);
if(www==0)d2=0;
else d2=abs(tx-e[tmp].x)/www;
}
else if(tmp==n+1){
int www=abs(v-e[tmp-1].t);
if(www==0)d2=0;
else d1=abs(tx-e[tmp-1].x)/www;
}
else {
int www=abs(v-e[tmp].t);
if(www==0)d2=0;
else d2=abs(tx-e[tmp].x)/abs(v-e[tmp].t);
www=abs(v-e[tmp-1].t);
if(www==0)d2=0;
else d1=abs(tx-e[tmp-1].x)/www;
}
ans=max(d1,d2);
if(d!=fro_fir && d!=fro_fir-1){
ans=max(ans,max_fir);
}
else {
ans=max(ans,max_sec);
}
printf("%d\n",ans);
}
return 0;
}
|
