题解 P5163 【WD与地图】
SSerxhs
2021-05-29 00:21:10
好玄妙的题。
操作只有删边，套路反转操作顺序转化为加边。
这个题如果放在无向图上就很好做了，$1$ 操作相当于合并两个连通块，$2$ 操作相当于单点修改，$3$ 操作相当于查连通块内前 $k$ 大的和，这可以对每个节点建动态开点权值线段树， $2$ 操作直接修改，$1$ 操作线段树合并，$3$ 操作在线段树上二分就可以了。
考虑如何把这个问题转化到无向图上。不难看出，题目说的地区即为强连通分
量。如果把强连通关系看成一条无向边，那么就可以转化到无向图的情况了。
称“内边”为端点在同一强连通分量的边。不难看出，仅保留内边并将内边变为无向边的图的每个连通块对应了原图的一个强连通分量，这提示我们：如果知道每条内边两端进入属于强连通分量的时间 $t$（即无向边连接的时间），那么按照时间排序后，可以按照无向图来做。
如果只求一条内边的时间 $t$，经典的做法是二分，每次加入 $T_i\le mid$ 的边并 tarjan 判定。求所有边的时间 $t$，可以考虑整体二分。**注意 $t$ 和 $T$ 是不一样的（$T$ 是原边加入时间）。**
考虑会遇到什么问题。整体二分的一个关键处理是：当二分答案区间 $[mid+1,r]$ 时，$[l,mid]$ 贡献必须考虑。在主席树模板等题目中的处理手段是 $kth\gets kth-x$，其中 $x$ 是 $[l,mid]$ 对答案的贡献，但强连通关系显然不具可减性。同时，也不能暴力保留 $T_i\in [l,mid]$ 的边，否则复杂度不正确。
一个对于上述复杂度不正确做法的剪枝的思路是先把 $[l,mid]$ 形成的强连通分量缩点，对于 $t_i\le mid $ （由整体二分的性质，到这一步已经可以判断每个边 $t$ 和 $mid$ 的关系）的边，它已经成为了内边，对 $[mid+1,r]$ 没有贡献，可以去掉。（如果始终先做 $[l,mid]$ 再做 $[mid+1,r]$，那么相当于这条边永久无效了。）对于 $t_i>mid$ 的边，它仍然可能对后面做贡献，继续保留这条边。
看起来好像有什么不对劲的？
$t_i>mid$，意味着这条边本来就会被整体二分扔到 $[mid+1,r]$ 去。从整体二分复杂度正确性的角度，只要每次二分过程中每个操作被分到至多一侧，且每次操作都和操作序列区间长度成线性关系就可以保证复杂度。那么在 $[mid+1,r]$ 有用的边本就是答案在 $[mid+1,r]$ 的边，即有用的边数也和操作序列成线性关系。
那么整体二分是正确的。至于缩点，用并查集维护一下就可以了。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
std::mt19937 rnd(time(0));
inline int sj(int n)
{
unsigned int x=rnd();
return x%n+1;
}
#define rand fst
template<typename typC> void read(register typC &x)
{
register int c=getchar(),fh=1;
while ((c<48)||(c>57))
{
if (c=='-') {c=getchar();fh=-1;break;}
c=getchar();
}
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
x*=fh;
}
template<typename typC, typename... Args> void read(typC &first, Args& ... args) {
read(first);
read(args...);
}
template<typename typC> void read(register typC *a,int num)
{
for (register int i=1;i<=num;i++) read(a[i]);
}
template<typename typC> void write(register typC x)
{
if (x<0) putchar('-'),x=-x;
static int st[100];
register int tp=1;
register typC y;st[1]=x%10;x/=10;
while (x) y=x/10,st[++tp]=x-y*10,x=y;++tp;
while (--tp) putchar(st[tp]|48);
}
template<typename typC> void write(register typC *a,register int num)
{
for (register int i=1;i<=num;i++) write(a[i]),putchar(i==num?10:32);
}
template<typename typC> typC ab(register typC x)
{
if (x<0) return -x;
return x;
}
#define space(x) write(x),putchar(32)
#define enter(x) write(x),putchar(10)
typedef pair<int,int> pa;
struct P
{
int t,u,v;
P(int c=0,int a=0,int b=0):t(c),u(a),v(b){}
};
struct Q
{
int t,u,v,typ,id;
Q(int c=0,int a=0,int b=0,int d=0,int e=0):t(c),u(a),v(b),typ(d),id(e){}
bool operator<(const Q &o) const {return t<o.t;}
};
const int N=1e5+2,M=2e5+2,K=4e5+2,O=1e7,inf=1e9;
struct dsu
{
int f[N],rk[N],st[N][2];
int tp;
void init(int n)
{
tp=0;
for (int i=1;i<=n;i++) f[i]=i,rk[i]=1;
}
int getf(int x)
{
while (f[x]!=x) x=f[x];
return x;
}
void uni(int x,int y)
{
x=getf(x);y=getf(y);
if (x==y) return;
if (rk[x]>rk[y]) swap(x,y);
st[++tp][0]=x,st[tp][1]=rk[y];
f[x]=y;if (rk[x]==rk[y]) ++rk[y];
}
int fix()
{
return tp;
}
void roll(int ntp)
{
while (tp>ntp) rk[f[st[tp][0]]]=st[tp][1],f[st[tp][0]]=st[tp][0],--tp;
}
};
struct tarjan
{
vector<int> lj[N];
int dfn[N],low[N],st[N],f[N],a[N];
int n,tp,cnt,fs;
bool ed[N];
void init(int nn,int *b)
{
n=nn;tp=0;
memcpy(a+1,b+1,n<<2);
for (int i=1;i<=n;i++) ed[a[i]]=0;
for (int i=1;i<=n;i++) lj[a[i]].clear();
}
void add(int x,int y)
{
lj[x].push_back(y);
}
void dfs(int x)
{
dfn[x]=low[x]=++cnt;
ed[st[++tp]=x]=1;
for (auto v:lj[x]) if (!dfn[v]) dfs(v),low[x]=min(low[x],low[v]); else if (ed[v]) low[x]=min(low[x],dfn[v]);
if (dfn[x]==low[x])
{
++fs;st[tp+1]=0;
while (st[tp+1]!=x)
{
ed[st[tp]]=0;
f[st[tp--]]=fs;
}
}
}
void cal()
{
for (int i=1;i<=n;i++) dfn[a[i]]=0;cnt=0;fs=0;
for (int i=1;i<=n;i++) if (!dfn[a[i]]) dfs(a[i]);
}
};
dsu d;
tarjan g;
map<pa,int> mp;
P lb[M];
Q xw[M],w[M],st1[M],st2[M],o[K];
int c[O][2],siz[O];
ll ans[M],s[O];
int a[N],st[N],t[M],fir[N],nu[M],nv[M],f[N],rt[N];
int T,n,m,q,i,j,k,x,y,z,la,ksiz,ks,qs,tp,tp1,tp2,ds,os;
bool ed[N];
void ztef(int l,int r,int ql,int qr)
{
if (l>r||ql>qr) return;
if (l==r)
{
for (int i=ql;i<=qr;i++) t[w[i].id]=l;
return;
}
int mid=l+r>>1,i,fp=d.fix(),u,v,m;tp=tp1=tp2=0;
for (i=ql;i<=qr;i++) nu[i]=d.getf(w[i].u),nv[i]=d.getf(w[i].v);
for (i=ql;i<=qr&&w[i].t<=mid;i++) if ((u=nu[i])!=(v=nv[i]))
{
if (!ed[u]) st[++tp]=u,ed[u]=1;
if (!ed[v]) st[++tp]=v,ed[v]=1;
} else throw;
for (i=1;i<=tp;i++) ed[st[i]]=0;
for (i=1;i<=g.fs;i++) fir[i]=0;
g.init(tp,st);
for (i=ql;i<=qr&&w[i].t<=mid;i++) if (nu[i]!=nv[i]) g.add(nu[i],nv[i]);
g.cal();
for (i=1;i<=tp;i++) if (!fir[g.f[st[i]]]) fir[g.f[st[i]]]=st[i]; else d.uni(fir[g.f[st[i]]],st[i]);
for (i=ql;i<=qr;i++) if (d.getf(nu[i])==d.getf(nv[i])) st1[++tp1]=w[i]; else st2[++tp2]=w[i];
m=ql+tp1;
for (i=1;i<=tp1;i++) w[ql+i-1]=st1[i];
for (i=1;i<=tp2;i++) w[m+i-1]=st2[i];
ztef(mid+1,r,m,qr);d.roll(fp);
ztef(l,mid,ql,m-1);
}
void inc(int &x,int v,int l=0,int r=inf)
{
if (!x) x=++ds;
s[x]+=v;++siz[x];
if (l==r) return;
int mid=l+r>>1;
if (v<=mid) inc(c[x][0],v,l,mid); else inc(c[x][1],v,mid+1,r);
}
void dec(int &x,int v,int l=0,int r=inf)
{
if (!x) x=++ds;
s[x]-=v;--siz[x];
if (!siz[x]) return x=0,void();
if (l==r) return;
int mid=l+r>>1;
if (v<=mid) dec(c[x][0],v,l,mid); else dec(c[x][1],v,mid+1,r);
}
void merge(int &x,int y)
{
if (x&&y)
{
s[x]+=s[y];siz[x]+=siz[y];
merge(c[x][0],c[y][0]);
merge(c[x][1],c[y][1]);
} else x|=y;
}
int getf(int x)
{
if (f[x]==x) return x;
return f[x]=getf(f[x]);
}
ll find(int x,int kth)
{
ll res=0;
int l=0,r=1e9;
while (kth&&l<r) if (siz[c[x][1]]>kth) x=c[x][1],l=(l+r>>1)+1; else res+=s[c[x][1]],kth-=siz[c[x][1]],x=c[x][0],r=l+r>>1;
return res+(ll)l*kth;
}
int main()
{
read(n,m,q);
read(a,n);
for (i=1;i<=m;i++)
{
read(lb[i].u,lb[i].v);lb[i].t=q+1;assert(lb[i].u!=lb[i].v);
assert(mp.find(pa(lb[i].u,lb[i].v))==mp.end());
mp[pa(lb[i].u,lb[i].v)]=i;
}
for (i=1;i<=q;i++)
{
read(xw[i].typ,xw[i].u,xw[i].v);xw[i].t=q-i+1;
if (xw[i].typ==1)
{
w[++ks]=xw[i];
lb[w[ks].id=mp[pa(xw[i].u,xw[i].v)]].t=q-i+1;
}
else if (xw[i].typ==2) a[xw[i].u]+=xw[i].v;
else xw[i].id=++qs;
}
for (i=1;i<=m;i++) if (lb[i].t==q+1) w[++ks]=Q(0,lb[i].u,lb[i].v,0,i);
reverse(w+1,w+m+1);assert(ks==m);d.init(n);
ztef(0,q+1,1,m);
for (i=1;i<=n;i++) inc(rt[i],a[i]);
for (i=1;i<=n;i++) f[i]=i;
for (i=q;i;i--) if (xw[i].typ!=1) o[++os]=xw[i];
for (i=1;i<=m;i++) o[++os]=Q(t[i],lb[i].u,lb[i].v,1,0);
sort(o+1,o+os+1);
for (i=1;i<=os;i++)
{
if (o[i].typ==1)
{
x=getf(o[i].u);y=getf(o[i].v);
if (x==y) continue;
merge(rt[x],rt[y]);f[y]=x;
}
if (o[i].typ==2)
{
x=getf(o[i].u);
dec(rt[x],a[o[i].u]);
inc(rt[x],a[o[i].u]-=o[i].v);
}
if (o[i].typ==3)
{
x=rt[getf(o[i].u)];
ans[o[i].id]=siz[x]<=o[i].v?s[x]:find(x,o[i].v);
}
}
for (i=1;i<=qs;i++) enter(ans[i]);
}
```