只有洛谷的毒瘤才会在毒瘤月赛里出毒瘤题......
题意：三个操作，删边，改变点权，求点x所在强连通分量内前k大点权之和。
解：*毒瘤数据结构乱堆......
整体二分套(tarjan+并查集) + 线段树合并。
首先可以变成加边。
然后就是神奇操作让人难以置信......
对于每条边，我们有个时刻t使得它的两端点在同一scc内。那么如何求出这个t呢？
整体二分!...这又是怎么想到的啊......
对于一个时刻mid，我们把小于它的边提取出来缩点，如果有的边两端点在一个scc，那么它的t就不大于mid。否则大于mid。
为了保证整体二分的复杂度，我们每次操作tarjan的图不能太大。具体来说，把之前做过的区间的scc用并查集缩起来。
对于每条边，提取两端点所在scc的代表元为关键点，构出虚图(?????)，然后tarjan。
之后递归左边，之后并查集缩点，之后递归右边。
所有t求出之后，再倒着跑一遍询问，按照时刻把边的两端点在并查集中合并(表示成为一个scc)，并对权值线段树进行合并。
查询就是所在scc的权值线段树的前k大之和，这个好办。
注意爆int。我写了300行7k......
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <map> typedef long long LL;
const int N = , M = , V = ; struct Edge {
int nex, v;
}edge[M]; int tp; struct Node {
int t, x, y, id;
}node[M], t1[M], t2[M]; struct Ask {
int f, x, y;
LL ans;
}ask[M]; std::vector<Node> v[M];
std::stack<int> S;
std::map<int, int> mp[N];
int e[N], fr[N], stk[N], top, dfn[N], low[N], use[N], X[N + M], xx, rt[N], sum[V], ls[V], rs[V], val[N];
int Time, scc_cnt, num, n, m, q, tot;
LL Val[V]; inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} namespace ufs {
int fa[N];
int find(int x) {
if(fa[x] == x) {
return x;
}
return fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
fa[find(x)] = find(y);
return;
}
inline void clear() {
for(int i = ; i <= n; i++) {
fa[i] = i;
}
return;
}
} void tarjan(int x) {
low[x] = dfn[x] = ++num;
S.push(x);
//printf("tarjan %d \n", x);
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!dfn[y]) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
}
else if(!fr[y]) { // find
low[x] = std::min(low[x], dfn[y]);
}
}
if(low[x] == dfn[x]) {
//printf("getscc \n");
++scc_cnt;
int y;
do {
y = S.top();
//printf("%d ", y);
S.pop();
fr[y] = scc_cnt;
//ufs::merge(x, y);
} while(y != x);
//puts("");
}
return;
} inline void TAR() {
scc_cnt = num = ;
for(int i = ; i <= top; i++) {
if(!dfn[stk[i]]) {
tarjan(stk[i]);
}
}
return;
} inline void link(int x, int y) {
x = ufs::find(x); y = ufs::find(y);
if(use[x] != Time) {
use[x] = Time;
dfn[x] = fr[x] = e[x] = ;
stk[++top] = x;
}
if(use[y] != Time) {
use[y] = Time;
dfn[y] = fr[y] = e[y] = ;
stk[++top] = y;
}
add(x, y); // self-circle is OK
return;
} inline void solve(int L, int R, int l, int r) {
if(R < L) {
return;
}
//printf("solve %d %d %d %d \n", L, R, l, r);
if(l == r) {
for(int i = L; i <= R; i++) {
v[r].push_back(node[i]);
}
return;
}
int mid = (l + r) >> ;
++Time; top = tp = ;
for(int i = L; i <= R; i++) {
if(node[i].t <= mid) {
link(node[i].x, node[i].y);
}
}
//int ufs_t = ufs::top;
TAR();
int top1 = , top2 = ;
for(int i = L; i <= R; i++) {
int x = ufs::find(node[i].x), y = ufs::find(node[i].y);
if(node[i].t <= mid && fr[x] == fr[y]) {
t1[++top1] = node[i];
}
else {
t2[++top2] = node[i];
}
}
memcpy(node + L, t1 + , top1 * sizeof(Node));
memcpy(node + L + top1, t2 + , top2 * sizeof(Node));
solve(L, L + top1 - , l, mid);
for(int i = L; i < L + top1; i++) {
int x = ufs::find(node[i].x);
int y = ufs::find(node[i].y);
ufs::merge(x, y);
}
solve(L + top1, R, mid + , r);
return;
} int merge(int x, int y) {
if(!x || !y || x == y) {
return x | y;
}
int o = ++tot;
sum[o] = sum[x] + sum[y];
Val[o] = Val[x] + Val[y];
ls[o] = merge(ls[x], ls[y]);
rs[o] = merge(rs[x], rs[y]);
return o;
} void add(int p, int v, int l, int r, int &o) {
//printf("add : %d %d %d %d \n", p, v, l, r);
if(!o) {
o = ++tot;
}
if(l == r) {
sum[o] += v;
Val[o] += v * X[r];
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
add(p, v, l, mid, ls[o]);
}
else {
add(p, v, mid + , r, rs[o]);
}
sum[o] = sum[ls[o]] + sum[rs[o]];
Val[o] = Val[ls[o]] + Val[rs[o]];
return;
} LL query(int k, int l, int r, int o) {
//printf("query %d [%d %d] \n", k, l, r);
if(!o) {
return ;
}
if(l == r) {
return 1ll * std::min(k, sum[o]) * X[r];
}
int mid = (l + r) >> ;
if(sum[rs[o]] >= k) {
return query(k, mid + , r, rs[o]);
}
else {
return Val[rs[o]] + query(k - sum[rs[o]], l, mid, ls[o]);
}
} int main() { scanf("%d%d%d", &n, &m, &q);
ufs::clear();
for(int i = ; i <= n; i++) {
scanf("%d", &val[i]);
X[++xx] = val[i];
}
for(int i = ; i <= m; i++) {
scanf("%d%d", &node[i].x, &node[i].y);
mp[node[i].x][node[i].y] = i;
node[i].id = i;
}
for(int i = ; i <= q; i++) {
scanf("%d%d%d", &ask[i].f, &ask[i].x, &ask[i].y);
if(ask[i].f == ) {
ask[i].y += val[ask[i].x];
X[++xx] = ask[i].y;
std::swap(val[ask[i].x], ask[i].y);
}
}
std::sort(X + , X + xx + );
xx = std::unique(X + , X + xx + ) - X - ;
for(int i = ; i <= n; i++) {
val[i] = std::lower_bound(X + , X + xx + , val[i]) - X;
}
for(int i = ; i <= q; i++) {
if(ask[i].f == ) {
ask[i].y = std::lower_bound(X + , X + xx + , ask[i].y) - X;
}
}
std::reverse(ask + , ask + q + );
for(int i = ; i <= q; i++) {
if(ask[i].f == ) {
int t = mp[ask[i].x][ask[i].y];
node[t].t = i;
}
} solve(, m, , q + );
//printf("--------------------------------\n");
ufs::clear();
for(int i = ; i <= n; i++) {
add(val[i], , , xx, rt[i]);
}
for(int i = ; i <= q; i++) {
//printf("i = %d \n", i);
for(int j = ; j < v[i].size(); j++) {
//printf(" > edge = %d %d \n", v[i][j].x, v[i][j].y);
int x = ufs::find(v[i][j].x), y = ufs::find(v[i][j].y);
ufs::merge(x, y);
int t = ufs::find(x);
rt[t] = merge(rt[x], rt[y]);
//printf("%d = merge %d %d \n", t, x, y);
}
if(ask[i].f == ) {
int t = ufs::find(ask[i].x);
ask[i].ans = query(ask[i].y, , xx, rt[t]);
}
else if(ask[i].f == ) {
int t = ufs::find(ask[i].x);
//printf("change %d : %d -> %d \n", ask[i].x, X[val[ask[i].x]], X[ask[i].y]);
add(val[ask[i].x], -, , xx, rt[t]);
add(ask[i].y, , , xx, rt[t]);
val[ask[i].x] = ask[i].y;
}
}
for(int i = q; i >= ; i--) {
if(ask[i].f == ) {
printf("%lld\n", ask[i].ans);
}
}
return ;
}
AC代码
对拍真是个好东西。