CF576C 题解

注意到 \(\sum\limits_{i=2}^N |x_{p_i} - x_{p_{i-1}}| + |y_{p_i} - y_{p_{i-1}}|\)。 本质上是两个点之间的曼哈顿距离 。

而曼哈顿最小距离生成树要 \(O(n^2 \log n)\) ，显然过不了。

注意到我们写过一个叫莫队的东西。

而莫队的复杂度为 \(O(n \sqrt n)\) ，也就是我们要求的东西。

加一点小优化，奇偶排序。

就可以过了。

怎么证明？

可以看一看这一篇博客

精简来说就是控制了左右指针跨越块的数量。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000001;
struct query{
    int l,r,id;
}q[maxn];
int n;
int sq;
bool cmp(query a,query b)
{
    if(a.l/sq==b.l/sq)
    {
        if(a.l/sq&1)
        {
            return a.r<b.r;
        }
        else
        {
            return a.r>b.r;
        }
    }
    else
    {
        return a.l<b.l;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sq=1145;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    sort(q+1,q+n+1,cmp);
    for(int i=1;i<=n;i++)
        cout<<q[i].id<<' ';
}