luogu P5471 [NOI2019]弹跳

因为是一个点向矩形区域连边,所以可以二维数据结构优化连边,但是会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<bits/stdc++.h>

#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<'0'||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]<e[bb][0];}

vector<int> ee[N];

vector<int>::iterator it[N];

struct node

{

	int x[2],i;

	bool operator < (const node &bb) const {return x[ii]!=bb.x[ii]?x[ii]<bb.x[ii]:x[ii^1]<bb.x[ii^1];}

}a[N],b[N];

int lx[N],rx[N],ly[N],ry[N],fa[N],sz[N],ch[N][2],rt;

bool ban[N];

int bui(int l,int r)

{

	if(l>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<dj> q2;

void updd(int x,int i,int ndi)

{

	if(!sz[x]||rx[x]<e[i][1]||lx[x]>e[i][2]||ry[x]<e[i][3]||ly[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\n",di[i]);

	return 0;

}

巴特西

luogu P5471 [NOI2019]弹跳

最新文章

热门文章