P3740 [HAOI2014]贴海报

· · 题解

并查集

分析

题意：给出一个长度为 n 的序列和 m 次操作，第 i 次操作指定一个区间 [l,r] 使得区间中所有元素的颜色都变为 i。求所有操作结束后序列中不同颜色的数量。

由于只需要所有操作结束后序列的信息，该问题可以离线求解。

性质：时间较晚的染色操作覆盖时间较早的染色操作。

反转时间轴，从最后一次操作开始染色。元素第一次被染上的颜色就是所有操作结束后的颜色，一旦被染色就可以不再考虑。

实现

因为元素只会从未染色的变成已染色的，可以使用并查集维护序列。具体地，维护序列的连通性。

使用 f_i 表示元素 i 在并查集中的根节点。类比最小生成树，当 f_u = f_v 时节点 u 与 v 连通。维护序列时，当且仅当所有符合 i \in [u,v] 的元素 i 被染色时认为 u,v 连通。 当 l,r 连通且 l-1 与 r+1 未被染色或超出序列范围时，称 [l,r] 为一个极长连通块。

每个极长连通块与其左边的第一个元素形成一个集合，集合的根节点为连通块左边第一个元素（不在连通块内）。 这个元素显然是未染色的，否则就不符合极长连通块的定义。如此一来，通过询问元素在并查集中的祖先就可以快速找到该元素左边第一个未染色的元素（如果元素未染色则找到的是元素本身）。可以发现一个元素未被染色当且仅当 f_i=i。

删除操作只需要让被删除的元素不再被遍历到，如果想要删除元素 i，简单地将元素 i 所在的集合合并到元素 i-1 所在的集合即可。删除操作的合并是有次序的，如果将 i-1 所在的集合合并到 i 所在的集合，并查集找到的就不是每个元素左边第一个未染色的元素了。 每个元素一旦被染色就需要删除，因此删除操作至多执行 n 次。

代码总体时间复杂度 O(n\log n)，空间复杂度 O(n)，由于空间开销过大无法通过此题。代码中从右到左染色是为了防止越界。

注意：如果在开始染色时没有调用并查集初始化，可能会修改到已经染色的元素。

#include<bits/stdc++.h>
using namespace std;
struct Post{int l,r;}s[1001];
int n,m,ans,f[10000001],c[10000001];
bool on[1001];
int ask(int x){return x==f[x] ? x:f[x]=ask(f[x]);}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d",&s[i].l,&s[i].r);
    for(int i=m;i>=1;i--)
        for(int j=ask(s[i].r);j>=s[i].l;j=ask(j-1))//调用并查集初始化
            c[j]=i,f[j]=j-1;
    for(int i=1;i<=n;i++) if(c[i]&&!on[c[i]]) on[c[i]]=1,++ans;
    printf("%d\n",ans);
    return 0;
}

递归实现的路径压缩并查集会开爆栈，而使用循环实现的路径压缩并查集可以通过本题。

代码总体时间复杂度 O(n \log n)，空间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
struct Post{int l,r;}s[1001];
int n,m,ans,top,f[10000001],c[10000001],v[10000001];
bool on[1001];
int ask(int x){
    while(f[x]!=x) v[++top]=x,x=f[x];
    while(top) f[v[top]]=x,--top;//路径压缩 
    return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d",&s[i].l,&s[i].r);
    for(int i=m;i>=1;i--)
        for(int j=ask(s[i].r);j>=s[i].l;j=ask(j-1))//调用并查集初始化
            c[j]=i,f[j]=j-1;
    for(int i=1;i<=n;i++) if(c[i]&&!on[c[i]]) on[c[i]]=1,++ans;
    printf("%d\n",ans);
    return 0;
}

离散化

将序列离散化后再染色可以通过此题。事实上离散化后暴力染色的做法时间复杂度为 O(m^2)，空间复杂度为 O(m)，完全可以通过本题，但笔者是为了并查集做法写的题解，所以还是写并查集了。

只对区间的左右端点离散化无法通过此题。 这会导致序列原有的信息丢失。

在离散化时额外加入区间右端点右边的元素和区间左端点左边的元素即可使染色操作在正确位置中止。实际上从右到左染色时加入左端点左边的元素已经足够保证正确性，从左到右则相反。

Code

时间复杂度 O(m\log m)，空间复杂度 O(m)，能够通过全部测试点。