题解：P10278 [USACO24OPEN] Painting Fence Posts S

· · 题解

先考虑建图，我们把所有横坐标相同的点放在一起，按照它们的纵坐标排序，设下标为 j（从 1 开始），我们需要让奇数的 j 向 j+1 连边，也就是在横坐标相同时，从小开始两个点之间连一条线段，连过的点不能再练（相当于间隔地连边）。这样我们就练完了所有竖边，连横边类似。

之后再选择一个点跑深搜，把每一个遍历到的点加入，相当于破环为链。

处理询问，假设现在我们给定了 (x1,y1),(x2,y2)，在所有 x 或 y 相同的点中利用二分找出这个点所在的线段，以及这个点所在线段的两个端点。接着比较 4 个点中，选择哪两个点最近（注意这里比较的时候要加上起始的位置，不能只比较柱子的距离）。找到最优的点对就直接差分了。

后面直接前缀和即可。

:::success[代码]

#include<bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
typedef long long ll;

struct edge{int to,w,nex;};
int n,m,x[M],y[M],hea[M],cnt,p[M],tot,id[M];
ll sum[M],ans[M],last,d[M];
bool vis[M];
edge g[M<<1];
map<pair<int,int>,int> mp;
map<int,vector<pair<int,int> > > gx,gy,px,py;
void add(int fro,int to,int w){g[++cnt]={to,w,hea[fro]},hea[fro]=cnt;}

void dfs(int u,int h)
{
    last=h;
    if(vis[u])
        return;
    vis[u]=1;
    p[++tot]=u;
    id[u]=tot;
    sum[tot]=h;
    for(int i=hea[u],v=g[i].to,w=g[i].w;i;i=g[i].nex,v=g[i].to,w=g[i].w)
        dfs(v,w);
}

ll dis(int i,int j)
{
    if(sum[i]>sum[j])
        swap(i,j);
    return min(sum[j]-sum[i],sum[tot]-sum[j]+sum[i]);
}

void calc(int l,int r)
{
    // cout<<"["<<l<<' '<<r<<"] ";
    d[l]++;
    d[r+1]--;
}

int main()
{
    // freopen("sample.in","r",stdin);
    // freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        gx[x[i]].push_back({y[i],i});
        gy[y[i]].push_back({x[i],i});
        mp[{x[i],y[i]}]=i;
    }
    for(auto i:gx)
    {
        auto &k=i.second;
        stable_sort(k.begin(),k.end());
        int len=k.size();
        for(int j=0;j<len;j+=2)
        {
            int h=k[j+1].first-k[j].first;
            add(k[j].second,k[j+1].second,h);
            add(k[j+1].second,k[j].second,h);
            px[i.first].push_back({k[j].first,k[j+1].first});
        }
    }
    for(auto i:gy)
    {
        auto &k=i.second;
        stable_sort(k.begin(),k.end());
        int len=k.size();
        for(int j=0;j<len;j+=2)
        {
            int h=k[j+1].first-k[j].first;
            add(k[j].second,k[j+1].second,h);
            add(k[j+1].second,k[j].second,h);
            py[i.first].push_back({k[j].first,k[j+1].first});
        }
    }
    dfs(1,0);
    p[++tot]=1;
    sum[tot]=last;
    for(int i=1;i<=tot;i++)
        sum[i]+=sum[i-1];
    // for(int i=1;i<=tot;i++)
    //  cout<<p[i]<<' ';cout<<'\n';
    for(int _=1;_<=n;_++)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        int flag1=0,flag2=0;
        ll a=0,b=0,c=0,d=0;
        int l,r;
        if(mp[{x1,y1}])
            l=r=mp[{x1,y1}];
        else
        {
            auto it=upper_bound(px[x1].begin(),px[x1].end(),make_pair(y1,0));
            if(it!=px[x1].begin()&&(--it)->second>=y1)
            {
                l=mp[{x1,it->first}];
                r=mp[{x1,it->second}];
                a=y1-it->first;
                b=it->second-y1;
                if(y1!=it->first&&y1!=it->second)
                    flag1=1;
            }
            else
            {
                it=upper_bound(py[y1].begin(),py[y1].end(),make_pair(x1,0));
                it--;
                l=mp[{it->first,y1}];
                r=mp[{it->second,y1}];
                a=x1-it->first;
                b=it->second-x1;
                if(x1!=it->first&&x1!=it->second)
                    flag1=1;
            }
        }
        int p,q;
        if(mp[{x2,y2}])
            p=q=mp[{x2,y2}];
        else
        {
            auto it=upper_bound(px[x2].begin(),px[x2].end(),make_pair(y2,0));
            if(it!=px[x2].begin()&&(--it)->second>=y2)
            {
                p=mp[{x2,it->first}];
                q=mp[{x2,it->second}];
                c=y2-it->first;
                d=it->second-y2;
                if(y2!=it->first&&y2!=it->second)
                    flag2=1;
            }
            else
            {
                it=upper_bound(py[y2].begin(),py[y2].end(),make_pair(x2,0));
                it--;
                p=mp[{it->first,y2}];
                q=mp[{it->second,y2}];
                c=x2-it->first;
                d=it->second-x2;
                if(x2!=it->first&&x2!=it->second)
                    flag2=1;
            }
        }
        if(l==p&&q==r&&flag1&&flag2)
        {
            // cout<<"Null\n";
            continue;
        }
        l=id[l];
        r=id[r];
        p=id[p];
        q=id[q];
        // cout<<l<<' '<<r<<' '<<p<<' '<<q<<" : ";
        ll h=min(min(dis(l,p)+a+c,dis(l,q)+a+d),min(dis(r,p)+b+c,dis(r,q)+b+d));
        if(dis(l,p)+a+c==h)
        {
            if(sum[l]>sum[p])swap(l,p);
            if(sum[p]-sum[l]>sum[tot]-sum[p]+sum[l])
                calc(1,l),calc(p,tot);
            else
                calc(l,p);
        }
        else if(dis(l,q)+a+d==h)
        {
            if(sum[l]>sum[q])swap(l,q);
            if(sum[q]-sum[l]>sum[tot]-sum[q]+sum[l])
                calc(1,l),calc(q,tot);
            else
                calc(l,q);
        }
        else if(dis(r,p)+b+c==h)
        {
            if(sum[r]>sum[p])swap(r,p);
            if(sum[p]-sum[r]>sum[tot]-sum[p]+sum[r])
                calc(1,r),calc(p,tot);
            else
                calc(r,p);
        }
        else if(dis(r,q)+b+d==h)
        {
            if(sum[r]>sum[q])swap(r,q);
            if(sum[q]-sum[r]>sum[tot]-sum[q]+sum[r])
                calc(1,r),calc(q,tot);
            else
                calc(r,q);
        }
        // cout<<'\n';
    }
    for(int i=1;i<=tot;i++)
        d[i]+=d[i-1];
    for(int i=1;i<tot;i++)
        ans[p[i]]=d[i];
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

:::