P8097 [USACO22JAN] Farm Updates G
题目描述
Farmer John 经营着总共NNN个农场（1≤N≤1051\le N\le 10^51≤N≤105），编号为1…N1\ldots N1…N。最初，这些农场之间没有道路连接，并且每个农场都在活跃地生产牛奶。
由于经济的动态性，Farmer John 需要根据QQQ次更新操作（0≤Q≤2⋅1050\le Q\le 2\cdot 10^50≤Q≤2⋅105）对他的农场进行改造。更新操作有三种可能的形式：
(D x)停用一个活跃的农场xxx，使其不再生产牛奶。(A x y)在两个活跃的农场xxx和yyy之间添加一条道路。(R e)删除之前添加的第eee条道路（e=1e = 1e=1是添加的第一条道路）。
一个农场xxx如果正在活跃地生产牛奶，或者可以通过一系列道路到达另一个活跃的农场，则称之为一个「有关的」农场。对于每个农场xxx，计算最大的iii（0≤i≤Q0\le i\le Q0≤i≤Q），使得农场xxx在第iii次更新后是有关的。
输入格式
输入的第一行包含NNN和QQQ。以下QQQ行每行包含如下格式之一的一次更新操作：
D x A x y R e输入保证对于 R 类更新，eee不超过已经添加的道路的数量，并且没有两次 R 类更新具有相等的eee值。
输出格式
输出NNN行，每行包含一个0…Q0\ldots Q0…Q范围内的整数。
输入输出样例 #1
输入 #1
5 9 A 1 2 A 2 3 D 1 D 3 A 2 4 D 2 R 2 R 1 R 3输出 #1
7 8 6 9 9说明/提示
【样例解释】
在这个例子中，道路以顺序(2,3),(1,2),(2,4)(2,3), (1,2), (2,4)(2,3),(1,2),(2,4)被删除。
农场111在道路(1,2)(1,2)(1,2)被删除之前是有关的。
农场222在道路(2,4)(2,4)(2,4)被删除之前是有关的。
农场333在道路(2,3)(2,3)(2,3)被删除之前是有关的。
农场444和555在所有更新结束后仍然是活跃的。所以它们一直保持为有关的，两者的输出均应为QQQ。
【数据范围】
测试点 2-5 满足N≤103N\le 10^3N≤103，Q≤2⋅103Q\le 2\cdot 10^3Q≤2⋅103。
测试点 6-20 没有额外限制。
C++实现
#include<cstdio>#include<vector>#include<cstdlib>constintN=2e5+10;intf[N];std::vector<int>vec[N];structquery{intop,x;}q[N];intans[N],vis[N];structedge{intx,y;}e[N];inttp,del[N];intgetf(intx){returnx==f[x]?x:f[x]=getf(f[x]);}inlinevoidlink(intu,intv,intnow){u=getf(u),v=getf(v);if(u==v)return;if((!vis[u])^(!vis[v])){if(!vis[u])for(autox:vec[u])vis[x]=now;elsefor(autox:vec[v])vis[x]=now;}if(vec[u].size()>vec[v].size()){f[v]=u;for(autox:vec[v])vec[u].push_back(x);}else{f[u]=v;for(autox:vec[u])vec[v].push_back(x);}}intmain(){charop[5];intx,y,n,Q;scanf("%d%d",&n,&Q);for(inti=1;i<=n;++i)f[i]=i,vis[i]=Q,vec[i].push_back(i);for(inti=1;i<=Q;++i){scanf("%s",op);if(op[0]=='A')scanf("%d%d",&x,&y),e[++tp].x=x,e[tp].y=y;elsescanf("%d",&x),q[i].op=op[0]=='D'?1:2,q[i].x=x;}for(inti=1;i<=Q;++i)if(q[i].op==1)vis[q[i].x]=0;elsedel[q[i].x]=1;for(inti=1;i<=tp;++i)if(!del[i])link(e[i].x,e[i].y,Q);for(inti=Q;i>=1;--i){if(!q[i].op)continue;if(q[i].op==1){intu=getf(q[i].x);if(!vis[u])for(autox:vec[u])vis[x]=i-1;}elselink(e[q[i].x].x,e[q[i].x].y,i-1);}for(inti=1;i<=n;++i)printf("%d\n",vis[i]);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
