首黑纪念+P5163做题报告
2026-05-02 15:54:50
发布于：广东
删帖秒置顶。
好题，喵喵题，但是代码有一些毒瘤。
看看题面。要求我们维护 个操作。
1 a b表示政府废弃了从 连向 的边，保证这条边存在。
2 a b表示政府把钱用于建设城市 ，使其发达程度增加 。
3 a b表示政府希望知道 城市所在地区发达程度前 大城市的发达程度之和。如果地区中的城市不足 个输出该地区所有城市的发达程度总和。
删除边是图一个很恶心的性质，考虑转化。注意到后面两个性质一个是查询，一个是可逆修改，因此可以把时间倒转，第二个操作变成将发达程度减少 ，废弃边改为添加边。
以下是该题的难点。
两个点 在一个地区当且仅当 可以互相到达。
如果在同一地区的定义是两点互相连通，有向边改为无向边，那么这题就是一道水到不能再水的水紫，用线段树合并维护后面两个操作就行了，基本和 [HNOI2012] 永无乡 一样，不能 想出做法、 写出代码、 调试完的小朋友们 死灭洄游记得远离盘子汗、通锐气等人。
但是要求 可以互相到达，也就是说我们要确保两点在同一个强连通分量里。可以转化成上面的简化版问题吗？如果我们知道每一条边的两个端点什么时候被缩进同一个强连通分量里，将这些边作为无向边，出现时间改成两点缩进同一个强连通分量的时间就可以按上面的做法做了。接下来考虑怎么求两点什么时候在同一个强连通分量里。注意到如果暴力加边、 和查询，时间复杂度是 的，但是这个答案是可二分的，因此：
（或者 
）
先考虑暴力整体二分，每次直接将所有出现时间大于 的边加入。明显是正确的，那么如何优化？
注意到每次二分的查询区间 里的边才是有效的。为什么？因为进入缩点更早的边可以在前面整体二分时先用并查集缩点，然后就不用考虑了。进入缩点更晚的边是没有用的，根据强连通分量的性质这些边不会为更多点在 以前进入强连通分量做出任何贡献。然后这个进入缩点的时间在整体二分中按照答案区间 刻画。这样我们只用加入当前询问区间中出现时间小于 的边（询问和修改是一体的），时间复杂度正确，剩下的就是用并查集跑缩点，但是我们这个整体二分在跑左边（原顺序，没有打乱）时需要右区间被缩点，而跑右区间时又需要右区间不被缩点，然后整体区间也要先缩一次小于等于 的点，所以需要先求解左儿子，然后撤销缩点求右儿子，这样就需要可撤销并查集，时间复杂度为 .
还能再优化。可撤销并查集很难看，能够省略它吗？考虑 hopebetter 启动注意到我们需要维护的性质比并查集好，并不需要资瓷集合的再次合并，因此只需要在每次整体二分中把左区间的所有点替换成所属的强连通分量的编号即可，右区间不做这个操作。这样你就得到了一个 ， 同时也是世界上最可爱的猫娘。
代码贴一下，不要认真研读，格式很难看并且基本是题解写法并且思路很不清晰，这一道题截至 2026/5/2 已经有 提交了，用来 ctj 也容易被逮捕的。
Ps：这题的时间限制很宽松，没有人单个测试点卡到 以上。空间限制是为线段树合并准备的。我在第二页不用找了。
#include<bits/stdc++.h>
using namespace std;
inline long long read(){
int x=0,f=1,ch=getchar_unlocked();
for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void write(long long x){
x<0?x=-x,putchar_unlocked('-'):0;static short st[19],top(0);
do st[++top]=x%10,x/=10;while(x);
while(top)putchar_unlocked(st[top--]|48);
}
#define mid (l+r>>1)
const int N=100005,M=N*60;
int n,m,q,idx,dfn[N],fa[N],low[N],be[N],cnt,s[N],rt[N],t1[M],ls[M],rs[M],st[N<<1],top;
long long t2[M];
bool ins[N];
vector<int>v[N],ex;
map<pair<int,int>,int>mp;
void init(){for(int i:ex)v[i].clear(),dfn[i]=be[i]=0;ex.clear();}
inline void link(int x,int y){ex.push_back(x),ex.push_back(y),v[x].push_back(y);}
int findfa(int u){return u==fa[u]?u:fa[u]=findfa(fa[u]);}
void dfs(int u){
dfn[u]=low[u]=++idx,st[++top]=u,ins[u]=1;
for(int v:v[u])
if(!dfn[v])
dfs(v),low[u]=min(low[u],low[v]);
else if(ins[v])low[u]=min(low[u],dfn[v]);
if(dfn[u]==low[u]){
while(st[top]^u)ins[st[top]]=0,be[st[top]]=u,--top;
--top,ins[u]=0,be[u]=u;
}
}
void tarjan(){idx=0;for(int x:ex)if(!dfn[x])dfs(x);}
void add(int &u,int l,int r,int x,int y){
if(!u)u=++cnt;
t1[u]+=y,t2[u]+=1ll*x*y;
if(l<r)x<=mid?add(ls[u],l,mid,x,y):add(rs[u],mid+1,r,x,y);
}
void merge(int &u,int v,int l,int r){if(!u||!v)u|=v;else t1[u]+=t1[v],t2[u]+=t2[v],merge(ls[u],ls[v],l,mid),merge(rs[u],rs[v],mid+1,r);}
long long qry(int u,int l,int r,int k){
if(!u||k<=0)return 0;
if(t1[u]<=k)return t2[u];
if(l==r)return 1ll*l*k;
return qry(ls[u],l,mid,k-t1[rs[u]])+qry(rs[u],mid+1,r,k);
}
struct edge{int u,v,t;void in(int i){u=read(),v=read(),t=0,mp[make_pair(u,v)]=i;}}e[N<<1];
struct Q{
int op,a,b;long long res;
void in(int i){op=read(),a=read(),b=read();if(op==1)e[mp[make_pair(a,b)]].t=i;if(op==2)s[a]+=b;}
void mccz(){int k=findfa(a);if(op==2)add(rt[k],1,1e9,s[a],-1),add(rt[k],1,1e9,s[a]-=b,1);if(op==3)res=qry(rt[k],1,1e9,b);}
}a[N<<1];
void solve(int l,int r,int ql,int qr){
if(l==r||ql>qr)return;
int ti=qr;
for(int i=qr;i>=ql;--i)if(e[i].t>mid)swap(e[ti--],e[i]);
init();
for(int i=ql;i<=ti;++i)link(e[i].u,e[i].v);
tarjan();
for(int i=ti;i>=ql;--i)
if(be[e[i].u]^be[e[i].v]||!be[e[i].u])e[i].t=mid+1,swap(e[ti--],e[i]);
for(int i=ti+1;i<=qr;++i){
if(be[e[i].u])e[i].u=be[e[i].u];
if(be[e[i].v])e[i].v=be[e[i].v];
}
solve(l,mid,ql,ti),solve(mid+1,r,ti+1,qr);
}
int main(){
n=read(),m=read(),q=read();
for(int i=1;i<=n;++i)s[i]=read();
for(int i=1;i<=m;++i)e[i].in(i);
for(int i=q;i>=1;--i)a[i].in(i);
for(int i=1;i<=n;++i)add(rt[i],1,1e9,s[i],1);
solve(0,q,1,m),iota(fa,fa+n+1,0);
for(int i=0,t=1;i<=q;++i){
if(i)a[i].mccz();
while(t<=m&&e[t].t==i){
int a=findfa(e[t].u),b=findfa(e[t].v);
if(a^b)fa[b]=a,merge(rt[a],rt[b],1,1e9);
++t;
}
}
for(int i=q;i>=1;--i)
if(a[i].op==3)write(a[i].res),putchar_unlocked('\n');
return 0;
}
第一发 NOI/NOI+/CTSC,果然是献给了整体二分呢。整体二分好可爱啊！
因为曼城茶座太可爱了，下面放几只曼城茶座。
全部评论 7
6天前 来自 广东
2
有帮助，赞一个