P4083 [USACO17DEC]A Pie for a Pie

· · 题解

看到其它题解都不太完善，都可以被卡成O(n^2)，这里给出严格的O(nlogn)算法。

首先，我们把Bessie做的馅饼按照Elsie的看法排序（因为Bessie要送什么馅饼取决于Elsie对蛋糕的评价），Elsie的馅饼同理。

接下来要用到一个非常重要的思想：倒序处理！我们把原题转化成从每一个价值为0的馅饼（在另一个人的看法之下）设为起点，送馅饼表示从一个馅饼转化到另一个馅饼。

于是我们发现，只要把每个馅饼向接下来可以送的馅饼（注意！由于我们是反向考虑，于是可送价值区间为[x-d,x]，其中x表示当前馅饼在别人看来的价值）连边，就转化成了一个最短路问题！

那么本题就做完了……吗？

我们发现，一个点（馅饼）可能会向很多点连边，最多n个，这导致空间复杂度可能会达到O(n^2)，时间复杂度同样。

但是，我们又可以发现，我们已经把馅饼排序，而可送价值也是一个区间，所以连边肯定是一个区间，那么我们可以通过二分查找，找到区间左端点和右端点。

然后，我们发现单点向区间连边很熟悉，这不就是线段树优化建图弱化版吗？

这里再讲一下具体过程：首先建一棵2*n的线段树，对于每一个线段树上的结点，向它的两个子结点连两条0边。接下来，倘若有结点x向区间[l,r]连边，就把[x,x]这个结点，向线段树的修改操作那样，连边即可。（具体细节参见代码）。这种算法即使是对于那些没有学真正的线段树优化建图（区间连区间）的同学（比如我）也很好理解。

还有一个细节，我们发现按照上述情况，边权只有0和1，于是，跑最短路时，我们就不必用优先队列，用双端队列即可。

P.S. 最后我看了一下最优解，发现有一个并查集优化，而且除去排序时间复杂度可以达到O(n)，但是我无法证明它的正确性，所以这里就不给出了，有兴趣可以去看看。

以下是代码：

#include<cstdio>
#include<cctype>
#include<utility>
#include<cstring>
#include<deque>
#include<algorithm>
using namespace std;
#define res register int
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) //fread优化
char buf[1<<21],*p1=buf,*p2=buf;
template<typename T>
inline void read(T &x) //快读
{
    static char ch;bool f=1;
    for(x=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=0;
    for(;isdigit(ch);x=(x<<1)+(x<<3)+ch-48,ch=getchar());x=f?x:-x;
}
template<typename T> //快输
inline void print(T x,char ch) {
    if(!x) {putchar(48);if(ch) putchar(ch);return;}
    if(x<0) putchar('-'),x=-x;
    static int Stack[sizeof(T)*3],top=-1;
    for(;x;Stack[++top]=x%10,x/=10);
    for(;~top;putchar(Stack[top--]+48));
    if(ch) putchar(ch);
}
template<typename T>
inline T max(T x,T y) {return x>y?x:y;}
template<typename T>
inline T min(T x,T y) {return x<y?x:y;}
template<typename T>
inline void chkmax(T &x,T y) {x=x>y?x:y;}
template<typename T>
inline void chkmin(T &x,T y) {x=x<y?x:y;}
struct node{
    int x,y,id;
} a[200001];
int b[200001],ver[1600001],nxt[1600001],head[1600001],edge[1600001],ans,n,m,d[800001],tot[100001];
inline void add(int x,int y,int z) {ver[++ans]=y,edge[ans]=z,nxt[ans]=head[x],head[x]=ans;}
inline bool cmp1(node x,node y) {return x.x<y.x;}
inline bool cmp2(node x,node y) {return x.y<y.y;}
void build(int q,int l,int r) {
    if(l==r) {b[l]=q;return;}
    int mid=l+r>>1;
    build(q<<1,l,mid),build(q<<1|1,mid+1,r),add(q,q<<1,0),add(q,q<<1|1,0); //向儿子结点连边
} 
void change(int q,int l1,int r1,int l,int r,int k) { //单点向区间连边
    if(r<l1||r1<l) return;
    if(l<=l1&&r1<=r) {add(k,q,1);return;}
    int mid=l1+r1>>1;
    change(q<<1,l1,mid,l,r,k),change(q<<1|1,mid+1,r1,l,r,k);
}
inline int erfen1(int x) {
    int l=n+1,r=n<<1,tot;
    if(a[r].x<x) return -1;
    while(l<=r) {
        int mid=l+r>>1;
        if(a[mid].x>=x) tot=mid,r=mid-1;else l=mid+1;
    }
    return tot;
}
inline int erfen2(int x) {
    int l=n+1,r=n<<1,tot;
    if(a[l].x>x) return -1;
    while(l<=r) {
        int mid=l+r>>1;
        if(a[mid].x<=x) tot=mid,l=mid+1;else r=mid-1;
    }
    return tot;
}
inline int erfen3(int x) {
    int l=1,r=n,tot;
    if(a[r].y<x) return -1;
    while(l<=r) {
        int mid=l+r>>1;
        if(a[mid].y>=x) tot=mid,r=mid-1;else l=mid+1;
    }
    return tot;
}
inline int erfen4(int x) {
    int l=1,r=n,tot;
    if(a[l].y>x) return -1;
    while(l<=r) {
        int mid=l+r>>1;
        if(a[mid].y<=x) tot=mid,l=mid+1;else r=mid-1;
    }
    return tot;
} //四个二分都得注意范围，不要搞错了。
deque<int> q;
inline void dijkstra() { //双端队列优化dijkstra
    for(res i=1;i<=n&&!a[i].y;++i) q.push_back(b[i]),d[b[i]]=1;
    for(res i=n+1;i<=n<<1&&!a[i].x;++i) q.push_back(b[i]),d[b[i]]=1; //这里要特别注意！起点必须是在别人看来价值为0的馅饼。
    while(!q.empty()) {
        int x=q.front();q.pop_front();
        for(res i=head[x];i;i=nxt[i])
          if(d[ver[i]]>d[x]+edge[i]) d[ver[i]]=d[x]+edge[i],edge[i]?q.push_back(ver[i]):q.push_front(ver[i]);
    }
    for(res i=1;i<=n;++i) tot[a[i].id]=d[b[i]];
}
int main()
{
    read(n),read(m);
    for(res i=1;i<=n<<1;++i) read(a[i].x),read(a[i].y),a[i].id=i;
    sort(a+1,a+1+n,cmp2),sort(a+1+n,a+1+(n<<1),cmp1),build(1,1,n<<1),memset(d,0x3f,sizeof(d));
    for(res i=1;i<=n;++i) {
        int L=erfen1(a[i].x-m),R=erfen2(a[i].x);
        if(L<0||R<0) continue;
        change(1,1,n<<1,L,R,b[i]);
    }
    for(res i=n+1;i<=n<<1;++i) {
        int L=erfen3(a[i].y-m),R=erfen4(a[i].y);
        if(L<0||R<0) continue;
        change(1,1,n<<1,L,R,b[i]);
    }
    dijkstra();
    for(res i=1;i<=n;++i) if(tot[i]>1e9) puts("-1");else printf("%d\n",tot[i]);
    return 0;
}