网站的服务器和空间,微网站技术,百度seo关键词优化方案,哪个网站可以做创意短视频正题
题目链接:https://www.luogu.com.cn/problem/P4700 题目大意 ABA\times BAB的网格上有nnn个点#xff0c;然后mmm条有向/无向边连接成平面图#xff0c;求最左边每个点能到达的最右边点的数量。 1≤A,B≤109,1≤n≤3105,1≤m≤91051\leq A,B\leq 10^9,1\leq n\leq 3\ti…正题
题目链接:https://www.luogu.com.cn/problem/P4700 题目大意
A×BA\times BA×B的网格上有nnn个点然后mmm条有向/无向边连接成平面图求最左边每个点能到达的最右边点的数量。
1≤A,B≤109,1≤n≤3×105,1≤m≤9×1051\leq A,B\leq 10^9,1\leq n\leq 3\times 10^5,1\leq m\leq 9\times 10^51≤A,B≤109,1≤n≤3×105,1≤m≤9×105 解题思路
突破点肯定是平面图考虑假设对于左边两个点a,ba,ba,b右边两个A,BA,BA,Byyy坐标递增显然如果aaa能走到BBB且不能走到AAA那么bbb一定不能走到AAA。
也就是说每个点能到右边一定是一个区间上的点先tarjantarjantarjan缩点一下dpdpdp出这个区间就好了。
需要注意的是如果一个右边的点无法被任何左边的点走到那么它不能被统计在区间里。
时间复杂度O(nlogn)O(n\log n)O(nlogn)排序 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includestack
using namespace std;
const int N3e510;
int n,m,A,B,cnt,cot,pnt,bnt;
int X[N],Y[N],p[N],b[N],l[N],r[N];
int dfn[N],low[N],col[N],in[N];
queueint q;stackint s;
vectorint G[N],T[N];
bool ins[N],v[N];
void tarjan(int x){dfn[x]low[x]cnt;s.push(x);ins[x]1;for(int i0;iG[x].size();i){int yG[x][i];if(!dfn[y]){tarjan(y);low[x]min(low[x],low[y]);}else if(ins[y])low[x]min(low[x],dfn[y]);}if(dfn[x]low[x]){col[x]cot;while(s.top()!x){col[s.top()]cot;ins[s.top()]0;s.pop();}ins[x]0;s.pop();}return;
}
void dfs(int x){if(v[x])return;v[x]1;for(int i0;iG[x].size();i)dfs(G[x][i]);
}
void Topsort(){for(int i1;icot;i)if(!in[i])q.push(i);while(!q.empty()){int xq.front();q.pop();for(int i0;iT[x].size();i){int yT[x][i];in[y]--;l[y]min(l[y],l[x]);r[y]max(r[y],r[x]);if(!in[y])q.push(y);}}return;
}
bool cmp(int x,int y)
{return Y[x]Y[y];}
int main()
{scanf(%d%d%d%d,n,m,A,B);for(int i1;in;i)scanf(%d%d,X[i],Y[i]);for(int i1;im;i){int x,y,k;scanf(%d%d%d,x,y,k);G[x].push_back(y);if(k!1)G[y].push_back(x);}for(int i1;in;i)if(X[i]0)dfs(i);for(int i1;in;i){if(X[i]0)p[pnt]i;else if(X[i]Av[i])b[bnt]Y[i];}sort(b1,b1bnt);for(int i1;in;i)if(!dfn[i])tarjan(i);for(int i1;icot;i)l[i]bnt1,r[i]0;for(int i1;in;i)if(X[i]Av[i]){Y[i]lower_bound(b1,b1bnt,Y[i])-b;l[col[i]]min(l[col[i]],Y[i]);r[col[i]]max(r[col[i]],Y[i]);}for(int x1;xn;x)for(int i0;iG[x].size();i){int yG[x][i];if(col[x]col[y])continue;T[col[y]].push_back(col[x]);in[col[x]];}Topsort();sort(p1,p1pnt,cmp);for(int i1;ipnt;i){int xcol[p[i]];if(!r[x]){puts(0);continue;}printf(%d\n,r[x]-l[x]1);}return 0;
}
