本文共 6690 字，大约阅读时间需要 22 分钟。
只有洛谷的毒瘤才会在毒瘤月赛里出毒瘤题......
题意：三个操作，删边，改变点权，求点x所在强连通分量内前k大点权之和。
解：狗屎毒瘤数据结构乱堆......
整体二分套(tarjan+并查集) + 线段树合并。
首先可以变成加边。
然后就是神奇操作让人难以置信......
对于每条边，我们有个时刻t使得它的两端点在同一scc内。那么如何求出这个t呢？
整体二分!...这又是怎么想到的啊......
对于一个时刻mid，我们把小于它的边提取出来缩点，如果有的边两端点在一个scc，那么它的t就不大于mid。否则大于mid。
为了保证整体二分的复杂度，我们每次操作tarjan的图不能太大。具体来说，把之前做过的区间的scc用并查集缩起来。
对于每条边，提取两端点所在scc的代表元为关键点，构出虚图(?????)，然后tarjan。
之后递归左边，之后并查集缩点，之后递归右边。
所有t求出之后，再倒着跑一遍询问，按照时刻把边的两端点在并查集中合并(表示成为一个scc)，并对权值线段树进行合并。
查询就是所在scc的权值线段树的前k大之和，这个好办。
注意爆int。我写了300行7k......
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 8 typedef long long LL; 9 const int N = 100010, M = 400010, V = 40000010; 10 11 struct Edge { 12 int nex, v; 13 }edge[M]; int tp; 14 15 struct Node { 16 int t, x, y, id; 17 }node[M], t1[M], t2[M]; 18 19 struct Ask { 20 int f, x, y; 21 LL ans; 22 }ask[M]; 23 24 std::vector v[M]; 25 std::stack S; 26 std::map mp[N]; 27 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]; 28 int Time, scc_cnt, num, n, m, q, tot; 29 LL Val[V]; 30 31 inline void add(int x, int y) { 32 tp++; 33 edge[tp].v = y; 34 edge[tp].nex = e[x]; 35 e[x] = tp; 36 return; 37 } 38 39 namespace ufs { 40 int fa[N]; 41 int find(int x) { 42 if(fa[x] == x) { 43 return x; 44 } 45 return fa[x] = find(fa[x]); 46 } 47 inline void merge(int x, int y) { 48 fa[find(x)] = find(y); 49 return; 50 } 51 inline void clear() { 52 for(int i = 1; i <= n; i++) { 53 fa[i] = i; 54 } 55 return; 56 } 57 } 58 59 void tarjan(int x) { 60 low[x] = dfn[x] = ++num; 61 S.push(x); 62 //printf("tarjan %d \n", x); 63 for(int i = e[x]; i; i = edge[i].nex) { 64 int y = edge[i].v; 65 if(!dfn[y]) { 66 tarjan(y); 67 low[x] = std::min(low[x], low[y]); 68 } 69 else if(!fr[y]) { // find 70 low[x] = std::min(low[x], dfn[y]); 71 } 72 } 73 if(low[x] == dfn[x]) { 74 //printf("getscc \n"); 75 ++scc_cnt; 76 int y; 77 do { 78 y = S.top(); 79 //printf("%d ", y); 80 S.pop(); 81 fr[y] = scc_cnt; 82 //ufs::merge(x, y); 83 } while(y != x); 84 //puts(""); 85 } 86 return; 87 } 88 89 inline void TAR() { 90 scc_cnt = num = 0; 91 for(int i = 1; i <= top; i++) { 92 if(!dfn[stk[i]]) { 93 tarjan(stk[i]); 94 } 95 } 96 return; 97 } 98 99 inline void link(int x, int y) {100 x = ufs::find(x); y = ufs::find(y);101 if(use[x] != Time) {102 use[x] = Time;103 dfn[x] = fr[x] = e[x] = 0;104 stk[++top] = x;105 }106 if(use[y] != Time) {107 use[y] = Time;108 dfn[y] = fr[y] = e[y] = 0;109 stk[++top] = y;110 }111 add(x, y); // self-circle is OK112 return;113 }114 115 inline void solve(int L, int R, int l, int r) {116 if(R < L) {117 return;118 }119 //printf("solve %d %d %d %d \n", L, R, l, r);120 if(l == r) {121 for(int i = L; i <= R; i++) {122 v[r].push_back(node[i]);123 }124 return;125 }126 int mid = (l + r) >> 1;127 ++Time; top = tp = 0;128 for(int i = L; i <= R; i++) {129 if(node[i].t <= mid) {130 link(node[i].x, node[i].y);131 }132 }133 //int ufs_t = ufs::top;134 TAR();135 int top1 = 0, top2 = 0;136 for(int i = L; i <= R; i++) {137 int x = ufs::find(node[i].x), y = ufs::find(node[i].y);138 if(node[i].t <= mid && fr[x] == fr[y]) {139 t1[++top1] = node[i];140 }141 else {142 t2[++top2] = node[i];143 }144 }145 memcpy(node + L, t1 + 1, top1 * sizeof(Node));146 memcpy(node + L + top1, t2 + 1, top2 * sizeof(Node));147 solve(L, L + top1 - 1, l, mid);148 for(int i = L; i < L + top1; i++) {149 int x = ufs::find(node[i].x);150 int y = ufs::find(node[i].y);151 ufs::merge(x, y);152 }153 solve(L + top1, R, mid + 1, r);154 return;155 }156 157 int merge(int x, int y) {158 if(!x || !y || x == y) {159 return x | y;160 }161 int o = ++tot;162 sum[o] = sum[x] + sum[y];163 Val[o] = Val[x] + Val[y];164 ls[o] = merge(ls[x], ls[y]);165 rs[o] = merge(rs[x], rs[y]);166 return o;167 }168 169 void add(int p, int v, int l, int r, int &o) {170 //printf("add : %d %d %d %d \n", p, v, l, r);171 if(!o) {172 o = ++tot;173 }174 if(l == r) {175 sum[o] += v;176 Val[o] += v * X[r];177 return;178 }179 int mid = (l + r) >> 1;180 if(p <= mid) {181 add(p, v, l, mid, ls[o]);182 }183 else {184 add(p, v, mid + 1, r, rs[o]);185 }186 sum[o] = sum[ls[o]] + sum[rs[o]];187 Val[o] = Val[ls[o]] + Val[rs[o]];188 return;189 }190 191 LL query(int k, int l, int r, int o) {192 //printf("query %d [%d %d] \n", k, l, r);193 if(!o) {194 return 0;195 }196 if(l == r) {197 return 1ll * std::min(k, sum[o]) * X[r];198 }199 int mid = (l + r) >> 1;200 if(sum[rs[o]] >= k) {201 return query(k, mid + 1, r, rs[o]);202 }203 else {204 return Val[rs[o]] + query(k - sum[rs[o]], l, mid, ls[o]);205 }206 }207 208 int main() {209 210 scanf("%d%d%d", &n, &m, &q);211 ufs::clear();212 for(int i = 1; i <= n; i++) {213 scanf("%d", &val[i]);214 X[++xx] = val[i];215 }216 for(int i = 1; i <= m; i++) {217 scanf("%d%d", &node[i].x, &node[i].y);218 mp[node[i].x][node[i].y] = i;219 node[i].id = i;220 }221 for(int i = 1; i <= q; i++) {222 scanf("%d%d%d", &ask[i].f, &ask[i].x, &ask[i].y);223 if(ask[i].f == 2) {224 ask[i].y += val[ask[i].x];225 X[++xx] = ask[i].y;226 std::swap(val[ask[i].x], ask[i].y);227 }228 }229 std::sort(X + 1, X + xx + 1);230 xx = std::unique(X + 1, X + xx + 1) - X - 1;231 for(int i = 1; i <= n; i++) {232 val[i] = std::lower_bound(X + 1, X + xx + 1, val[i]) - X;233 }234 for(int i = 1; i <= q; i++) {235 if(ask[i].f == 2) {236 ask[i].y = std::lower_bound(X + 1, X + xx + 1, ask[i].y) - X;237 }238 }239 std::reverse(ask + 1, ask + q + 1);240 for(int i = 1; i <= q; i++) {241 if(ask[i].f == 1) {242 int t = mp[ask[i].x][ask[i].y];243 node[t].t = i;244 }245 }246 247 solve(1, m, 1, q + 1);248 //printf("--------------------------------\n");249 ufs::clear();250 for(int i = 1; i <= n; i++) {251 add(val[i], 1, 1, xx, rt[i]);252 }253 for(int i = 1; i <= q; i++) {254 //printf("i = %d \n", i);255 for(int j = 0; j < v[i].size(); j++) {256 //printf(" > edge = %d %d \n", v[i][j].x, v[i][j].y);257 int x = ufs::find(v[i][j].x), y = ufs::find(v[i][j].y);258 ufs::merge(x, y);259 int t = ufs::find(x);260 rt[t] = merge(rt[x], rt[y]);261 //printf("%d = merge %d %d \n", t, x, y);262 }263 if(ask[i].f == 3) {264 int t = ufs::find(ask[i].x);265 ask[i].ans = query(ask[i].y, 1, xx, rt[t]);266 }267 else if(ask[i].f == 2) {268 int t = ufs::find(ask[i].x);269 //printf("change %d : %d -> %d \n", ask[i].x, X[val[ask[i].x]], X[ask[i].y]);270 add(val[ask[i].x], -1, 1, xx, rt[t]);271 add(ask[i].y, 1, 1, xx, rt[t]);272 val[ask[i].x] = ask[i].y;273 }274 }275 for(int i = q; i >= 1; i--) {276 if(ask[i].f == 3) {277 printf("%lld\n", ask[i].ans);278 }279 }280 return 0;281 }
对拍真是个好东西。
转载于:https://www.cnblogs.com/huyufeifei/p/10403339.html
