题解 P5471 【[NOI2019]弹跳】

做法：思维+动态开点线段树+分块

首先我们考虑最短路做法，发现边数是级别的。一维的情况我们能用线段树优化建边，但二维呢？反正我不会。

我们想到Dijkstra的思想，每次找到dis最小的点，并用这个点去更新其他点。

我们把矩形看成点，相当于每次找出dis最小的矩形，然后更新矩形中的点。

但一次性更新矩形中的全部点肯定不现实，我们就可以每次更新矩形中的一个点即可。

现在的问题就是如何找矩形中的一个点。发现有点难办啊。

一开始我想到是用树套树找点，结果被卡空间（QAQ），两只log的空间刚好被卡，舒适。

然后我们就考虑如何优化空间。大家都知道时间换空间吧，我就是这么想的。

我们可以分块套动态开点线段树。我们对每x轴上的每一个点建一颗动态开点线段树，空间为。再维护个动态开点线段树记录每一块的情况，空间为。

总算是把空间卡进去了。

每次查询我们先找到目标的块，然后在块上的动态开点线段树上二分找到一个点即可。

由于只要找一个点，找到了就可以return。所以时间复杂度不到极限的，卡卡常就能过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define mid (l+r)/2
const int N=70285;
int n,m,size,num,cnt,top,gs,ID,w,h,x[N],y[N],LL[N],RR[N],bel[N],Ans[N],tree[N],L[(N<<6)+1000000],R[(N<<6)+1000000],sum[(N<<6)+1000000];
multiset<int>xu[2*N];
int mp[(N<<6)+1000000];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
struct node{
    int val,l,r,d,u;
};
vector<node>g[N];
bool operator < (node a,node b)
{
    return a.val>b.val;
}
priority_queue<node>q;
void update(int &rt,int l,int r,int x,int id,int val)
{
    if(!rt)rt=++cnt;
    sum[rt]+=val;
    if(l==r)
    {
        int xjh=0;
        if(mp[rt])xjh=mp[rt];
        else{
            xjh=++top;
            mp[rt]=top;
        }
        if(val==1)xu[xjh].insert(id);
        else xu[xjh].erase(id);
        return;
    }
    if(x<=mid)update(L[rt],l,mid,x,id,val);
    else update(R[rt],mid+1,r,x,id,val);
}
void change(int x,int y,int id,int val)
{
    update(tree[x],1,h,y,id,val);
    update(tree[n+bel[x]],1,h,y,id,val);
}
void Zhao(int rt,int l,int r)
{
    if(l==r)
    {
        int xjh=mp[rt];
        ID=*xu[xjh].begin();
        return;
    }
    if(sum[L[rt]])Zhao(L[rt],l,mid);
    else Zhao(R[rt],mid+1,r);
}
void query(int &rt,int l,int r,int x,int y)
{
    if(!rt)return;
    if(sum[rt]==0)return;
    if(ID!=-1)return;
    if(l==x&&r==y)
    {
        Zhao(rt,l,r);
        return;
    }
    if(y<=mid)query(L[rt],l,mid,x,y);
    else if(x>mid)query(R[rt],mid+1,r,x,y);
    else{
        query(L[rt],l,mid,x,mid);
        query(R[rt],mid+1,r,mid+1,y);
    }
}
void find(int l,int r,int d,int u)
{
    if(bel[l]==bel[r]||bel[l]+1==bel[r])
    {
        for(int i=l;i<=r;i++)
        {
            query(tree[i],1,h,d,u);
            if(ID!=-1)return;
        }
        return;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
    {
        query(tree[n+i],1,h,d,u);
        if(ID!=-1)return;
    }
    if(LL[bel[l]]==l)
    {
         query(tree[n+bel[l]],1,h,d,u);
        if(ID!=-1)return;       
    }
    else{
        for(int i=l;i<=RR[bel[l]];i++)
        {
            query(tree[i],1,h,d,u);
            if(ID!=-1)return;
        }
    }
    if(RR[bel[r]]==r)
    {
         query(tree[n+bel[r]],1,h,d,u);
        if(ID!=-1)return;       
    }
    else{
        for(int i=LL[bel[r]];i<=r;i++)
        {
            query(tree[i],1,h,d,u);
            if(ID!=-1)return;
        }
    }
}
void write(int x)
{
    if(x<10)
    {
        putchar('0'+x);
        return;
    }
    write(x/10);
    putchar('0'+x%10);
}
signed main()
{
    freopen("jump.in","r",stdin);
    freopen("jump.out","w",stdout);
    n=read();m=read();w=read();h=read();w=h=0;
    for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),l=read(),r=read(),d=read(),u=read();
        w=max(w,r);
        h=max(h,u);
        g[x].push_back((node){y,l,r,d,u});
    }
    size=sqrt(w);
    num=w/size;
    if(w%size)num++;
    for(int i=1;i<=num;i++)LL[i]=w+1;
    for(int i=1;i<=w;i++)
    {
        bel[i]=(i-1)/size+1;
        LL[bel[i]]=min(LL[bel[i]],i);
        RR[bel[i]]=max(RR[bel[i]],i);
    }
    for(int i=2;i<=n;i++)change(x[i],y[i],i,1);
    gs=1;
    for(int i=0;i<g[1].size();i++)
    {
        node u=g[1][i];
        q.push((node){u.val,u.l,u.r,u.d,u.u});
    }
    while(gs<n)
    {
        if(q.empty())break;
        node u=q.top();
        ID=-1;
        find(u.l,u.r,u.d,u.u);
        if(ID==-1)
        {
            q.pop();
            continue;
        }
        Ans[ID]=u.val;
        change(x[ID],y[ID],ID,-1);
        for(int i=0;i<g[ID].size();i++)
        {
            node x=g[ID][i];
            q.push((node){u.val+x.val,x.l,x.r,x.d,x.u});
        }
        gs++;
    }
    for(int i=2;i<=n;i++)write(Ans[i]),putchar('\n');
    return 0;
}