容易得出一种暴力算法:将询问按 \(w\) 排序,将没有修改的边按 \(d\) 排序。对于每个询问 \((t_i,s_i,w_i)\),做两部分操作(这里 \(t\) 是时间的意思):
- 将没有修改的边中满足 \(d_i\ge w_i\) 的边加入并查集。
- 遍历所有修改 \((T_j,b_j,r_j)\),若 \(T_j<t_i\),则修改 \(b_j\)。然后遍历这些有修改的边,将满足条件的边加入并查集。
查询到答案后,将第二部分操作撤回。
将边加入并查集是指将边连接的两个连通块合并。
可以发现,如果没有第二部分,时间复杂度为 \(\mathcal O(q+m\log n)\)。
而第二部分需要遍历满足条件的所有修改,非常浪费时间。
我们可以考虑将第二部分中的一些修改转化为第一部分。假设有一个标准 \(T\),满足 \(\forall i,t_i\ge T\),那么可以将所有的满足 \(T_j<T\) 的修改直接打到 \(d\) 上,这些修改操作就变成了第一部分。
因此,我们将询问按时间排序,然后分块考虑。对于每一块来说,块内最小的 \(t\) 就是我们要找的标准。所以首先确保将小于 \(t\) 的修改打到 \(d\) 上。需要对修改按时间排序。
将块内按 \(w\) 排序,直接跑暴力算法,但是只遍历 \(T_j\in [T,t_{\max}]\) 的修改,最后撤回所有操作。那么处理一个块的第一部分时间复杂度为 \(\mathcal O(m\log n)\),第二部分时间复杂度为 \(\mathcal O(L^2\log n)\),。其中 \(L\) 是块长。
解释一下第二部分的时间复杂度:修改总数虽然是 \(\mathcal O(q)\) 的,但是分块后由于每一块需要遍历的修改都不同,因此平均每块的修改是 \(\mathcal O(L)\) 的。
这个算法总时间复杂度为
\[\mathcal O(\frac qL(m\log n+L^2\log n))=\mathcal O(\frac{qm\log n}L+qL\log n)) \]忽略了预处理的时间复杂度,因为它们不值一提。
实现有亿点复杂。
有一个细节让我调了很久:遍历一个块内的询问时,注意在暴力算法中 “没有修改的边” 的集合会发生变化。
\(L\) 的取值自己算。
下面是 AC 代码(不建议参考,可能会 TLE):
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e4+5,M=1e5+5;
int n,m,L,Q,u[M],v[M],d[M],dd[M],b[M],r[M],t[M],cnt1,cnt2,ans[M],top,fa[N],hei[N],siz[N];
bool chd[M];vector<int>vp;struct Opt{int x,y;bool z;}sta[M];
int get(int x){return x==fa[x]?x:get(fa[x]);}
inline void merge(int x,int y){
x=get(x);y=get(y);if(x==y)return;
if(hei[x]>hei[y])swap(x,y);
sta[++top]={x,y,hei[x]==hei[y]};fa[x]=y;siz[y]+=siz[x];if(hei[x]==hei[y])hei[y]++;
}
inline void erase(){
if(sta[top].z)hei[sta[top].y]--;
siz[sta[top].y]-=siz[sta[top].x];fa[sta[top].x]=sta[top].x;top--;
}
struct Query{
int s,w,pos;friend bool operator<(const Query&A,const Query&B){return A.w>B.w;}
}q[M];
bool cmpWeight(const int&A,const int&B){return d[A]<d[B];}
int main(){
scanf("%d%d",&n,&m);L=sqrt(m*log(n))/2;
for(int i=1;i<=n;i++)fa[i]=i,siz[i]=hei[i]=1;
for(int i=1;i<=m;i++)scanf("%d%d%d",u+i,v+i,d+i);
scanf("%d",&Q);for(int i=1,op;i<=Q;i++){
scanf("%d",&op);if(op==1){t[++cnt1]=i;scanf("%d%d",b+cnt1,r+cnt1);}
else{q[++cnt2].pos=i;scanf("%d%d",&q[cnt2].s,&q[cnt2].w);}
}
for(int i=1,st,ed,fi,tl,tot=1;i<=cnt2;i+=L){
st=i;ed=min(i+L-1,cnt2);vp.clear();fi=top;tl=q[ed].pos;
while(tot<=cnt1&&t[tot]<q[st].pos)d[b[tot]]=r[tot],tot++;
for(int k=tot;k<=cnt1&&t[k]<tl;k++)chd[b[k]]=1;
for(int k=1;k<=m;k++)if(!chd[k])vp.push_back(k);
sort(vp.begin(),vp.end(),cmpWeight);sort(q+st,q+ed+1);
for(int j=st,topd;j<=ed;j++){
while((!vp.empty())&&d[vp.back()]>=q[j].w)merge(u[vp.back()],v[vp.back()]),vp.pop_back();
for(int k=tot;k<=cnt1&&t[k]<tl;k++)if(t[k]>q[j].pos)dd[b[k]]=d[b[k]];
topd=top;for(int k=tot;k<=cnt1&&t[k]<q[j].pos;k++)dd[b[k]]=r[k];
for(int k=tot;k<=cnt1&&t[k]<tl;k++)if(dd[b[k]]>=q[j].w)merge(u[b[k]],v[b[k]]);
ans[q[j].pos]=siz[get(q[j].s)];while(top>topd)erase();
}
for(int k=tot;k<=cnt1&&t[k]<tl;k++)chd[b[k]]=0;
while(top>fi)erase();
}
for(int i=1;i<=Q;i++)if(ans[i])printf("%d\n",ans[i]);
return 0;
}
标签:APIO2019,sta,int,题解,top,mathcal,P5443,hei,log
From: https://www.cnblogs.com/hihihi198/p/16882078.html