题解：P11021 「LAOI-6」区间测速

· · 题解

这场比赛之前，我曾经祈祷最后两题不要出构造。

不知道是不是有更简便的解法，但在我看完题面并想好做法之后，突然就开始想念构造了，起码只用动脑子。

有点大的分讨。

首先得出一个结论：

假设 t_a<t_b<t_c，那么无论 x_a,x_b,x_c 的值为多少，a 到 b 或者 b 到 c 的平均速度一定大于等于从 a 到 c 的平均速度。

假设 v 为通过一段的速度，证明如下：

用一张图来表示（假设每个监控的信息被抽象为一个点）：

然后我们可以开始考虑如何执行题目的操作了。

有一个简单并且显而易见的思路：当一个点被修改，先得出该点拿掉之后该序列的最大值，然后再看这个点按照时间顺序插入之后的最靠近该点左右的两个点（这里用到了上面那个结论，想一想为什么）所提供的答案，将这三个结果取最大值。

还是用一张图表示：

这种做法可以解决一大部分情况，但万一修改到的红色点在两个蓝色段上呢？

简单，只要再维护一个第二大不就行了吗？

然后还是看图吧，更清楚：

这个方法可以解决很多问题，但还有一种特殊情况：如果修改到的红色点同时在两个段上呢？

简单，只要再维护一个第三大不就行了吗？

由于一个点一定不能同时覆盖到三个区间，因此我们不用再说“简单，只要再维护一个第四大不就行了吗？”

值得注意的是，我们统计的第一、第二、第三大只是长度为一的区间的大小顺序，所以我们才需要引入紫色段（这个长度为二的区间仍然可能大于第二大、第三大）。

思路大概到这里，至于代码……长度有点吓人，码量作为基础赛第三题感觉有点过于凶残了。

具体的实现方法还有一些实现上的细节本题解并未提及，可以参考于代码。

因为是比赛写的，所以代码没有经过任何优化也不简洁，并不值得借鉴。

代码没有注释，还请见谅。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int xi,ti,id;
}a[1000005];
bool cmp(node a,node b){
    return a.ti<b.ti;
}
int f[1000005];
signed main(){
    int n,m;
    int maxn1=0,maxn2=0,maxi1=0,maxi2=0,maxn3=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].xi>>a[i].ti;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++){
//      cout<<a[i].xi-a[i-1].xi<<" "<<a[i].ti<<" "<<a[i-1].ti<<endl;
        if(maxn1<abs(a[i].xi-a[i-1].xi)/(a[i].ti-a[i-1].ti)){
            maxn3=maxn2;
            maxn2=maxn1;
            maxi2=maxi1;
            maxn1=abs(a[i].xi-a[i-1].xi)/(a[i].ti-a[i-1].ti);
            maxi1=i-1;
        }
        else if(maxn2<abs(a[i].xi-a[i-1].xi)/(a[i].ti-a[i-1].ti)){
            maxn3=maxn2;
            maxn2=abs(a[i].xi-a[i-1].xi)/(a[i].ti-a[i-1].ti);
            maxi2=i-1;
        }
        else if(maxn3<abs(a[i].xi-a[i-1].xi)/(a[i].ti-a[i-1].ti)){
            maxn3=abs(a[i].xi-a[i-1].xi)/(a[i].ti-a[i-1].ti);
        }
        f[a[i].id]=i;
    }
//  cout<<"___________________________________________\n";
//  cout<<maxn1<<" "<<maxn2<<" "<<maxn3<<"ASD\n";
    while(m--){
        int u,v;
        cin>>u>>v;
        u=f[u];
        int nt=-1;
        if(u==maxi1){
//          cout<<"MAXI____\n";
            if(u==maxi2+1){
                nt=max(abs(a[maxi1+1].xi-a[maxi1-1].xi)/(a[maxi1+1].ti-a[maxi1-1].ti),maxn3);
            }
            else{
                nt=max(abs(a[maxi1+1].xi-a[maxi1-1].xi)/(a[maxi1+1].ti-a[maxi1-1].ti),maxn2);
            }
        }
        else if(u==maxi1+1){
//          cout<<"MAXI++++\n";
            if(u==maxi2){
//              cout<<"@\n";
                nt=max(abs(a[maxi1+2].xi-a[maxi1].xi)/(a[maxi1+2].ti-a[maxi1].ti),maxn3);
            }
            else{
                nt=max(abs(a[maxi1+2].xi-a[maxi1].xi)/(a[maxi1+2].ti-a[maxi1].ti),maxn2);
            }
        }
        else{
            nt=maxn1;
        }
//      cout<<nt<<endl;
        int l=1,r=n,mid,tmp=0;
        while(l<=r){
            mid=l+r>>1;
            if(a[mid].ti<=v){
                tmp=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        int now=0;
//      cout<<u<<"________________"<<tmp<<endl;
        if(tmp==0){
            if(u==1){
                now=max(now,abs(a[2].xi-a[u].xi)/(a[2].ti-v));
            }
            else{
                now=max(now,abs(a[1].xi-a[u].xi)/(a[1].ti-v));
            }
        }
        else{
            if(u==tmp&&tmp!=1){
                now=max(now,abs(a[u].xi-a[tmp-1].xi)/(v-a[tmp-1].ti));
            }
            else{
//              cout<<"ASDJKLAS\n";
//              cout<<a[u].xi<<" "<<a[tmp].xi<<" "<<a[u].ti<<" "<<a[tmp].ti<<endl;
                now=max(now,abs(a[u].xi-a[tmp].xi)/(v-a[tmp].ti));
            }
            if(u==tmp+1&&tmp!=n){
                now=max(now,abs(a[tmp+2].xi-a[u].xi)/(a[tmp+2].ti-v));
            }
            else{
                now=max(now,abs(a[tmp+1].xi-a[u].xi)/(a[tmp+1].ti-v));
            }
        }
        cout<<max(nt,now)<<"\n";
    }
    return 0;
}