3 条题解

  • 0
    @ 2026-7-19 15:34:43 
    #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[200010],m,la[200010];
struct Q{
	int x,v;
}q[200010];
int fa[200010],sz[200010],c[200010];
vector<int> v[200010];
int find(int x){
	return fa[x]=(fa[x]==x?x:find(fa[x]));
}
int now[5],ans[200010][5];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int x;
		char C;
		cin>>x>>C;
		int k=(C=='C'?1:(C=='O'?2:3));
		q[i]={x,k};//记录询问离线处理 
		la[x]=k;//记录每个点最后的颜色 
		v[x].push_back(k);//记录每个点的颜色变化 
	}
	for(int i=1;i<=n;i++){
		fa[i]=i;sz[i]=1;//初始化并查集 
	}
	for(int i=1;i<=n;i++){
		if(la[i])c[i]=la[i];//记录块的颜色 
		else{
			sz[find(a[i])]+=sz[find(i)];//向父亲合并 
			fa[find(i)]=find(a[i]);
		}
	} 
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			now[c[i]]+=sz[i];//累加初始答案 
		}
	}
	for(int i=m;i;i--){
		for(int j=1;j<=3;j++){
			ans[i][j]=now[j];//倒序记录答案 
		}
		if(v[q[i].x].size()==1){
			now[c[q[i].x]]-=sz[q[i].x];//减去修改后的答案 
			c[q[i].x]=0;
			if(find(a[q[i].x])==q[i].x)continue;//特判修改前是否有颜色 
			now[c[find(a[q[i].x])]]+=sz[q[i].x];//加上修改前的答案 
			sz[find(a[q[i].x])]+=sz[find(q[i].x)];//向父亲合并 
			fa[find(q[i].x)]=find(a[q[i].x]);
			v[q[i].x].pop_back();
		}
		else{
			now[c[q[i].x]]-=sz[q[i].x];//同理 
			v[q[i].x].pop_back();
			c[q[i].x]=v[q[i].x].back();//修改节点颜色 
			now[c[q[i].x]]+=sz[q[i].x];
		}
	} 
	for(int i=1;i<=m;i++){
		for(int j=1;j<=3;j++){
			cout<<ans[i][j]<<" \n"[j==3];//正序输出答案 
		}
	}
	return 0;
}
/*
hack:
6
5 5 5 5 5 4 
5
4 O
3 C
3 C
5 C
2 W


0 2 0
1 2 0
1 2 0
4 2 0
3 2 1
*/
    • 0
      @ 2026-7-19 14:27:47

      tmd 场上 5 min 分钟想完的思路为什么打了 1h 又调了 1h！！！

      这题其实如果只看思路的话应该只有绿，但是凭借其需要的超级码力和一百多行代码成功跻身青题行列。

      首先一看就知道这个图是一个基环森林。求完环后先不用管环，考虑环上的子树维护。易发现新的派对其实相当于单独分出一个子树并记录。但这并不容易维护，因为你要维护当前节点最近的带色祖先（或许可以用 st 表？）。

      所以考虑离线处理，先 dfs 求出所有派对举行完毕后每个派对的人数，逆向删点或换色。每次将自己的人数加到最近带色祖先（有可能是环上的其他点，这个后面再讲）。但最近带色祖先可能会先被删去，所以使用并查集维护。

      目前子树预处理完毕，考虑环上处理。这个可能会相对麻烦，处理完子树后先算出每个子树根的权值，然后前缀和计算每个带色点的最终权值（不过我似乎用的树状数组？），在这个过程中要顺便把那些非带色点的并查集变成距离他们最近的带色点。此时也顺便解决了部分子树根不带色的归属问题。

      剩下还有一些细节问题，如果一个环上的最后一个带色点被删去后，我们可以将这最后一个点的并查集父亲变成 00。

      最后由于是基环森林所以我们需要对每棵子树分别计算，但离线处理时就不需要管了。

      听着很简单，但你可以去写一写。

      #include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>G[N];
int v[N],f[N],nxt[N],len,mp[N];
stack<int>stk;
void dfs(int x)
{
	if(v[x])
	{
		while(stk.top()!=x)
			f[++len]=stk.top(),mp[stk.top()]=len,stk.pop();
		f[++len]=x;mp[x]=len;
		return ;
	}
	v[x]=1;stk.push(x);
	dfs(nxt[x]);
}
struct bcj
{
	int fa[N];bcj(){for(int i=1;i<=N-10;i++)fa[i]=i;}
	int findfa(int x){return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);}
}tr1;
int v1[N],siz[N],tag[N],ans[N][4],f1[N],len1,v2[N];
void dfs2(int x,int f)
{
	v2[x]=1;
	siz[x]=1;
	if(v1[x])f=x;
	tr1.fa[x]=f;
	for(int y:G[x])if(!mp[y])
	{
		dfs2(y,f);
		if(!v1[y])siz[x]+=siz[y];
	}
}
struct BIT
{
	int c[N],n;
	void clear(){for(int i=1;i<=n;i++)c[i]=0;}
	void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
	int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
};
struct node{int id,x;}e[N];
vector<int>now[N];
void solve(int x)
{
	len=len1=0;
	dfs(x);
	for(int i=1;i<=len;i++)dfs2(f[i],f[i]);
	BIT tr;
	tr.n=len;tr.clear();
	for(int i=1;i<=len;i++)tr.add(i,siz[f[i]]);
	for(int i=1;i<=len;i++)if(v1[f[i]])f1[++len1]=f[i];
	for(int i=1;i<len1;i++)
		siz[f1[i]]=tr.get(mp[f1[i+1]]-1)-tr.get(mp[f1[i]]-1);
	if(len1)siz[f1[len1]]=tr.get(len)-tr.get(mp[f1[len1]]-1)+tr.get(mp[f1[1]]-1);
	int ff=f1[len1];
	for(int i=1;i<=len;i++)
	{
		if(tag[f[i]])ff=f[i];
		tr1.fa[f[i]]=ff;
	}
}
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
		cin>>nxt[i],G[nxt[i]].push_back(i);
	int q;cin>>q;
	for(int i=1;i<=q;i++)
	{
		int x;string s;cin>>x>>s;
		int vv=s[0]=='C'?1:s[0]=='O'?2:3;
		e[i]={x,vv};
		v1[x]=1;tag[x]=vv;
		now[x].push_back(vv);
	}
	for(int i=1;i<=n;i++)if(!v2[i])solve(i);
	int sum[4]={0,0,0,0};
	for(int i=1;i<=n;i++)
		if(tag[i])
			sum[tag[i]]+=siz[i];
	for(int i=q;i>=1;i--)
	{
		ans[i][1]=sum[1];ans[i][2]=sum[2];ans[i][3]=sum[3];
		int id=e[i].id,t=e[i].x;
		sum[t]-=siz[id];
		now[id].pop_back();
		if(now[id].empty())
		{
			if(tr1.findfa(nxt[id])==id)
			{
				tr1.fa[id]=0;
				continue;
			}
			tr1.fa[id]=tr1.fa[nxt[id]];
			int gfa=tr1.fa[id];
			siz[gfa]+=siz[id];
			if(gfa)sum[now[gfa].back()]+=siz[id];
		}
		else sum[now[id].back()]+=siz[id];
	}
	for(int i=1;i<=q;i++)cout<<ans[i][1]<<' '<<ans[i][2]<<' '<<ans[i][3]<<'\n';
	return 0;
}
      • 0
        @ 2026-5-9 15:11:02

        图是一个由边 i→aii\rarr a_i 构成的内向基环树，把会到达同一个点的奶牛们的初始位置称作一个块儿。发现如果正着做，则块数量会越来越多，要处理块的分裂；而倒着做，块数量会越来越少，要处理块的合并。经过快速思考，发现块的合并是好处理的，所以我们倒着做。

        考虑并查集维护每个块的大小和颜色，对于撤销了点 ii 的一次操作，我们分类讨论：

        • 如果这次操作不是点 ii 上第一次染色操作，则将点 ii 的颜色改变，对应更新答案；
        • 如果这次操作是点 ii 上第一次染色操作，则点 ii 的块应当与 aia_i 所在的块合并，更新 aia_i 所在块的大小与答案。

        实现时，注意仔细处理没有颜色的块，比如写暴力跳 aia_i 直到有颜色的话就可能在没颜色的环上无限递归下去。

        赛时完整代码：

        #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<=(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define all(x) (x.begin()),(x.end())
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
int n, q, p[200010], c[200010], fa[200010], sz[200010], ans[300], vis[200010];
char typ[200010];
string s[200010];
vector<char> op[200010];
int fd(int x) {
    if (fa[x] == x)    return x;
    fa[x] = fd(fa[x]);
    typ[x] = typ[fa[x]];
    return fa[x];
}
void merge(int x, int y) {
    int fx = fd(x), fy = fd(y);
    ans[typ[fy]] -= sz[fy];
    sz[fy] += sz[fx];
    ans[typ[fy]] += sz[fy];
    fa[fx] = fy;
}
void dfs(int now) {
    if (typ[now] || vis[now])    return;
    vis[now] = 1;
    int nxt = p[now];
    dfs(fd(nxt));
    merge(now, nxt);
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    rep(i, 1, n) {
        cin >> p[i];
    }
    cin >> q;
    rep(i, 1, q) {
        cin >> c[i] >> s[i];
        op[c[i]].pb(s[i][0]);
    }
    rep(i, 1, n) {
        fa[i] = i;
        sz[i] = 1;
        if (SZ(op[i])) {
            typ[i] = op[i].back();
            ans[typ[i]]++;
        }
    }
    rep(i, 1, n) {
        dfs(i);
    }
    vector<array<int, 3>> sv;
    per(i, 1, q) {
        sv.pb({ ans['C'],ans['O'],ans['W'] });
        assert(fd(c[i]) == c[i]);
        if (SZ(op[c[i]]) == 1) {
            ans[op[c[i]].back()] -= sz[c[i]];
            typ[c[i]] = vis[c[i]] = 0;
            dfs(c[i]);
        }
        else {
            ans[op[c[i]].back()] -= sz[c[i]];
            op[c[i]].pop_back();
            ans[op[c[i]].back()] += sz[c[i]];
            typ[c[i]] = op[c[i]].back();
        }
    }
    reverse(all(sv));
    rep(i, 0, q - 1) {
        cout << sv[i][0] << " " << sv[i][1] << " " << sv[i][2] << "\n";
    }
    return 0;
}
        • 1

        [USACO26JAN1] COW Traversals G

        信息

        ID
        2198
        时间
        2000ms
        内存
        256MiB
        难度
        9
        标签
        递交数
        15
        已通过
        4
        上传者
        1. Language
        2. 兼容模式
        3. 主题
        3. Worker 0, 7ms
        4. Powered by Hydro v5.0.1 Community