luogu P5471 [NOI 2019] 점프

luogu
점 이 직사각형 영역 으로 연결 되 어 있 기 때문에 2 차원 데이터 구 조 를 최적화 할 수 있 습 니 다. 하지만 MLE. 사각형 의 데이터 구 조 를 유지 하 는 데 \ (KD - tree \) 가 있 기 때문에 \ (KDT \) 최적화 연결, 공간 복잡 도 \ (m \ sqrt n \) 를 고려 하여 통과 할 수 없습니다.
더 나 아가 한 문제 의 끝 은 몇 개의 \ (KDT \) 에 있 는 점 과 연 결 된 다음 에 이 점 들 의 하위 트 리 가 이 점 에 의 해 업 데 이 트 됩 니 다. \ (dijkstra \) 과정 을 고려 하여 매번 \ (dis \) 의 가장 작은 점 을 꺼 내 고 다른 점 을 업데이트 합 니 다. 그리고 다른 점 이 현재 가장 작은 \ (dis x + w i \) 에 의 해 업데이트 되면 더 이상 업 데 이 트 될 수 없습니다. 그러면 우 리 는 매번 가장 작은 \ (dis x + w i \) 를 꺼 낼 수 있 습 니 다.그리고 폭력 업데이트 \ (x \) 에 대응 하 는 점 과 하위 트 리 를 삭제 합 니 다. 이 점 의 확장 과 삭 제 된 총 횟수 는 \ (O (n) \) 회 이기 때문에 공간 \ (O (n) \), 시간 \ (O (mlogn + m \ sqrt n) \) 을 할 수 있 습 니 다.

#include
#define LL long long
#define uLL unsigned long long
#define db double

using namespace std;
const int N=70000+10,M=150000+10,inf=2109876543;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int n,m,di[N],ii=0,e[M][5];
bool cmp(int aa,int bb){return e[aa][0] ee[N];
vector::iterator it[N];
struct node
{
    int x[2],i;
    bool operator < (const node &bb) const {return x[ii]!=bb.x[ii]?x[ii]r) return 0;
    int mid=(l+r)>>1;
    nth_element(b+l,b+mid,b+r+1);
    int x=b[mid].i,ndd=ii^1;
    sz[x]=1;
    ii=ndd,ch[x][0]=bui(l,mid-1),fa[ch[x][0]]=x,sz[x]+=sz[ch[x][0]];
    ii=ndd,ch[x][1]=bui(mid+1,r),fa[ch[x][1]]=x,sz[x]+=sz[ch[x][1]];
    lx[x]=min(a[x].x[0],min(lx[ch[x][0]],lx[ch[x][1]]));
    rx[x]=max(a[x].x[0],max(rx[ch[x][0]],rx[ch[x][1]]));
    ly[x]=min(a[x].x[1],min(ly[ch[x][0]],ly[ch[x][1]]));
    ry[x]=max(a[x].x[1],max(ry[ch[x][0]],ry[ch[x][1]]));
    return x;
}
struct dj
{
    int x,d;
    bool operator < (const dj &bb) const {return d>bb.d;}
};
priority_queue q2;
void updd(int x,int i,int ndi)
{
    if(!sz[x]||rx[x]e[i][2]||ry[x]e[i][4]) return;
    if(lx[x]>=e[i][1]&&rx[x]<=e[i][2]&&ly[x]>=e[i][3]&&ry[x]<=e[i][4]&&di[x]>ndi)
    {
        di[x]=ndi;
        ban[x]=1;
        int xx=x;
        while(xx) --sz[xx],xx=fa[xx];
        if(it[x]!=ee[x].end()) q2.push((dj){x,di[x]+e[*it[x]][0]});
    }
    else if(a[x].x[0]>=e[i][1]&&a[x].x[0]<=e[i][2]&&a[x].x[1]>=e[i][3]&&a[x].x[1]<=e[i][4]&&di[x]>ndi)
    {
        di[x]=ndi;
        ban[x]=1;
        int xx=x;
        while(xx) --sz[xx],xx=fa[xx];
        if(it[x]!=ee[x].end()) q2.push((dj){x,di[x]+e[*it[x]][0]});
    }
    updd(ch[x][0],i,ndi);
    updd(ch[x][1],i,ndi);
}

int main()
{
    n=rd(),m=rd(),rd(),rd();
    for(int i=1;i<=n;++i)
    {
        a[i].x[0]=rd(),a[i].x[1]=rd(),a[i].i=i;
        b[i]=a[i],di[i]=inf;
    }
    lx[0]=ly[0]=inf,rx[0]=ry[0]=-1;
    rt=bui(2,n);
    for(int i=1;i<=m;++i)
    {
        ee[rd()].push_back(i);
        for(int j=0;j<=4;++j)
            e[i][j]=rd();
    }
    for(int i=1;i<=n;++i)
        sort(ee[i].begin(),ee[i].end(),cmp),it[i]=ee[i].begin();
    q2.push((dj){1,(di[1]=0)+e[*it[1]][0]});
    while(!q2.empty())
    {
        int x=q2.top().x;
        q2.pop();
        updd(rt,*it[x],di[x]+e[*it[x]][0]);
        if((++it[x])!=ee[x].end()) q2.push((dj){x,di[x]+e[*it[x]][0]});
    }
    for(int i=2;i<=n;++i) printf("%d
",di[i]);
    return 0;
}