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;
}