搜索引擎网站,扬州做网站的科技公司,个人开发app最简单方法,青海网站建设策划正题
题目链接:https://www.luogu.com.cn/problem/P4083 题目大意
开始时AAA和BBB各有两个礼物#xff0c;每个礼物对两个人有不同的价值#xff0c;开始时AAA会送BBB一个礼物。 对于一个收到礼物的人#xff0c;如果该礼物对他来说价值为valvalval#xff0c;那么他会回…正题
题目链接:https://www.luogu.com.cn/problem/P4083 题目大意
开始时AAA和BBB各有两个礼物每个礼物对两个人有不同的价值开始时AAA会送BBB一个礼物。 对于一个收到礼物的人如果该礼物对他来说价值为valvalval那么他会回送一个对于他来说[val,vald][val,vald][val,vald]这个范围内的礼物。 直到某个人收到价值为000的礼物就停止求对于AAA开始送的每个礼物最少要互送多少个礼物才能停止 解题思路
我们可以发现其实就是每次对于一个区间内连边然后求最短路。
我们对于AAA和BBB各自开一棵线段树然后优化一下连边从价值为000的礼物开始跑之后直接输出每个礼物的最短路即可 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includevector
using namespace std;
const int N1e5*20;
struct node{int to,next,w;
}a[N*2];
struct gnode{int x,y,w,id;
}g[N],b[N];
int n,d,num,tot,cnt,rt0,rt1;
int ls[N],in[N],f[N],w[N];
int lson[N],rson[N],v1[N],v2[N];
bool vis[N];
queueint q;
void addl(int x,int y,int w){a[tot].tox;a[tot].nextls[y];a[tot].ww;ls[y]tot;
}
void Build(int x,int l,int r,int z){xnum;if(lr){if(z)addl(x,g[l].id,0);else addl(x,b[l].id,0);return;}int mid(lr)1;Build(lson[x],l,mid,z);Build(rson[x],mid1,r,z);addl(x,lson[x],0);addl(x,rson[x],0);return;
}
void Change(int x,int L,int R,int l,int r,int pos){if(lr)return;if(LlRr){addl(pos,x,1);return;}int mid(LR)1;if(rmid)Change(lson[x],L,mid,l,r,pos);else if(lmid)Change(rson[x],mid1,R,l,r,pos);else Change(lson[x],L,mid,l,mid,pos),Change(rson[x],mid1,R,mid1,r,pos);return;
}
void SPFA(){while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!vis[y]){q.push(y);vis[y]1;}}}vis[x]0;}
}
bool cmp1(gnode x,gnode y)
{return x.xy.x;}
bool cmp2(gnode x,gnode y)
{return x.yy.y;}
int main()
{scanf(%d%d,n,d);for(int i1;in;i)scanf(%d%d,b[i].x,b[i].y),b[i].idi;for(int i1;in;i)scanf(%d%d,g[i].x,g[i].y),g[i].idin;sort(b1,b1n,cmp1);sort(g1,g1n,cmp2);numn*2;Build(rt0,1,n,0);Build(rt1,1,n,1);for(int i1;in;i)v1[i]b[i].x;for(int i1;in;i)v2[i]g[i].y;sort(b1,b1n,cmp2);sort(g1,g1n,cmp1);int link1;memset(f,0x3f,sizeof(f));for(int i1;in;i){int llower_bound(v21,v21n,b[i].y)-v2;int rupper_bound(v21,v21n,b[i].yd)-v2-1;Change(rt1,1,n,l,r,b[i].id);if(!b[i].y)q.push(b[i].id),f[b[i].id]0,vis[b[i].id]1;}for(int i1;in;i){int llower_bound(v11,v11n,g[i].x)-v1;int rupper_bound(v11,v11n,g[i].xd)-v1-1;Change(rt0,1,n,l,r,g[i].id);if(!g[i].x)q.push(g[i].id),f[g[i].id]0,vis[g[i].id]1;}SPFA();for(int i1;in;i){if(f[i]2147483647/3)printf(-1\n);else printf(%d\n,f[i]1);}
}
