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

2026年7月17日 ooliver OI

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

AT_abc380_e [ABC380E] 1D Bucket Tool

使用并查集表示一个连通块，分别用 $c o l_{i}, s t_{i}, e d_{i}$ 表示连通块 $i$ 的颜色、左端点和右端点。

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

代码：

C++

#include
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>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]

`#include
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>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;im;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;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		coutsolve(n-t+1)"\n";
	}
	return 0;
}`

P1197 [JSOI2008] 星球大战

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

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

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

代码：

C++

#include
using namespace std;

const int N=5e5+5;
int n,m,k,sum;
int fa[N],a[N],b[N],ans[N];
vector 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>x>>y;
		x++,y++;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin>>k;
	for(int i=1;i>b[i];
		b[i]++;
		a[b[i]]=1;
	}
	for(int i=1;i0;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

`#include
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>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;im;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;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		coutsolve(n-t+1)"\n";
	}
	return 0;
}`

P2391 白雪皑皑

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

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

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

代码：

C++

#include
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=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

`#include
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>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;im;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;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		coutsolve(n-t+1)"\n";
	}
	return 0;
}`

P16377 [NordicOI 2026] Name Change 改名

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

代码：

C++

#include
using namespace std;

const int N=2e5+5;
int n,m;
string s,t;
int fa[N];
vector 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>x>>y;
		fa[find(y)]=find(x);
	}
	for(int i=1;i

`#include
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>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;im;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;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		coutsolve(n-t+1)"\n";
	}
	return 0;
}`

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

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

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

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

代码：

C++

#include
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> g[N];
pair 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=0;j--)
			if(st[x][j]>1&&cnt+dis[x][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>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>a[i];
	while(l>1;
		if(check(mid)) r=mid-1,ans=mid,haveans=1;
		else l=mid+1;
	}
	if(!haveans) cout

`#include
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>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli);
	if(!cnt) return t;
	t=m,cnt--;
	for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli);
	return t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;im;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;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1];
	while(q--){
		int t;
		cin>>t;
		coutsolve(n-t+1)"\n";
	}
	return 0;
}`

P3098 [USACO13DEC] The Bessie Shuffle G

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

C++

#include
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=0;i--) if(cnt>=(1ll>n>>m>>q;
    for(int i=1;i>p[i],inv[p[i]]=i,st[i-1][0]=inv[i];
    fill(st[m],st[m]+63,m);
    for(int k=1;k>t;
        cout

`#include
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>=(1lli)&&st[t][i]!=m) t=st[t][i],cnt-=(1lli);//倍增进行逆A类洗牌
    if(!cnt) return t;
    t=m,cnt--;
    for(int i=62;i>=0;i--) if(cnt>=(1lli)) t+=(1lli),cnt-=(1lli);//剩余卡片不够m张，倍增直接取出
    return t;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;im;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;k63;k++) for(int i=0;im;i++) st[i][k]=st[st[i][k-1]][k-1];
    while(q--){
        int t;
        cin>>t;
        coutsolve(n-t+1)"\n";
    }
    return 0;
}`