题解 P5443 【[APIO2019]桥梁】

Fading · 2019-07-10 23:00:26 · 题解

感谢 @soar_unprecedentedly 指出的一处错误以及提供的更优解~

算法1：

考虑最暴力的暴力：

对于每一个修改，直接修改这个边。

对于每一个询问，枚举所有边。

如果这个边的重量限制大于等于当前询问的重量，那么加入并查集。

最后看询问点所在的并查集的大小就好了。

复杂度O(Qm\alpha)

期望得分：13分。

算法2：

我们考虑对所有边，所有的询问排序（根据重量从大到小）。

有趣的是，如果没有修改操作的话，我们可以通过离线把边加入并查集的方法完美解决这个问题。

这个方法很简单，此处不再赘述。

如果有修改怎么办呢？

我们分两类边讨论：有修改的边，和无修改的边。

有些边是永远没有修改的，可以在离线的时候直接加入并查集。

对于有修改的边，我们如何处理？

可以暴力枚举。我们枚举所有修改操作，看看操作时间是否大于当前询问时间。

如果大于，不做处理。否则修改这些边。

最后根据重量大小把这些有修改的边加入并查集。

最后撤销一下加入并查集的有修改的边即可。

时间复杂度O(Q\log_2Q+m\log_2m+Q(Q+Q\log_2n))

期望得分：13分。

算法3：

算法1和算法2的瓶颈很显然：一个枚举了所有的边，一个枚举了所有的操作。

两个算法也各有优劣：

算法1在边很少的情况下非常快，直接把边改了。

算法2在询问很少的情况下非常快，而且离线了，只需要考虑修改过的边。

所以我们考虑均摊一下两个做法。

怎么均摊？

考虑分块。

对于所有询问分块。S个询问为1块。

如何对询问块进行处理？

先对第1个块内的所有询问操作,所有边按照重量排序（从大到小）。

然后我们直接照搬算法2的流程，离线，枚举每一个询问。

对于这S个操作无修改的边，直接加入并查集。

对于这S个操作内有修改的边，枚举所有这S个操作的所有修改操作。根据时间判断这些边的重量。

然后加入并查集，得到答案，再撤回，进行下一个询问。

最后我们像算法1一样，处理完这个块后，执行这个块的所有修改操作，直接把边权改了。

然后进行第2个块的操作，做完再搞第3个块...以此类推。

我们发现复杂度变得很有意思，因为一个块内最多只有S个修改操作。

时间复杂度为O(\frac QS m\log_2m+\frac QS S^2\log_2n)

即O(QS\log_2n+\frac {Qm\log_2m}{S})

时间复杂度懒得算了，特别奇怪，好像S取\sqrt{m\log_2n}跑的飞快，因为并查集常数是跑不满\log_2n的。

期望得分：100分。

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
struct edge{
    int from,to,dis,id;
}g[120001],g1[120001],g2[120001];
int tot;
inline void made(int from,int to,int dis,int id){
    g[++tot].from=from;g[tot].to=to;g[tot].dis=dis;g[tot].id=id;
}
inline bool cmp(edge a,edge b){
    return a.dis>b.dis;
}
inline bool cmpid(edge a,edge b){
    return a.id<b.id;
}
struct que{
    int opt,id,W,num;
}q[120001],cac1[120001],cac2[120001];
inline bool cmp0(que a,que b){
    return a.W>b.W;
}
int n,m,S,ans[120001],Id[120001],sz[120001],F[120001];
int find(int u){
    if (F[u]!=u) return find(F[u]);
    else return u;
}
int sta[120001][2],top;
inline void merge(int u,int v){
    int fu=find(u),fv=find(v);
    if (fu==fv) return;
    if (sz[fu]<sz[fv]) swap(fu,fv);
    F[fv]=fu;sz[fu]+=sz[fv];
    sta[++top][0]=fu;sta[top][1]=fv;
}
inline void cancel(){
    ll u=sta[top][0],v=sta[top--][1];
    sz[u]-=sz[v];F[v]=v;
}
int cnt1,cnt2,D[120001];
bool vis[120001];
int all,dl[120001],Op[120001];
inline void work(int sum){
    cnt1=all=top=cnt2=0;
    for (int i=1;i<=m;i++) vis[i]=0,D[i]=0,Id[g[i].id]=i;
    for (int i=1;i<=sum;i++){
        if (q[i].opt==1){
            cac1[++cnt1]=q[i];
            if (vis[Id[q[i].num]]) continue;
            D[Id[q[i].num]]=g[Id[q[i].num]].dis;
            vis[Id[q[i].num]]=1;
            dl[++all]=Id[q[i].num];
        }else{
            cac2[++cnt2]=q[i];
        }
    }
    for (int i=1;i<=n;i++) F[i]=i,sz[i]=1;
    sort(cac2+1,cac2+1+cnt2,cmp0);
    int pos=1;
    for (int i=1;i<=cnt2;i++){
        while (pos<=m&&g[pos].dis>=cac2[i].W){
            if (!vis[pos]) merge(g[pos].from,g[pos].to);
            pos++;
        }
        ll las=top;
        for (int j=1;j<=cnt1;j++){
            if (cac1[j].id<cac2[i].id){
                D[Id[cac1[j].num]]=cac1[j].W;
            }
        }
        for (int j=1;j<=all;j++){
            if (D[dl[j]]>=cac2[i].W){
                merge(g[dl[j]].from,g[dl[j]].to);
            }
            D[dl[j]]=g[dl[j]].dis;
        }
        ans[cac2[i].id]=sz[find(cac2[i].num)];
        for (;las!=top;) cancel();
    }
    ll tot1=0,tot2=0;
    for (int i=1;i<=sum;i++){
        if (q[i].opt==1) g[Id[q[i].num]].dis=q[i].W; 
    }
    for (int i=1;i<=m;i++){
        if (vis[i]) g1[++tot1]=g[i];
        else g[++tot2]=g[i]; 
    }
    sort(g1+1,g1+1+tot1,cmp);
    merge(g+1,g+1+tot2,g1+1,g1+1+tot1,g2+1,cmp); 
    for (int i=1;i<=m;i++) g[i]=g2[i];
}
signed main(){
    n=read(),m=read();
    S=sqrt(m*log2(n));
    for (int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        made(x,y,z,i);
    }
    int Q=read();
    sort(g+1,g+1+m,cmp);
    int cnt=0;
    for (int i=1;i<=Q;i++){
        q[++cnt].id=i;
        int op=read();q[cnt].opt=op;
        Op[i]=op;
        if (op==1){
            q[cnt].num=read(),q[cnt].W=read();
        }else{
            q[cnt].num=read(),q[cnt].W=read();
        }
        if (cnt==S) work(S),cnt=0;
    }
    if (cnt) work(cnt);
    for (int i=1;i<=Q;i++){
        if (Op[i]==2) printf("%d\n",ans[i]);
    }
    return 0;
}

算法4：

感谢 @soar_unprecedentedly 提供做法~

即O(QS\alpha+\frac {Qm\log_2m}{S})。