「APIO 2019」桥梁

题目

三天终于把\(APIO\)做完了

这题还是比较厉害的，如果不知道这是个分块应该就自闭了

考虑一个非常妙的操作，按照操作分块

我们设一个闸值\(S\)，把\(S\)个边权修改操作分成一块，把所有的边分成两类，一类是在这个块内被修改过的边，一类是没有被修改过的边

我们把没有被修改过的边按照边权离线，同时把这个块内所有的询问离线，用并查集来维护这张图，只需要保证进行一次询问之前图中只有边权大于等于它的边

进行询问的时候当然还得考虑这个块内被修改过的边的贡献，对于这个块内被修改过但是修改的时间大于当前询问的，我们直接按照原来的权值把它加入并查集；对于修改时间小于询问时间的边，我们把其最后一次被修改的权值加入并查集

这个时候只需要查询一下询问所在联通块大小就好了

我们发现这里的这些操作还需要支持撤回，所以并查集就不能路径压缩了

但是卡卡常就过去了

代码

#include<bits/stdc++.h>

#define re register

#pragma GCC optimize(3)

#pragma GCC optimize("-fcse-skip-blocks")

#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<15,stdin),S==T)?EOF:*S++)

char BB[1<<18],*S=BB,*T=BB;

const int maxn=1e5+5;

inline int read() {

    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

struct Edge{int u,v,rk,t,o,w;}e[maxn],r[maxn];

struct Ask{int o,x,y,rk;}q[maxn],g[maxn];

inline int cmp(const Edge &A,const Edge &B) {return A.o==B.o?A.w>B.w:A.o<B.o;}

inline int ctp(const Edge &A,const Edge &B) {return A.t<B.t;}

inline int cxp(const Ask &A,const Ask &B) {return A.y>B.y;}

inline int cop(const Edge &A,const Edge &B) {return A.rk<B.rk;}

int n,m,cnt,s,Q,now;

int fa[maxn],sz[maxn],st1[maxn],st2[maxn],f[maxn],top,Ans[maxn],st[maxn],pt,U[maxn],V[maxn];

inline int find(int x) {while(x!=fa[x]) x=fa[x];return x;}

inline void back(int x) {sz[st1[x]]-=sz[st2[x]];fa[st2[x]]=st2[x];}

inline void merge(int x,int y) {

    int xx=find(x),yy=find(y);

    if(xx==yy) return;

    if(sz[xx]<sz[yy]) fa[xx]=yy,sz[yy]+=sz[xx],st1[++top]=yy,st2[top]=xx;

    else fa[yy]=xx,sz[xx]+=sz[yy],st1[++top]=xx,st2[top]=yy;

}

inline void calc(int t) {

   	for(re int i=1;i<=now;i++) {

   		if(r[i].t>g[t].rk) break;

   		if(!f[r[i].rk]) st[++pt]=r[i].rk,U[pt]=r[i].u,V[pt]=r[i].v;

   		f[r[i].rk]=q[r[i].t].y;

	}

    for(re int i=now;i;--i) {

    	if(r[i].t<g[t].rk) break;

    	if(r[i].t>g[t].rk&&!f[r[i].rk]&&r[i].w>=g[t].y)

			merge(r[i].u,r[i].v);

	}

	while(pt) {

		if(f[st[pt]]>=g[t].y) merge(U[pt],V[pt]);

		f[st[pt]]=0;--pt;

	}

    Ans[g[t].rk]=sz[find(g[t].x)];

    while(top) back(top--);

}

inline void solve(int L,int R) {

    if(L>R) return;

    int H=0,tot=1;now=0;

    for(re int i=1;i<=n;i++) fa[i]=i,sz[i]=1;

    for(re int i=L;i<=R;i++)

		if(q[i].o==1) e[q[i].x].t=i,e[q[i].x].o=1,r[++now]=e[q[i].x];

			else g[++H]=q[i];

	std::sort(r+1,r+now+1,ctp);

	std::sort(g+1,g+H+1,cxp);std::sort(e+1,e+m+1,cmp);

    for(re int i=1;i<=m;i++) {

		if(e[i].o) break;

		while(tot<=H&&e[i].w<g[tot].y) calc(tot),tot++;

		int xx=find(e[i].u),yy=find(e[i].v);

		if(xx!=yy) {

	    	if(sz[xx]<=sz[yy]) sz[yy]+=sz[xx],fa[xx]=yy;

	    	else sz[xx]+=sz[yy],fa[yy]=xx;

		}

    }

    while(tot<=H) calc(tot),tot++;

    std::sort(e+1,e+m+1,cop);

    for(re int i=L;i<=R;i++) if(q[i].o==1) e[q[i].x].o=0,e[q[i].x].w=q[i].y;

}

int main() {

    n=read(),m=read();

    for(re int i=1;i<=m;i++)

		e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].rk=i;

    Q=read();s=3.4*std::sqrt(m);

    int l=1;

    for(re int i=1;i<=Q;i++) {

		q[i].o=read(),q[i].x=read(),q[i].y=read();q[i].rk=i;

		if(q[i].o==1) ++cnt;

		if(cnt>=s) solve(l,i),cnt=0,l=i+1;

    }

    solve(l,Q);

    for(re int i=1;i<=Q;i++) if(q[i].o==2) printf("%d\n",Ans[i]);

    return 0;

}

巴特西

「APIO 2019」桥梁

最新文章

热门文章