[Codeforces Round #334(Div.1)] 603E-Pastoral Oddities

一道很棒的分治题
题目页面(603E)


这个题做法目前来看有三种:
1.LCT维护最小生成树;
2.cdq分治(或整体二分);
3.线段树分治
实际上第2种方法是最好写的……不过就是跑的有点慢(应该是我的写法问题)。
那接下来就介绍一下第二种写法吧(


首先可以发现,一个连通块是满足条件的,当且仅当连通块的点数为偶数。
也就是说,连通块的点数为奇数时就不行。由此可见,当 $n\bmod 2==1$ 时答案全都为 $-1$。
然后这个题要求所有合法连通块中最大的边(这题非要把 edge 说成 path,导致我一开始以为是要求最长最短路最短禁止套娃)。所以不难想到,我们所需要的边一定在这个连通块的最小生成树上。
我们首先将所有的边按照权值从小到大排序,像Kruskal那样。
考虑分治:我们令 $solve(l,r,low,up)$ 表示当前处理的区间为 $[l,r]$,答案的区间为 $[low,up]$。接下来,就考虑怎么统计答案。
考虑Kruskal算法:我们需要用并查集来维护这棵树,这道题我们也可以用相同的方法,不过由于会带有删边操作(将 $x$ 到其父亲 $fx$ 这条边删掉),那么我们的并查集也就得支持撤销操作,所以不能写路径压缩。为了优化,我们可以将按秩合并优化放上去,即将小树接到大树的根上,这样均摊下来复杂度不会太高。
然后就是分治过程:每一次我们计算 $mid=(l+r)>>1$ 的答案。由于我们当前要计算的答案区间为 $[low,up]$,那么 $[l,mid]$ 的这些边中,可能会有一些边的权值小于等于 $low$。可以发现:对于一个连通块,连的边越多越好(连通块合法的前提下)。那么我们就将这些边加上去,对应的点就用并查集搞起来。之后,我们再将权值在 $[low,up]$ 中的边从小到大依次加进去,用 $cnt$ 记录不合法的连通块数量($cnt$ 一开始为 $n$),那么加完边或者加到中间 $cnt=0$ 的话说明当前存在一个合法方案,答案就是最后加的那条边的权值。
然后就是cdq分治或者整体二分的套路了:我们将并查集过程中更新过的这些根用一个栈存起来,每一次统计完就将这些点与其父亲相连的边删掉即可,否则会重复统计答案。
代码中 $low$ 和 $up$ 并没有直接代表权值,而是相当于将权值离散化一下得到的权值下标之类的东西。这样可以优化一点常数。
……不过仍然比较慢就是了。

#include <bits/stdc++.h>
#define ll long long
#define ls id<<1
#define rs id<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=300050;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int f[N];
int n,m,cnt,h;
ll ans[N];
int s[N],siz[N];
struct edge
{
    int x,y;ll w;
    int id;
}e[N],g[N];
inline bool cmp(const edge &x,const edge &y)
{
    return (x.w==y.w)?x.id<y.id:x.w<y.w;
}
inline void Union(int x,int y)
{
    int rkx=0,rky=0;
    while(x!=f[x])x=f[x],rkx++;
    while(y!=f[y])y=f[y],rky++;
    if(x==y)return;
    if(rkx>rky)swap(x,y);
    cnt-=(siz[x]&1)+(siz[y]&1)-((siz[x]+siz[y])&1);
    f[x]=y;siz[y]+=siz[x];
    s[++h]=x;
}
inline void del(int x)
{
    int fx=f[x];
    siz[fx]-=siz[x];f[x]=x;
    cnt+=(siz[fx]&1)+(siz[x]&1)-((siz[x]+siz[fx])&1);
}
void solve(int l,int r,int low,int up)
{
    if(l>r)return;
    int mid=(l+r)>>1,las=h,ansmid=low;
    int id=e[mid].id;
    for(int i=l;i<=mid;++i)
        if(e[i].w<=low)Union(e[i].x,e[i].y);
    for(int i=low;i<=up&&cnt;++i,ansmid++)
        if(g[i].id<=mid)Union(g[i].x,g[i].y);
    ansmid=max(low,ansmid-1);
    if(cnt==0)ans[id]=g[ansmid].w;
    else ans[id]=-1;
    while(h>las)del(s[h]),h--;
    for(int i=low;i<=ansmid;++i)
        if(g[i].id<=l)Union(g[i].x,g[i].y);
    solve(l,mid-1,ansmid,up);
    while(h>las)del(s[h]),h--;
    for(int i=l;i<=mid;++i)
        if(e[i].w<=low)Union(e[i].x,e[i].y);
    solve(mid+1,r,low,ansmid);
    while(h>las)del(s[h]),h--;
}
int main()
{
    cin>>n>>m;cnt=n;
    for(int i=1;i<=n;++i)f[i]=i,siz[i]=1;
    if(n&1){for(int i=1;i<=m;++i)puts("-1");return 0;}
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%lld",&e[i].x,&e[i].y,&e[i].w);
        e[i].id=i;g[i]=e[i];
    }
    sort(g+1,g+m+1,cmp);
    for(int i=1;i<=m;++i)e[g[i].id].w=i;
    solve(1,m,1,m);
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
    return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注