忠县网站制作,photoshop在线修图,ps软件是干什么用的,正规代运营公司题意#xff1a;nnn个点mmm条边的无向图#xff0c;qqq次询问#xff0c;每次给定s,t,L,Rs,t,L,Rs,t,L,R#xff0c;判断是否存在一条sss到ttt的路径#xff0c;使得路径上可以找到一点kkk,满足此路径s∼ks\sim ks∼k的部分标号都≥L\geq L≥L且k∼tk\sim tk∼t标号都≤R\…题意nnn个点mmm条边的无向图qqq次询问每次给定s,t,L,Rs,t,L,Rs,t,L,R判断是否存在一条sss到ttt的路径使得路径上可以找到一点kkk,满足此路径s∼ks\sim ks∼k的部分标号都≥L\geq L≥L且k∼tk\sim tk∼t标号都≤R\leq R≤R均包括端点
n,q≤2×105,m≤4×105n,q\leq2\times10^5,m\leq4\times10^5n,q≤2×105,m≤4×105
显然找到sss只走≥L\geq L≥L的点能到达的点集SSS,ttt只走≤R\leq R≤R能到达TTT判断SSS和TTT是否有交即可
分别从大到小和从小到大建出Kruscal重构树发现SSS和TTT是树上的一个子树
什么只有点权怎么建Kruscal重构树
因为你走一条边实际上受到了两个端点的限制所以直接取两个点的min/max\min/\maxmin/max当边权就可以了
然后对SSS和TTT跑dfs序设两个dfs序数组分别为dfsa,dfsbdfsa,dfsbdfsa,dfsb
那么对于uuu点可以映射成平面上的(dfsau,dfsbu)(dfsa_u,dfsb_u)(dfsau,dfsbu)
二维数点即可
因为横纵坐标分别互不相同所以写主席树会很清真
注意建Kruscal重构树的虚点不要加到主席树里面否则会出奇怪的问题
复杂度O(nlogn)O(n\log n)O(nlogn)
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#define MAXN 600005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
struct edge{int u,v;}e[MAXN];
int n,m,q;
inline bool cmp1(const edge a,const edge b){return max(a.u,a.v)max(b.u,b.v);}
inline bool cmp2(const edge a,const edge b){return min(a.u,a.v)min(b.u,b.v);}
inline int Min(const int x,const int y){return xy? x:y;}
inline int Max(const int x,const int y){return xy? x:y;}
struct KruscalRestructTree
{int f[MAXN],fa[MAXN][20],ch[MAXN][2],val[MAXN],cnt;int dfn[MAXN],ed[MAXN],pos[MAXN],tim;int find(int x){return f[x]x? x:f[x]find(f[x]);}inline void init(){cntn;for (int i1;in;i) val[i]i;for (int i1;inm;i) f[i]i;}inline void insert(int u,int v,int m(const int,const int)){ufind(u),vfind(v);if (uv) return;f[u]f[v]fa[u][0]fa[v][0]cnt;ch[cnt][0]u,ch[cnt][1]v;val[cnt]m(val[u],val[v]);}void dfs(int u){if (!u) return;pos[dfn[u]tim]u;for (int i1;i20;i) fa[u][i]fa[fa[u][i-1]][i-1];dfs(ch[u][0]),dfs(ch[u][1]);ed[u]tim;}inline void query(int u,int l,int r,int ql,int qr){if (val[u]ql||qrval[u]) return (void)(l0);for (int i19;i0;i--)if (fa[u][i]qlval[fa[u][i]]val[fa[u][i]]qr)ufa[u][i];ldfn[u],red[u];}
}S,T;
int ch[MAXN5][2],sum[MAXN5],cnt;
int rt[MAXN];
void insert(int x,int y,int l,int r,int k)
{xcnt;ch[x][0]ch[y][0],ch[x][1]ch[y][1],sum[x]sum[y]1;if (lr) return;int mid(lr)1;if (kmid) insert(ch[x][0],ch[y][0],l,mid,k);else insert(ch[x][1],ch[y][1],mid1,r,k);
}
int query(int x,int l,int r,int ql,int qr)
{if (qllrqr) return sum[x];if (qrl||rql) return 0;int mid(lr)1;return query(ch[x][0],l,mid,ql,qr)query(ch[x][1],mid1,r,ql,qr);
}
int main()
{nread(),mread(),qread();S.init(),T.init();for (int i1;im;i) e[i].uread()1,e[i].vread()1;sort(e1,em1,cmp2);for (int i1;im;i) S.insert(e[i].u,e[i].v,Min);sort(e1,em1,cmp1);for (int i1;im;i) T.insert(e[i].u,e[i].v,Max);int totS.cnt;S.dfs(tot),T.dfs(tot);for (int i1;itot;i) if (S.pos[i]n) insert(rt[i],rt[i-1],1,tot,T.dfn[S.pos[i]]);else rt[i]rt[i-1];while (q--){int s,t,l,r;sread()1,tread()1,lread()1,rread()1;int lx,rx,ly,ry;S.query(s,lx,rx,l,tot),T.query(t,ly,ry,1,r);if (!lx||!ly){puts(0);continue;}int ansquery(rt[rx],1,tot,ly,ry)-query(rt[lx-1],1,tot,ly,ry);printf(%d\n,!!ans);}return 0;
}
