渭南建站,推进门户网站建设工作,怎么下载html中的视频,网站在线开放端口正题
题目链接:https://www.luogu.com.cn/problem/P3247 题目大意 nnn个点mmm条边#xff0c;每条边有(x,y,a,b)(x,y,a,b)(x,y,a,b)。qqq次询问(x′,y′,a′,b′)(x,y,a,b)(x′,y′,a′,b′)表示询问是否存在一条x′−y′x-yx′−y′的路径使得路径上amaxa′,bma…正题
题目链接:https://www.luogu.com.cn/problem/P3247 题目大意
nnn个点mmm条边每条边有(x,y,a,b)(x,y,a,b)(x,y,a,b)。qqq次询问(x′,y′,a′,b′)(x,y,a,b)(x′,y′,a′,b′)表示询问是否存在一条x′−y′x-yx′−y′的路径使得路径上amaxa′,bmaxb′a_{max}a,b_{max}bamaxa′,bmaxb′ 解题思路
考虑暴力的做法我们用加入所有a≤a′a\leq aa≤a′且b≤b′b\leq bb≤b′的边加入然后看x′y′xyx′y′是否在同一连通块且联通块中a,ba,ba,b最大值是否是a′,b′a,ba′,b′。
如何优化我们把所有的边根据aia_iai的权值分成若干个块对于每个块我们把所有a′aa′在这个范围的内的询问进行处理我们把所有处理的询问和在块前面的边按照bbb排序然后这一部分我们就用指针扫描加入对于在块里的边我们就暴力扫描加入。
但是每个询问做完之后注意块里的边要删去所以我们不能用路径压缩用按秩合并即可。
时间复杂度O(qmlogn)O(q\sqrt m\log n)O(qmlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includecmath
using namespace std;
const int N1e510;
struct node{int x,y,a,b,s;
}e[N],q[N],cl[N];
int n,m,Q,tot,p[N];
int fa[N],siz[N],A[N],B[N];
bool ans[N];
bool cmpa(node x,node y)
{return x.ay.a?(x.by.b):(x.ay.a);}
bool cmpb(node x,node y)
{return x.by.b?(x.ay.a):(x.by.b);}
int find(int x)
{return fa[x]x?x:find(fa[x]);}
int read() {int x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
void unionn(int x,int y,int a,int b){xfind(x),yfind(y);if(siz[x]siz[y])swap(x,y);cl[tot](node){x,y,A[y],B[y],siz[y]};A[y]max(max(A[x],A[y]),a);B[y]max(max(B[x],B[y]),b);if(x!y)fa[x]y;siz[y]max(siz[y],siz[x]1);return;
}
void Clear(){for(int itot;i1;i--){fa[cl[i].x]cl[i].x;A[cl[i].y]cl[i].a;B[cl[i].y]cl[i].b;siz[cl[i].y]cl[i].s;}tot0;return;
}
int main()
{
// freopen(multiple5.in,r,stdin);
// freopen(data.out,w,stdout);nread();mread();for(int i1;im;i)e[i].xread(),e[i].yread(),e[i].aread(),e[i].bread();Qread();for(int i1;iQ;i)q[i].xread(),q[i].yread(),q[i].aread(),q[i].bread(),q[i].si;sort(e1,e1m,cmpa);sort(q1,q1Q,cmpb); int Tsqrt(m*log2(n));e[m1].a1e91;for(int k1;km;kT){int lk,rmin(kT,m);int cnt0;for(int i1;in;i)fa[i]i,A[i]B[i]-1,siz[i]0;for(int i1;iQ;i)if(q[i].ae[l].aq[i].ae[r1].a)p[cnt]i;if(!cnt)continue;if(k)sort(e1,el,cmpb);int pt1;for(int i1;icnt;i){int xp[i];while(ptle[pt].bq[x].b)unionn(e[pt].x,e[pt].y,e[pt].a,e[pt].b),pt;tot0;for(int jl;jr;j)if(e[j].aq[x].ae[j].bq[x].b)unionn(e[j].x,e[j].y,e[j].a,e[j].b);int fxfind(q[x].x),fyfind(q[x].y);ans[q[x].s]((fxfy)(A[fx]q[x].a)(B[fx]q[x].b));Clear();}}for(int i1;iQ;i)if(ans[i])printf(Yes\n);else printf(No\n);return 0;
}
