题解：P11675 [USACO25JAN] Photo Op G

· · 题解

前言

好像大家都是同一个难写做法，这里分享我一个赛时的简单做法。

题解

一个初步结论是：

这是因为我们绕路的目的是避开一些 (x_i,0) \rightarrow (0,y_i) 的线段，对于任意一条路线，我们都可以通过调整成上述形式使答案不劣。具体可以手玩一下。

令我们选择的中转点为 (x',0),(0,y')，那么一条线段 (x_i,0) \rightarrow (0,y_i) 的限制可以表示为：

当 x' 确定时，上述限制确定了合法的 y' 为一个区间 [l,r]，显然我们存在以下贪心策略：

到这里我们有一个 O(n^2) 的暴力：对每个 x' 暴力维护合法区间 [l,r]，每次加入线段后暴力枚举 x' 更新答案。

重新思考上述过程，我们有以下观察：

从这个结论下手分析：我们考察 x_1 < x_2 \leq X,r_1 < Y。如果 r_2 < Y，那么 x_2 肯定优于 x_1，这种情况下最优的 x' 肯定是 \leq X 中最大的；若 l_2 > Y 或 Y \in [l_2,r_2]，那么 l_2/Y 一定是 \geq Y 的所有合法 y' 中最小的。

按照上面的分析，我们可以总结得出：

于是我们用树状数组维护每个 x_i,y_i 对应的合法区间 [l,r]，每次取出上述 O(1) 个 x_i,y_i 得到答案即可。时间复杂度 O(n \log n)。

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+10,M=1e6+10;
set<int> X1,X2,Y1,Y2;
vector<int> vec[N];
int n,T,xx[N],yy[N]; 
struct BIT1
{
    int C[M];
    BIT1(){for(int i=0;i<M;i++) C[i]=M-1;}
    inline void add(int x,int y){for(;x;x-=x&-x) C[x]=min(C[x],y);}
    inline int query(int x){int res=M-1;for(;x<M;x+=x&-x) res=min(res,C[x]);return res;}
}Xpre,Ypre;
struct BIT2
{
    int C[M];
    inline void add(int x,int y){if(!x) return;for(;x<M;x+=x&-x) C[x]=max(C[x],y);}
    inline int query(int x){int res=0;for(;x;x-=x&-x) res=max(res,C[x]);return res;}
}Xsuc,Ysuc;
inline void ins(int x,int y)
{
    if(x!=xx[0])
    {
        Xpre.add(x-1,y);Xsuc.add(x+1,y);
        Ypre.add(y-1,x);Ysuc.add(y+1,x);    
    }
    if(x<=xx[0]) X1.insert(x);else X2.insert(x);
    if(y<=yy[0]) Y1.insert(y);else Y2.insert(y);
}
inline int calcx(int x,int l,int r)
{
    if(r<yy[0]) return abs(x-xx[0])+yy[0]-r+sqrt(1ll*x*x+1ll*r*r);
    if(l>yy[0]) return abs(x-xx[0])+l-yy[0]+sqrt(1ll*x*x+1ll*l*l);
    return abs(x-xx[0])+sqrt(1ll*x*x+1ll*yy[0]*yy[0]);
}
inline int calcy(int x,int l,int r)
{
    if(r<xx[0]) return abs(x-yy[0])+xx[0]-r+sqrt(1ll*x*x+1ll*r*r);
    if(l>xx[0]) return abs(x-yy[0])+l-xx[0]+sqrt(1ll*x*x+1ll*l*l);
    return abs(x-yy[0])+sqrt(1ll*x*x+1ll*xx[0]*xx[0]);
}
inline int query()
{
    int ans=1e7;
    while(!X1.empty())
    {
        auto it=X1.end();--it;
        int rs=Xpre.query(*it),ls=Xsuc.query(*it);
        if(ls>rs) X1.erase(it);
        else
        {
            ans=min(ans,calcx(*it,ls,rs));
            break;
        }
    }
    while(!X2.empty())
    {
        auto it=X2.begin();
        int rs=Xpre.query(*it),ls=Xsuc.query(*it);
        if(ls>rs) X2.erase(it);
        else
        {
            ans=min(ans,calcx(*it,ls,rs));
            break;
        }
    }
    while(!Y1.empty())
    {
        auto it=Y1.end();--it;
        int rs=Ypre.query(*it),ls=Ysuc.query(*it);
        if(ls>rs) Y1.erase(it);
        else
        {
            ans=min(ans,calcy(*it,ls,rs));
            break;
        }
    }
    while(!Y2.empty())
    {
        auto it=Y2.begin();
        int rs=Ypre.query(*it),ls=Ysuc.query(*it);
        if(ls>rs) Y2.erase(it);
        else
        {
            ans=min(ans,calcy(*it,ls,rs));
            break;
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d%d%d",&n,&T,&xx[0],&yy[0]);vec[0].push_back(0);
    for(int i=1;i<=n;i++)
    {
        int t;
        scanf("%d%d%d",&t,&xx[i],&yy[i]);
        vec[t].push_back(i);
    }
    for(int o=0;o<T;o++)
    {
        for(auto i:vec[o]) ins(xx[i],yy[i]);
        printf("%d\n",query());
    }
    return 0;
}