ZR 集训 Day1 - 基础数据结构及其应用

AT_abc380_e [ABC380E] 1D Bucket Tool

使用并查集表示一个连通块，分别用 $col_i,st_i,ed_i$ 表示连通块 $i$ 的颜色、左端点和右端点。

进行修改操作时，要向当前连通块的左右两边看看能否合并。

代码：

C++

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,q;
int fa[N],col[N],siz[N],st[N],ed[N];

int find(int x){
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}

int main(){
    cin>>n>>q;
	for(int i=1;i<=n;i++) fa[i]=col[i]=st[i]=ed[i]=i,siz[i]=1;
	while(q--){
		int op,x,c;
		cin>>op>>x;
		if(op==1){
			cin>>c;
			x=find(x);
			siz[col[x]]-=ed[x]-st[x]+1;
			siz[c]+=ed[x]-st[x]+1;
			col[x]=c;
			if(st[x]>1){
				int l=find(st[x]-1);
				if(c==col[l]){
					fa[l]=x;
					st[x]=st[l];
				}
			}
			if(ed[x]<n){
				int r=find(ed[x]+1);
				if(c==col[r]){
					fa[r]=x;
					ed[x]=ed[r];
				}
			}
		}
		else cout<<siz[x]<<"\n";
	}
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,q;
int p[N],inv[N],st[N][70];

int solve(int x){//x表示
	int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1));
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)&&st[t][i]!=m) t=st[t][i],cnt-=(1ll<<i);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)) t+=(1ll<<i),cnt-=(1ll<<i);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
	fill(st[m],st[m]+63,m);
	for(int k=1;k<63;k++) for(int i=0;i<m;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		cout<<solve(n-t+1)<<"\n";
	}
	return 0;
}

P1197 [JSOI2008] 星球大战

并查集是不支持删除的，但这道题需要我们对并查集进行删除操作。

不难想到，我们离线并倒着进行处理，这时，删除操作就变成了加边，这题就可做了。

坑点：点从 $0$ 开始计数。

代码：

C++

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,m,k,sum;
int fa[N],a[N],b[N],ans[N];
vector<int> g[N];

int find(int x){
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}

int main(){
    cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		x++,y++;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>b[i];
		b[i]++;
		a[b[i]]=1;
	}
	for(int i=1;i<=n;i++){
		if(a[i]) continue;
		sum++;
		for(int u:g[i]){
			if(a[u]) continue;
			int x=find(i),y=find(u);
			if(x==y) continue;
			fa[x]=y,sum--;
		}
	}
	for(int i=k;i>0;i--){
		ans[i]=sum;
		int u=b[i];
		a[u]=0;
		sum++;
		for(int v:g[u]){
			if(a[v]) continue;
			int x=find(v),y=find(u);
			if(x==y) continue;
			fa[x]=y,sum--;
		}
	}
	ans[0]=sum;
	for(int i=0;i<=k;i++) cout<<ans[i]<<"\n";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,q;
int p[N],inv[N],st[N][70];

int solve(int x){//x表示
	int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1));
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)&&st[t][i]!=m) t=st[t][i],cnt-=(1ll<<i);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)) t+=(1ll<<i),cnt-=(1ll<<i);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
	fill(st[m],st[m]+63,m);
	for(int k=1;k<63;k++) for(int i=0;i<m;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		cout<<solve(n-t+1)<<"\n";
	}
	return 0;
}

P2391 白雪皑皑

不难发现，后面的操作会覆盖前面的颜色，这是一个令人头疼的问题。

根据上面的思路，可以想到倒着进行操作，用连通块并查集维护那些被染了色的块，每次进行操作时找到区间可以染色的来染色。

染色时，我们将当前格子的父亲设为它右边格子，这样下次访问到这个格子时就可以直接跳过。

代码：

C++

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,m,p,q;
int fa[N],col[N],st[N],ed[N];

int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

int main(){
    cin>>n>>m>>p>>q;
	for(int i=1;i<=n+1;i++) fa[i]=st[i]=ed[i]=i;
	for(int i=m;i>=1;i--){
		int l=((i*q+p)%n)+1,r=((i*p+q)%n)+1;
		if(l>r) swap(l,r);
		for(int j=l;j<=r;){
            if(col[j]==0) fa[j]=j+1,col[j]=i;
			j=find(j);
        }
	}
	for(int i=1;i<=n;i++) cout<<col[i]<<"\n";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,q;
int p[N],inv[N],st[N][70];

int solve(int x){//x表示
	int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1));
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)&&st[t][i]!=m) t=st[t][i],cnt-=(1ll<<i);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)) t+=(1ll<<i),cnt-=(1ll<<i);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
	fill(st[m],st[m]+63,m);
	for(int k=1;k<63;k++) for(int i=0;i<m;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		cout<<solve(n-t+1)<<"\n";
	}
	return 0;
}

P16377 [NordicOI 2026] Name Change 改名

能交换的两个位置我们连一条边，易正同一连通块内的位置是可以互相交换的，所以我们用并查集维护，最后判断每个联通块对应的两个字符集是否相等。

代码：

C++

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int n,m;
string s,t;
int fa[N];
vector<int> a[N],b,c;

int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

int main(){
    cin>>n>>m>>s>>t;
	s="#"+s,t="#"+t;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		fa[find(y)]=find(x);
	}
	for(int i=1;i<=n;i++) a[find(i)].push_back(i);
	for(int i=1;i<=n;i++){
		if(a[i].empty()) continue;
		for(int x:a[i]) b.push_back(s[x]),c.push_back(t[x]);
		sort(b.begin(),b.end());
		sort(c.begin(),c.end());
		for(int j=0;j<b.size();j++) if(b[j]!=c[j]){
			cout<<"No";
			return 0;
		}
		b.clear(),c.clear();
	}
	cout<<"Yes";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,q;
int p[N],inv[N],st[N][70];

int solve(int x){//x表示
	int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1));
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)&&st[t][i]!=m) t=st[t][i],cnt-=(1ll<<i);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)) t+=(1ll<<i),cnt-=(1ll<<i);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
	fill(st[m],st[m]+63,m);
	for(int k=1;k<63;k++) for(int i=0;i<m;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		cout<<solve(n-t+1)<<"\n";
	}
	return 0;
}

P1084 [NOIP 2012 提高组] 疫情控制

倍增题，尝试封锁根节点的子节点。

不难发现答案具有单调性，可以二分答案。

这里使用倍增，先贪心地往上跳，如果可以跳到根节点，就先让它呆在根节点儿子处，再找到所有需要驻扎的根节点儿子，进行贪心配对。

代码：

C++

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=6e4+5;
int n,m,t,at,bt,ct,l,r,mid,ans;
int d[N],a[N],st[N][20],dis[N][20],hav[N],ned[N];
bool haveans,sta[N],nd[N];
vector<pair<int,int>> g[N];
pair<int,int> h[N];

void dfs1(int x,int fa){
	for(auto u:g[x]){
		int y=u.first,z=u.second;
		if(y==fa) continue;
		d[y]=d[x]+1;
		st[y][0]=x,dis[y][0]=z;
		for(int j=1;j<=t;j++){
			st[y][j]=st[st[y][j-1]][j-1];
			dis[y][j]=dis[y][j-1]+dis[st[y][j-1]][j-1];
		}
		dfs1(y,x);
	}
}

bool dfs2(int x){
	bool p=0;
	if(sta[x]) return 1;
	for(auto u:g[x]){
		int y=u.first;
		if(d[y]<d[x]) continue;
		p=1;
		if(!dfs2(y)) return 0;
	}
	if(!p) return 0;
	return 1;
}

bool check(int lim){
	memset(sta,0,sizeof sta);
	memset(nd,0,sizeof nd);
	ct=at=bt=0;
	for(int i=1;i<=m;i++){
		int x=a[i],cnt=0;
		for(int j=t;j>=0;j--)
			if(st[x][j]>1&&cnt+dis[x][j]<=lim){
				cnt+=dis[x][j];
				x=st[x][j];
			}
		if(st[x][0]==1&&cnt+dis[x][0]<=lim) h[++ct]=make_pair(lim-cnt-dis[x][0],x);
		else sta[x]=1;
	}
	for(auto u:g[1]) if(!dfs2(u.first)) nd[u.first]=1;
	sort(h+1,h+ct+1);
	for(int i=1;i<=ct;i++){
		if(nd[h[i].second]&&h[i].first<dis[h[i].second][0]) nd[h[i].second]=0;
		else hav[++at]=h[i].first;
	}
	for(auto u:g[1]) if(nd[u.first]) ned[++bt]=dis[u.first][0];
	if(at<bt) return 0;
	sort(hav+1,hav+at+1),sort(ned+1,ned+bt+1);
	int i=1,j=1;
	while(i<=bt&&j<=at){
		if(hav[j]>=ned[i]) i++,j++;
		else j++;
	}
	if(i>bt) return 1;
	return 0;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	t=log2(n)+1;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
		r+=z;
	}
	d[1]=1;
	dfs1(1,0);
	cin>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid,haveans=1;
		else l=mid+1;
	}
	if(!haveans) cout<<-1;
	else cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,q;
int p[N],inv[N],st[N][70];

int solve(int x){//x表示
	int cnt=min(x,n-m+1),t=max(0ll,x-(n-m+1));
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)&&st[t][i]!=m) t=st[t][i],cnt-=(1ll<<i);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)) t+=(1ll<<i),cnt-=(1ll<<i);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
	fill(st[m],st[m]+63,m);
	for(int k=1;k<63;k++) for(int i=0;i<m;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		cout<<solve(n-t+1)<<"\n";
	}
	return 0;
}

P3098 [USACO13DEC] The Bessie Shuffle G

考虑对操作进行逆操作，直接模拟会超时，想到使用倍增，详细的看代码实现：

C++

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,q;
int p[N],inv[N],st[N][70];

int solve(int x){//x表示需要当前卡片是第几轮被取出的
    int cnt=min(x,n-m+1),//cnt表示需要经历的A类洗牌的次数
        t=max(0ll,x-(n-m+1));//t表示A类洗牌后的位置
    for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)&&st[t][i]!=m) t=st[t][i],cnt-=(1ll<<i);//倍增进行逆A类洗牌
    if(!cnt) return t;
    t=m,cnt--;
    for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)) t+=(1ll<<i),cnt-=(1ll<<i);//剩余卡片不够m张，倍增直接取出
    return t;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
    fill(st[m],st[m]+63,m);
    for(int k=1;k<63;k++) for(int i=0;i<m;i++) st[i][k]=st[st[i][k-1]][k-1];
    while(q--){
        int t;
        cin>>t;
        cout<<solve(n-t+1)<<"\n";
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+5;
int n,m,q;
int p[N],inv[N],st[N][70];

int solve(int x){//x表示需要当前卡片是第几轮被取出的
    int cnt=min(x,n-m+1),//cnt表示需要经历的A类洗牌的次数
        t=max(0ll,x-(n-m+1));//t表示A类洗牌后的位置
    for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)&&st[t][i]!=m) t=st[t][i],cnt-=(1ll<<i);//倍增进行逆A类洗牌
    if(!cnt) return t;
    t=m,cnt--;
    for(int i=62;i>=0;i--) if(cnt>=(1ll<<i)) t+=(1ll<<i),cnt-=(1ll<<i);//剩余卡片不够m张，倍增直接取出
    return t;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++) cin>>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
    fill(st[m],st[m]+63,m);
    for(int k=1;k<63;k++) for(int i=0;i<m;i++) st[i][k]=st[st[i][k-1]][k-1];
    while(q--){
        int t;
        cin>>t;
        cout<<solve(n-t+1)<<"\n";
    }
    return 0;
}