loj #3145. 「APIO 2019」桥梁

loj #3145. 「APIO 2019」桥梁

填坑系列

高级数据结构不好直接维护，暴力的话时间复杂度又太高，于是考虑分块

对于每一个块内的操作，我们将所有边分成在块内修改过的边和没有修改过的边，块内询问按权值从大到小排序。

对于每个询问，先在并查集中加入所有没有修改过的边，这个可以使用类似离线的方法处理；之后我们暴力遍历块内所有修改过的边，得到在这个询问时间之前的这些边的权值，然后将比询问权值大的边加入并查集中，并在查询完答案之后撤销以便进行下一次询问，所以需要可撤销的并查集

处理完块内的所有询问之后，更新所有修改过边的权值，这里为了减少一个\(log\)的时间使用的归并排序

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
const int N=1000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct edgenode{
    int u,v,w,id;
}edge[100100],tmpe[100100],tmp1[100100];
bool cmp1(edgenode p,edgenode q) {return p.w>q.w;}

struct qnode{
    int id,x,y,op;
}q[100100],q1[100100],q2[100100];
bool cmp2(qnode p,qnode q) {return p.y>q.y;}
int n,m,qcnt=0,ans[100100],fa[50050],siz[50050],noww[100100],id[100100],tot1=0,tot2=0,tp=0,sta[50060];
bool vis[100100];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

int find(int x) {if (fa[x]==x) return x;else return find(fa[x]);}

void Merge(int u,int v)
{
    int fx=find(u),fy=find(v);
    if (fx!=fy)
    {
        if (siz[fx]<siz[fy]) swap(fx,fy);
        fa[fy]=fx;siz[fx]+=siz[fy];
        sta[++tp]=fy;
    }
}

void apart(int x)
{
    int fx=fa[x];
    siz[fx]-=siz[x];fa[x]=x;
}

void work()
{
    memset(vis,0,sizeof(vis));
    tot1=0;tot2=0;
    rep(i,1,qcnt)
    {
        if (q[i].op==1) {vis[q[i].x]=1;q1[++tot1]=q[i];}
        else q2[++tot2]=q[i];
    }
    rep(i,1,m) id[edge[i].id]=i;
    sort(q2+1,q2+1+tot2,cmp2);
    rep(i,1,n) {fa[i]=i;siz[i]=1;}tp=0;
    int pos=1;
    rep(i,1,tot2)
    {
        while ((pos<=m) && (edge[pos].w>=q2[i].y))
        {
            if (!vis[edge[pos].id]) Merge(edge[pos].u,edge[pos].v);
            pos++;
        }
        int pre=tp;
        rep(j,1,tot1) noww[q1[j].x]=edge[id[q1[j].x]].w;
        rep(j,1,tot1)
        {
            if (q1[j].id<=q2[i].id) noww[q1[j].x]=q1[j].y;
        }
        rep(j,1,tot1)
        {
            if (noww[q1[j].x]>=q2[i].y) 
                Merge(edge[id[q1[j].x]].u,edge[id[q1[j].x]].v);
        }
        ans[q2[i].id]=siz[find(q2[i].x)];
        while (tp>pre)
        {
            apart(sta[tp]);tp--;
        }
    }
    rep(i,1,tot1) edge[id[q1[i].x]].w=q1[i].y;
    tot1=0;tot2=0;
    rep(i,1,m)
    {
        if (vis[edge[i].id]) tmpe[++tot1]=edge[i];
        else tmp1[++tot2]=edge[i];
    }
    sort(tmpe+1,tmpe+1+tot1,cmp1);
    merge(tmpe+1,tmpe+1+tot1,tmp1+1,tmp1+1+tot2,edge+1,cmp1);
    sort(edge+1,edge+1+m,cmp1); 
}

int main()
{
    n=read();m=read();
    rep(i,1,m)
    {
        edge[i].u=read();edge[i].v=read();edge[i].w=read();
        edge[i].id=i;
    }
    sort(edge+1,edge+1+m,cmp1);
    int Q=read();
    rep(i,1,Q)
    {
        q[++qcnt].id=i;q[qcnt].op=read();
        q[qcnt].x=read();q[qcnt].y=read();
        if (qcnt==N) {work();qcnt=0;}
    }
    if (qcnt) work();
    rep(i,1,Q)
        if (ans[i]) printf("%d\n",ans[i]);
    return 0;
}

loj #3145. 「APIO 2019」桥梁

原文：https://www.cnblogs.com/encodetalker/p/11167332.html