当前位置：首页 > news >正文

打卡信奥刷题（3194）用C++实现信奥题 P8097 [USACO22JAN] Farm Updates G

news 2026/5/1 23:11:53

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;}