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

ZMQ_Ink65536 · 2024-09-07 22:57:26 · 题解

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

正解似乎是线段树，但我是一点也不会 （线段树板子都是拿树状数组水的），所以来分享一种不用线段树的方法。

前置知识

• 结构体
• 排序
• 关联式容器（map）
• 容器适配器（优先队列）
• 二分

解题思路

首先看暴力的打法：对于每次修改，按照时间排序，验证，复杂度：O(n m \log n)。

发现每次修改时仅会更改一小部分数值，也就是暴力算法进行了大量重复计算。考虑优化。

首先，很明确的一点，每次更改最多影响前 5 大的数据。如图：

会影响原位置的 3 个数据和新位置的 2 个数据：

若给上图的十个方块编号 1 到 10 相信读者数得出来，则删除 (2,3) 和 (3,4) 对答案的贡献，添加 (2,4)、(7,3) 和 (3,8) 的贡献。

此时我们就可以只在这几个值里面枚举答案。

实现细节

为降低复杂度，我们需要大量 O(\log n) 的算法，下面会简单介绍在这道题的具体使用方法。

• 首先，对初始数据用 t_i 从小至大排序，复杂度 O(n \log n)，代码：sort(a + 1 , a + n + 1 , cmp);。
• 其次，使用 map 记录排序后 a_i 对应的原位置，复杂度 O(n \log n)，代码：map<int , int> mp;、mp[a[i].num] = i;。
• 然后，使用优先队列取出答案前 5 大值（我为了保证正确性取了前 10 大），复杂度 O(\text{取的数的个数} \times \log n)。
• 进入每次询问：
  • 找到原位置对应的现在的位置，用 map 直接取出，复杂度 O(\log n)，代码：place = mp[u];。
  • 优先队列边界处理删除，复杂度 O(\log n)。
  • 二分查找 a_i 移动到的新时间位置，复杂度 O(\log n)。
  • 优先队列边界处理加入，复杂度 O(\log n)。
  • 此时，堆顶即为此次询问的答案，查询，复杂度 O(\log n)。
  • 别忘了恢复优先队列，复杂度 O(\text{取的数的个数} \times \log n)。

最终复杂度：O((n + m \times \text{取的数的个数}) \log n)。

如果不理解可以参照代码，但是没有注释。

参考代码

#include<bits/stdc++.h>
using namespace std;
struct p
{
    int x , t , num;
}a[100005];
struct p_ 
{
    int l , r , val;
    inline bool operator <(const p_ &other) const
    {
        return val < other.val;
    }
    inline bool operator >(const p_ &other) const
    {
        return val > other.val;
    }
}aq[15];
bool cmp(p l , p r)
{
    return l.t < r.t;
}
int n , m , u , v , ans , place , tp;
priority_queue<p_> q , qtmp;
map<int , int> mp;
int floating(int q)
{
    if(q == 0)
    {
        return 1000000007;
    }
    return q;
}
int calc(int p , int q)
{
    return abs(a[p].x - a[q].x) / floating(a[p].t - a[q].t);
}
int find(int q)
{
    int l = 1 , r = n , mid , ans = 0;
    while(l <= r)
    {
        mid = (l + r) / 2;
        if(a[mid].t < q)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i].x >> a[i].t;
        a[i].num = i;
    }
    sort(a + 1 , a + n + 1 , cmp);
    for(int i = 1 ; i <= n ; i++)
    {
        mp[a[i].num] = i;
    }
    for(int i = 2 ; i <= n ; i++)
    {
        q.push(p_{i - 1 , i , calc(i , i - 1)});
    }
    for(int i = 1 ; i <= min(n - 1 , 10) ; i++)
    {
        aq[i] = q.top();
        q.pop();
    }
    while(m--)
    {
        for(int i = 1 ; i <= min(n - 1 , 10) ; i++)
        {
            qtmp.push(aq[i]);
        }
        cin >> u >> v;
        place = mp[u];
        int l , r , val;
        l = qtmp.top().l;
        r = qtmp.top().r;
        val = qtmp.top().val;
        while(l == place || r == place)
        {
            qtmp.pop();
            l = qtmp.top().l;
            r = qtmp.top().r;
            val = qtmp.top().val;
        }
        if(place > 1 && place < n)
        {
            qtmp.push(p_{place - 1 , place + 1 , calc(place + 1 , place - 1)});
        }
        tp = find(v);
        if(tp == 0)
        {
            qtmp.push(p_{place , tp + 1 , abs(a[tp + 1].x - a[place].x) / floating(a[tp + 1].t - v)});
        }
        else if(tp == n)
        {
            qtmp.push(p_{tp , place , abs(a[place].x - a[tp].x) / floating(v - a[tp].t)});
        }
        else
        {
            qtmp.push(p_{place , tp + 1 , abs(a[tp + 1].x - a[place].x) / floating(a[tp + 1].t - v)});
            qtmp.push(p_{tp , place , abs(a[place].x - a[tp].x) / floating(v - a[tp].t)});
        }
        cout << qtmp.top().val << '\n';
        while(!qtmp.empty())
        {
            qtmp.pop();
        }
    }
    return 0;
}

赛时记录

坑点提醒

• 如果目标位置在边界，不要把两边算上，会 RE。
• 除法要注意向下取整时不出现除零错误，参照代码 floating() 函数。
• 初始状态下，可能的答案总共有 n - 1 个而不是 n 个。

STL 大法好！！！

考场手搓的非正解做法，希望大家支持（毕竟这是我写过的最长的一篇题解了），代码这么史，应该没人会抄的。