[DS记录]P5163 WD与地图
command_block
·
·
个人记录
题意 : 给出一张有向图,要求支持下列操作 :
-
删除一条边
-
将 u 的点权增加 c
-
求 u 所在强连通分量中,前 k 大的点权和
允许离线。
------------
这个 $\rm idea$ 应该最初是 $\bf{d}{\color{red}uls}$ 的。
删边维护 $\rm SCC$ ,一脸不可做的样子,考虑时光倒流,变成加边。
仍然不好直接做,考虑求出每条边被“缩起来”的时间。
如果能求出这个,维护强连通性就和无向图连通性一样简单了……剩余的操作就是线段树合并了。
发现“缩起来”是具有单调性的，可考虑**整体二分**。
先考虑朴素的判定，不难想到将出现时间 $\leq mid$ 的边全部建立，然后缩点。
此时若某条边两端在同一个强连通分量内，则其被缩起来的时间 $\leq mid$。
接下来改进为整体二分。
我们希望能够得到 $\leq mid$ 的边集的缩点情况，似乎并没有显然的做法。
先不考虑复杂度，观察一下这个算法的行为。
每次分治时，会将当前边集分成左右两部分，其中左半部满足已经缩起来。
这样，我们处理右半部时，左边的所有边的贡献就只有强连通性，没有所谓的 $\rm DAG$ 边。
换句话说，整体二分会把缩不起来的 $\rm DAG$ 边丢到后面继续缩。
这样，我们就只需要传递连通性。
可以只用并查集维护 $[1,l)$ 中边的强连通性，然后加入 $[l,mid]$ 内的边来跑。
具体流程就是 ：
- 把 $[l,mid]$ 的边加入缩好强连通性的图中。
- 跑 `tarjan` 来缩点，为了保证复杂度，注意不要遍历没有边相连的点。
- 把边划分为两个部分。
- 将新产生的强连通性加入并查集。
- 将边集清空。
- 求解右儿子。
- 将本层产生的强连通性从并查集中撤回。
- 求解左儿子。
复杂度 $O(n\log^2n)$。
`1h`写,`30min`调,居然是最优解……
```cpp
#include<algorithm>
#include<cstdio>
#include<map>
#define ll long long
#define Pr pair<int,int>
#define mp make_pair
#define MaxN 100500
#define MaxM 200500
using namespace std;
int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct UFS
{
int f[MaxN],c[MaxN],sx[MaxN],sy[MaxN],tot;
void Init(int n)
{for (int i=1;i<=n;i++){f[i]=i;c[i]=1;}}
int find(int u)
{return f[u]==u ? u : find(f[u]);}
void merge(int x,int y){
x=find(x);y=find(y);
if (x==y)return ;
if (c[x]>c[y])swap(x,y);
c[f[x]=y]+=c[x];
sx[++tot]=x;sy[tot]=y;
}
void undo(int lim)
{
while(tot>lim){
int x=sx[tot],y=sy[tot];
c[y]-=c[f[x]=x];
tot--;
}
}
}F;
struct sLine{int f,t,p;}l[MaxM],sl[MaxM];
struct Line{int t,nxt;}g[MaxM];
int tl,fir[MaxN],st[MaxN],tot,vis[MaxN],vf;
void adl(int f,int t){
if (vis[f]<vf)vis[st[++tot]=f]=vf;
if (vis[t]<vf)vis[st[++tot]=t]=vf;
g[++tl]=(Line){t,fir[f]};fir[f]=tl;
}
int dfn[MaxN],low[MaxN],stk[MaxN],top,tim;
bool in[MaxN];
void clear(){
for (int i=1;i<=tot;i++)
fir[st[i]]=dfn[st[i]]=low[st[i]]=0;
tl=tot=tim=0;
}
void dfs(int u)
{
low[u]=dfn[u]=++tim;
in[stk[++top]=u]=1;
for (int i=fir[u],v;i;i=g[i].nxt)
if (dfn[v=g[i].t]){
if (in[v])low[u]=min(low[u],dfn[v]);
}else {dfs(v);low[u]=min(low[u],low[v]);}
if (low[u]==dfn[u]){
while(stk[top]!=u){
F.merge(stk[top],stk[top-1]);
in[stk[top--]]=0;
}in[stk[top--]]=0;
}
}
int n;
void solve(int tl,int tr,int pl,int pr)
{
if (pl>pr)return ;
if (tl==tr){
for (int i=pl;i<=pr;i++)l[i].p=tl;
return ;
}int mid=(tl+tr)>>1,savt=F.tot;
vf++;
for (int i=pl;i<=pr;i++)
if (l[i].p<=mid)
adl(F.find(l[i].f),F.find(l[i].t));
for (int i=1;i<=tot;i++)
if (!dfn[st[i]])dfs(st[i]);
clear();
int pmid=pl-1,nr=0;
for (int i=pl;i<=pr;i++)
if (F.find(l[i].f)==F.find(l[i].t)&&l[i].p<=mid)
l[++pmid]=l[i];
else sl[++nr]=l[i];
for (int i=1;i<=nr;i++)l[pmid+i]=sl[i];
solve(mid+1,tr,pmid+1,pr);
F.undo(savt);
solve(tl,mid,pl,pmid);
}
struct Node
{int l,r,c;ll s;}a[MaxN*60];
int to,wfc,tn;
const int lim=1000000000;
void add(int l,int r,int &u)
{
if (!u)u=++tn;
a[u].c+=wfc;
if (l==r){a[u].s+=wfc*l;return ;}
int mid=(l+r)>>1;
if (to<=mid)add(l,mid,a[u].l);
else add(mid+1,r,a[u].r);
a[u].s=a[a[u].l].s+a[a[u].r].s;
}
int merge(int x,int y)
{
if (!x||!y)return x|y;
a[x].c+=a[y].c;
a[x].s+=a[y].s;
if (a[x].l||a[x].r){
a[x].l=merge(a[x].l,a[y].l);
a[x].r=merge(a[x].r,a[y].r);
}return x;
}
ll qry(int l,int r,int u,int k)
{
if (l==r)return 1ll*min(k,a[u].c)*l;
int mid=(l+r)>>1,rc=a[a[u].r].c;
if (k<=rc)return qry(mid+1,r,a[u].r,k);
return qry(l,mid,a[u].l,k-rc)+a[a[u].r].s;
}
bool cmpL(const sLine &A,const sLine &B)
{return A.p<B.p;}
struct Data{int op,a,b;}b[MaxM];
map<Pr,int> tpl;
int m,q,x[MaxN],rt[MaxN];
ll ans[MaxM];int na;
int main()
{
n=read();m=read();q=read();
for (int i=1;i<=n;i++)x[i]=read();
for (int i=1;i<=m;i++){
l[i].f=read();l[i].t=read();
tpl[mp(l[i].f,l[i].t)]=i;
}
for (int i=1;i<=q;i++){
b[i].op=read();
b[i].a=read();
b[i].b=read();
if (b[i].op==2)
x[b[i].a]+=b[i].b;
}reverse(b+1,b+q+1);
for (int i=1;i<=q;i++)
if (b[i].op==1)
l[tpl[mp(b[i].a,b[i].b)]].p=i;
F.Init(n);
solve(0,q+1,1,m);
sort(l+1,l+m+1,cmpL);
for (int i=1;i<=n;i++){
to=x[i];wfc=1;
add(0,lim,rt[i]);
}
for (int i=0,p=1;i<=q;i++){
while(p<=m&&l[p].p==i){
int u=F.find(l[p].f),v=F.find(l[p].t);
if (u!=v){
int srt=merge(rt[u],rt[v]);
F.merge(u,v);
rt[F.find(u)]=srt;
}p++;
}if (b[i].op==2){
int u=F.find(b[i].a);
to=x[b[i].a];wfc=-1;add(0,lim,rt[u]);
to=(x[b[i].a]-=b[i].b);wfc=1;add(0,lim,rt[u]);
}if (b[i].op==3){
int u=F.find(b[i].a);
ans[++na]=qry(0,lim,rt[u],b[i].b);
}
}for (int i=na;i;i--)printf("%lld\n",ans[i]);
return 0;
}
```