题目大意
有一个简单有向图。每个点有点权。
有三种操作：
- 修改点权
- 删除一条边
- 询问和某个点在同一个强连通分量中的点的前 \(k\) 大点权和。
\(n\leq 100000,m,q\leq 200000\)
题解
把操作反过来，每次只有加边操作。
用线段树维护同一个强连通分量内的点的点权。
用整体二分去计算每条边的两个端点被合并的时间。
每次把加入时间 \(\leq tmid\) 的边拿出来跑一次 tarjan，就可以知道哪些边在 \(\leq tmid\) 的时间内被缩掉了。
用带撤回的并查集维护即可。
时间复杂度：\(O((n+m+q)\log^2 n)\)
代码
#pragma GCC optimize ("-O2")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
#include<map>
using namespace std;
using std::min;
using std::max;
using std::swap;
using std::sort;
using std::reverse;
using std::random_shuffle;
using std::lower_bound;
using std::upper_bound;
using std::unique;
using std::vector;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUG
char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}
int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}
const int N=1000010;
int n,m,q;
namespace seg
{
ll s[10*N];
int sz[10*N];
int lc[10*N],rc[10*N];
int cnt;
#define mid ((L+R)>>1)
void mt(int p)
{
s[p]=s[lc[p]]+s[rc[p]];
sz[p]=sz[lc[p]]+sz[rc[p]];
}
int insert(int p,int x,int v,int L,int R)
{
if(!p)
p=++cnt;
if(L==R)
{
s[p]+=x*v;
sz[p]+=v;
return p;
}
if(x<=mid)
lc[p]=insert(lc[p],x,v,L,mid);
if(x>mid)
rc[p]=insert(rc[p],x,v,mid+1,R);
mt(p);
return p;
}
int merge(int p1,int p2,int L,int R)
{
if(!p1||!p2)
return p1+p2;
if(L==R)
{
s[p1]+=s[p2];
sz[p1]+=sz[p2];
return p1;
}
lc[p1]=merge(lc[p1],lc[p2],L,mid);
rc[p1]=merge(rc[p1],rc[p2],mid+1,R);
mt(p1);
return p1;
}
ll query(int p,int k,int L,int R)
{
if(k>=sz[p])
return s[p];
if(L==R)
return (ll)k*L;
ll res=query(rc[p],k,mid+1,R);
if(k>sz[rc[p]])
res+=query(lc[p],k-sz[rc[p]],L,mid);
return res;
}
}
struct edge
{
int x,y,t;
};
edge b[N];
vector<pii> g2[N];
int t;
namespace solve
{
int f[N],r[N];
int st_r[5*N],st_x[5*N];
int tot,now;
int find(int x)
{
return f[x]==x?x:find(f[x]);
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
if(r[x]>r[y])
swap(x,y);
tot++;
st_r[tot]=r[y];
st_x[tot]=x;
f[x]=y;
if(r[x]==r[y])
r[y]++;
}
void pop()
{
r[f[st_x[tot]]]=st_r[tot];
f[st_x[tot]]=st_x[tot];
tot--;
}
vector<int> g[N];
int dfn[N],low[N],_ti;
int vis[N],st[N],top;
int c[N],ti;
edge b1[N],b2[N];
int d[N];
int cnt;
void dfs(int x)
{
vis[x]=1;
st[++top]=x;
dfn[x]=low[x]=++_ti;
for(auto v:g[x])
if(vis[v]!=2)
{
if(!vis[v])
dfs(v);
low[x]=min(low[x],low[v]);
}
if(low[x]>=dfn[x])
{
int v;
do
{
v=st[top--];
vis[v]=2;
if(v!=x)
merge(v,x);
}
while(v!=x);
}
}
void gao(int tl,int tr,int l,int r)
{
if(l>r)
return;
int tmid=(tl+tr)>>1;
int now=tot;
ti++;
int cnt=0;
for(int i=l;i<=r;i++)
{
if(b[i].t<=tmid)
{
int x=find(b[i].x);
int y=find(b[i].y);
if(c[x]!=ti)
{
d[++cnt]=x;
vis[x]=0;
c[x]=ti;
g[x].clear();
}
if(c[y]!=ti)
{
d[++cnt]=y;
vis[y]=0;
c[y]=ti;
g[y].clear();
}
g[x].push_back(y);
}
}
top=0;
_ti=0;
for(int i=1;i<=cnt;i++)
if(!vis[d[i]])
dfs(d[i]);
int t1=0,t2=0;
for(int i=l;i<=r;i++)
{
int flag=0;
if(b[i].t<=tmid)
{
int x=b[i].x;
int y=b[i].y;
if(find(x)==find(y))
flag=1;
}
if(flag)
b1[++t1]=b[i];
else
b2[++t2]=b[i];
}
if(tl==tr)
{
for(int i=1;i<=t1;i++)
g2[tl].push_back(pii(b1[i].x,b1[i].y));
while(tot>now)
pop();
}
else
{
for(int i=1;i<=t1;i++)
b[l+i-1]=b1[i];
for(int i=1;i<=t2;i++)
b[l+t1+i-1]=b2[i];
gao(tmid+1,tr,l+t1,r);
while(tot>now)
pop();
gao(tl,tmid,l,l+t1-1);
}
}
void solve()
{
for(int i=1;i<=n;i++)
{
f[i]=i;
r[i]=1;
}
gao(0,q,1,t);
}
}
map<int,int> g[N];
int rt[N];
int f[N];
int a[N];
int op[N],qx[N],qy[N];
ll ans[N];
const int _=1e9;
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
{
rt[x]=seg::merge(rt[x],rt[y],1,_);
f[y]=x;
}
}
int main()
{
open("f");
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
// scanf("%d",&a[i]);
a[i]=rd();
int x,y;
for(int i=1;i<=m;i++)
{
// scanf("%d%d",&x,&y);
x=rd();
y=rd();
g[x][y]=1;
}
for(int i=q;i>=1;i--)
{
// scanf("%d%d%d",&op[i],&x,&y);
op[i]=rd();
x=rd();
y=rd();
if(op[i]==1)
{
qx[i]=x;
qy[i]=y;
g[x].erase(y);
t++;
b[t].t=i;
b[t].x=x;
b[t].y=y;
}
else if(op[i]==2)
{
qx[i]=x;
qy[i]=-y;
a[x]+=y;
}
else
{
qx[i]=x;
qy[i]=y;
}
}
for(int i=1;i<=n;i++)
for(auto v:g[i])
{
t++;
b[t].t=0;
b[t].x=i;
b[t].y=v.first;
}
solve::solve();
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n;i++)
rt[i]=seg::insert(rt[i],a[i],1,1,_);
for(int i=0;i<=q;i++)
{
for(auto v:g2[i])
merge(v.first,v.second);
if(!i)
continue;
x=qx[i];
y=qy[i];
if(op[i]==2)
{
int z=find(x);
rt[z]=seg::insert(rt[z],a[x],-1,1,_);
a[x]+=y;
rt[z]=seg::insert(rt[z],a[x],1,1,_);
}
else
{
x=find(x);
ans[i]=seg::query(rt[x],y,1,_);
}
}
for(int i=q;i>=1;i--)
if(op[i]==3)
printf("%lld\n",ans[i]);
return 0;
}