XCPC Notes

Appearance

发布时间：2024-02-25

一般启发式合并本质 ​

小集合合并到大集合 时间复杂度: O(nlogn)O(nlogn)

P3201 [HNOI2009] 梦幻布丁 ​

题目描述 ​

nn 个布丁摆成一行，进行 mm 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。

例如，颜色分别为 1,2,2,11,2,2,1 的四个布丁一共有 33 段颜色.

输入格式 ​

第一行是两个整数，分别表示布丁个数 nn 和操作次数 mm。
第二行有 nn 个整数，第 ii 个整数表示第 ii 个布丁的颜色 aia_i。
接下来 mm 行，每行描述一次操作。每行首先有一个整数 opop 表示操作类型：

  • 若 op=1op = 1，则后有两个整数 x,yx, y，表示将颜色 xx 的布丁全部变成颜色 yy。
  • 若 op=2op = 2，则表示一次询问。

输出格式 ​

对于每次询问，输出一行一个整数表示答案。

样例 #1 ​

样例输入 #1 ​

4 3
1 2 2 1
2
1 2 1
2

样例输出 #1 ​

3
1

提示 ​

样例 1 解释 ​

初始时布丁颜色依次为 1,2,2,11, 2, 2, 1，三段颜色分别为 [1,1],[2,3],[4,4][1, 1], [2, 3], [4, 4]。
一次操作后，布丁的颜色变为 1,1,1,11, 1, 1, 1，只有 [1,4][1, 4] 一段颜色。

数据规模与约定 ​

对于全部的测试点，保证 1≤n,m≤1051 \leq n, m \leq 10^5，1≤ai,x,y≤1061 \leq a_i ,x, y \leq 10^6。

提示 ​

请注意，不保证颜色的编号不大于 nn，也不保证 x≠yx \neq y，mm 不是颜色的编号上限。

思路 ​

  • 两种颜色看作两个集合，利用启发式合并实现两种颜色合并
  • 维护段数，左右两边颜色不同(一边不同就多一条边，反之亦然)
cpp
set<int> S[1000010];
int ans;
int n,m;
void merge(int x,int y){
	if(x==y)return;
	if(S[x].size()>S[y].size())swap(S[x],S[y]);
	for(auto i:S[x])ans-=S[y].count(i-1)+S[y].count(i+1);
	for(auto i:S[x])S[y].insert(i);
	S[x].clear();
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		if(!S[x].count(i-1))ans++;
		S[x].insert(i);
	}
	while(m--){
		int op;
		cin>>op;
		if(op==2)cout<<ans<<"\n";
		else{
			int x,y;
			cin>>x>>y;
			merge(x,y);
		}
	}
}

树上启发式合并(dsu on tree) ​

CF600E Lomsat gelral ​

题意：
一棵树每个节点有一种颜色，某个节点的主导颜色为该子树下颜色数量最多的颜色编号，求每个节点的主导颜色和 思路：

  • 每遍历完一颗子树的点，就要把最大值清空(避免影响另一颗子树的计算)
  • 当算完所有子节点后，就要统计当前点，需要在遍历一次子节点将颜色加回来
  • 可以发现遍历的最后一棵子树不用清空
  • 将重儿子作为最后一次遍历的子树
  • 每个轻儿子被遍历的次数为到根节点轻边的数
  • 对于一条轻边，siz重儿子>=siz轻儿子siz_{重儿子}>=siz_{轻儿子} ,因此轻边最多lognlogn 条
  • 时间复杂度: O(nlogn)O(nlogn)
cpp
int color[N],siz[N],son[N],cnt[N];
vector<int> adj[N];
ll ans[N];
ll sum,mx,n;
void dfs_son(int u,int fa){
    siz[u]=1;
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs_son(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void update(int u,int fa,int sign,int pson){//将u子树的颜色加(减)到集合
    int c=color[u];
    cnt[c]+=sign;
    if(cnt[c]>mx)mx=cnt[c],sum=c;
    else if(cnt[c]==mx)sum+=c;
    for(auto v:adj[u]){
        if(v==fa||v==pson)continue;
        update(v,u,sign,pson);
    }
}
void dfs(int u,int fa,int op){
    for(auto v:adj[u]){
        if(v==fa||v==son[u])continue;
        dfs(v,u,0);
    }
    if(son[u])dfs(son[u],u,1);
    update(u,fa,1,son[u]);//更新除重儿子树外的点
    ans[u]=sum;
    if(!op)update(u,fa,-1,0),sum=mx=0;//当前节点为轻儿子，所有节点删除
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>color[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_son(1,0);
    dfs(1,0,1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<" \n"[i==n];
}

CF570D Tree Requests ​

题意：
给定一棵树，每个节点有个字母，有m次询问
每次询问子树v内深度为k的节点能否组成回文串
思路：

  • 判断一些字符是否能组成回文串，只需看字符出现数量是否小于等于1
  • 与深度有关，考虑启发式合并
  • numsi,j表示深度为i字母为j的数量nums_{i,j} 表示深度为i字母为j的数量
  • 将询问离线下来，每次更新完当前节点看是否有询问，更新答案即可
cpp
struct Q{
    int pos,dep;
};
int n,m;
vector<int> adj[N];
vector<Q> q[N];
int dep[N],siz[N],son[N],ans[N];
int nums[N][26];
string s;
int have;
void dfs_son(int u,int fa){
    siz[u]=1;
    dep[u]=dep[fa]+1;
    for(auto v:adj[u]){
        dfs_son(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void update(int u,int sign,int pson){
    int x=s[u]-'a';
    if(nums[dep[u]][x]&1)have--;
    nums[dep[u]][x]+=sign;
    if(nums[dep[u]][x]&1)have++;
    for(auto v:adj[u]){
        if(v==pson)continue;
        update(v,sign,pson);
    }
}
void dfs(int u,int op){
    for(auto v:adj[u]){
        if(v==son[u])continue;
        dfs(v,0);
    }
    if(son[u])dfs(son[u],1);
    update(u,1,son[u]);
    for(auto [pos,d]:q[u]){
        int have=0;
        for(int j=0;j<26;j++){
            have+=nums[d][j]&1;
        }
        ans[pos]=(have<=1);
    }
    if(!op)update(u,-1,0);
}
void solve(){
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        adj[x].push_back(i);
    }
    cin>>s;
    s=" "+s;
    dfs_son(1,0);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
    
        q[x].push_back({i,y});
    }
    dfs(1,1);
    for(int i=1;i<=m;i++)cout<<(ans[i]?"Yes\n":"No\n");
}

CF246E(树上启发式,线段树合并) ​

给定一片森林，每次询问一个节点的 K-Son 共有个多少不同的名字。一个节点的 K-Son 即为在该节点子树内的，深度是该节点深度加 K 的节点。

前置题目 ​

P1972 [SDOI2009] HH的项链(在序列上的做法) ​

给定一个序列，每次询问区间内有多少个不同的数

做法1：树状数组 ​

  • 可以发现若左端点恒为1,则我们只关心每个数最后出现的位置(产生贡献的位置)
  • 因此对每个询问按r排序，当枚举到当前询问的r位置时计算答案
  • 用树状数组维护前缀和，每次把前一个出现的位置减1，当前位置加1
cpp
struct ANS{
    int l,r,val,pos;
    bool operator<(const ANS&tmp)const{
        return r<tmp.r;
    }
} ans[N];
int a[N],n,m,c[N];
map<int,int> pre;
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))c[i]+=y;
}
int query(int x){
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i)){
        ans+=c[i];
    }
    return ans;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>ans[i].l>>ans[i].r;
        ans[i].pos=i;
    }
    sort(ans+1,ans+m+1);
    for(int i=1,j=1;j<=m;i++){
        if(pre[a[i]])add(pre[a[i]],-1);
        add(i,1);
        pre[a[i]]=i;
        while(i==ans[j].r){
            ans[j].val=query(ans[j].r)-query(ans[j].l-1);
            j++;
        }
    }
    vector<int> res(m+1);
    for(int i=1;i<=m;i++)res[ans[i].pos]=ans[i].val;
    for(int i=1;i<=m;i++)cout<<res[i]<<"\n";
}

做法2：可持久化线段树 ​

从左到右建不同的版本，和之前一样维护最后出现的数的贡献，询问l,r即在r的版本询问该区间和，但是数据过大tle了

CF208E Blood CousinsCD ​

定义p级表亲为在同一深度下，公共祖先为第p个祖先的点定义 p级表亲为在同一深度下，公共祖先为第p个祖先的点
每次询问每个点的p级表亲

做法1：DSU ​

将每个询问的点的对应祖先找出来，离线 问题转变为在u子树下节点深度为d的节点数(记得减1)

cpp
struct Q{
    int pos,dep;
};
vector<int> adj[N];
vector<Q> q[N];
int n,m,par[N][30],dep[N],siz[N],son[N],nums[N],ans[N];
void dfs_son(int u,int fa){
    if(!u)dep[u]=0;
    else dep[u]=dep[fa]+1;
    par[u][0]=fa;   
    for(int i=1;i<=log2(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
    siz[u]=1;
    for(auto v:adj[u]){
        dfs_son(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void update(int u,int sign,int pson){
    nums[dep[u]]+=sign;
    for(auto v:adj[u]){
        if(v==pson)continue;
        update(v,sign,pson);
    }
}
void dfs(int u,int op){
    for(auto v:adj[u]){
        if(v==son[u])continue;
        dfs(v,0);
    }
    if(son[u])dfs(son[u],1);
    update(u,1,son[u]);
    for(auto [pos,d]:q[u]){
        ans[pos]=nums[d]-1;
    }
    if(!op)update(u,-1,-1);
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        adj[x].push_back(i);
    }
    dfs_son(0,-1);
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        int yy=y;
        for(int i=25;i>=0;i--){
            if(par[x][i]>0&&y>=(1<<i))x=par[x][i],y-=(1<<i);
        }
        if(!y)q[x].push_back({i,dep[x]+yy});
    }
    dfs(0,1);
    for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
}

做法2：二分 ​

回到本题 ​

直接dsu了，有dfs+树状数组+二分的做法

cpp
struct Q{
    int pos,dep;
};
set<int> nums[N*2];
map<string,int> vis;
int idx,n,m,a[N],ans[N];
vector<int> adj[N];
vector<Q> q[N];
int dep[N],son[N],siz[N];
void dfs_son(int u,int fa){
    if(!u)dep[u]=0;
    else dep[u]=dep[fa]+1;
    siz[u]=1;
    for(auto v:adj[u]){
        dfs_son(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void update(int u,int sign,int pson){
    if(sign>0){
        if(!nums[dep[u]].count(a[u]))nums[dep[u]].insert(a[u]);
    }
    else nums[dep[u]].clear();
    for(auto v:adj[u]){
        if(v==pson)continue;
        update(v,sign,pson);
    }
}
void dfs(int u,int op){
    for(auto v:adj[u]){
        if(v==son[u])continue;
        dfs(v,0);
    }
    if(son[u])dfs(son[u],1);
    update(u,1,son[u]);
    for(auto [pos,d]:q[u]){
        ans[pos]=nums[d].size();
    }
    if(!op)update(u,-1,-1);
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(vis[s])a[i]=vis[s];
        else a[i]=++idx,vis[s]=a[i];
        int x;
        cin>>x;
        adj[x].push_back(i);
    }
    cin>>m;
    dfs_son(0,-1);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        q[x].push_back({i,dep[x]+y});
    }
    dfs(0,1);
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}

Wenwei Lin · 2022 — 2025