SDOI2019世界地图 最小生成树

发表于 更新于 分类于 阅读次数：

[SDOI2019]世界地图 只需要把前缀后缀的MST合并。考虑加入边的过程，只会删掉原来的环上的边。也就是说明只需要维护一些环即可。进一步的，可以把环上的链缩起来。 想法很简单，之后代码就不会写了。。网上冲浪后学习到了实现技巧： 直接暴力Kruskal合并两棵树。之后只需要在新树上缩掉一些边即可。 进行两次DFS：设置叶子节点为初始可用节点。随便选一个叶子开始DFS1。 在DFS1过程中，一个点子树中叶子的数量。如果超过两个叶子，说明这个点在叶子的环上，打标记。 在DFS2过程中，把两个端点都有标记的点加入新树中。用一个变量维护删掉的边的和并累计入答案。 注意到DFS过程是从一个叶子开始的，可以分析出，DFS不需要考虑父亲的情况。这样就简单的实现出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
// 调试懒得删了
#include <bits/stdc++.h>

using std::cerr;
using std::endl;

const int N = 105, M = 10005;

unsigned int SA, SB, SC;
int n, m, q, lim, ri[M][N], dn[M][N];

inline int get_weight() {
  SA ^= SA << 16;
  SA ^= SA >> 5;
  SA ^= SA << 1;
  unsigned int t = SA;
  SA = SB;
  SB = SC;
  SC ^= t ^ SA;
  return SC % lim + 1;
}

struct Edge {
  int x, y; long long w;
  inline friend bool operator<(const Edge &a, const Edge &b) {
    return a.w < b.w;
  }
};

struct MST {
  int id;
  long long sum;
  std::vector<Edge> E;

  MST() { id = sum = 0; }
  MST(int v[]) {
    id = n, E.resize(n - 1), sum = 0;
    for (int i = 1; i < n; ++i)
      E[i - 1] = { i, i + 1, v[i] };
  }

  inline long long calc() {
    long long ret = sum;
    for (auto e : E)
      ret += e.w;
    return ret;
  }
} pre[M], suf[M];

int fa[M];

int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

struct Graph {
  int to, nxt, w;
} G[M * 2];
int head[M], etot;

inline void addedge(int x, int y, int w) {
  G[++etot] = { y, head[x], w }, head[x] = etot;
}

inline void addedge(const Edge &e) {
  addedge(e.x, e.y, e.w);
  addedge(e.y, e.x, e.w);
}

std::vector<Edge> E;
int id;

int tag[M];
long long sum;

// mark all vertexs on line
// O(n)
int dfs1(int x, int fa) {
  // std::cout << x << std::endl;
  int son = 0;
  for (int i = head[x]; i; i = G[i].nxt) {
    int y = G[i].to;
    if (y != fa)
      son += !!dfs1(y, x);
  }
  if (son >= 2)
    tag[x] = 1;
  // std::cout << x << " " << son + tag[x] << std::endl;
  // std::cout << x << " " << tag[x] << std::endl;
  return son + tag[x];
}

void dfs2(int x, int fa, int ver, int val) {
  if (tag[x]) {
    if (ver)
      E.push_back({ tag[x], ver, val });
    ver = tag[x];
    sum -= val;
    val = 0;
  }
  for (int i = head[x]; i; i = G[i].nxt) {
    int y = G[i].to;
    if (y != fa) {
      dfs2(y, x, ver, std::max(val, G[i].w));
    }
  }
}

inline MST merge(const MST &a, const MST &b, int v[]) {
  id = a.id + b.id;
  E.clear();
  for (auto e : a.E)
    E.push_back(e);
  for (auto e : b.E)
    E.push_back({ e.x + a.id, e.y + a.id, e.w });
  for (int i = 1; i <= n; ++i)
    E.push_back({ a.id - n + i, a.id + i, v[i] });
  std::sort(E.begin(), E.end());

  for (int i = 1; i <= id; ++i) {
    fa[i] = i;
    head[i] = 0;
    if (i <= n  i >= id - n + 1)
      tag[i] = 1;
    else
      tag[i] = 0;
  }


  etot = 0;
  sum = 0;
  for (auto e : E) {
    int x = find(e.x), y = find(e.y);
    if (x != y) {
      addedge(e);
      fa[x] = y;
      sum += e.w;
      // std::cout << e.x << " " << e.y << std::endl;
    }
  }

  E.clear();
  dfs1(1, 0);

  /*
  for (int i = 1; i <= id; ++i)
    cerr << tag[i] << " ";
  cerr << endl;
  */

  int num = 0;
  for (int i = 1; i <= id; ++i)
    if (tag[i]) tag[i] = ++num;

  // cerr << num << endl;

  dfs2(1, 0, 0, 0);

  MST ret; ret.sum = a.sum + b.sum;
  ret.sum += sum;
  ret.E = E, ret.id = num;
  return ret;

  /*
  E.clear();
  for (int i = 1; i <= etot; i += 2)
    E.push_back({ G[i].to, G[i + 1].to, G[i].w });
  MST ret; ret.sum = 0;
  ret.E = E, ret.id = id;
  return ret;
  */
}

int main() {
  freopen("data", "r", stdin);
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cin >> n >> m >> SA >> SB >> SC >> lim;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      ri[j][i] = get_weight();
  for (int i = 1; i < n; ++i)
    for (int j = 1; j <= m; ++j)
      dn[j][i] = get_weight();

  pre[1] = MST(dn[1]);
  suf[m] = MST(dn[m]);

  for (int i = 2; i < m; ++i) {
    pre[i] = merge(pre[i - 1], MST(dn[i]), ri[i - 1]);
    /*
    if (i == 3)
      exit(0);
    */
  }
  for (int i = m - 1; i > 1; --i)
    suf[i] = merge(MST(dn[i]), suf[i + 1], ri[i]);


  std::cin >> q;
  while (q--) {
    int l, r; std::cin >> l >> r;
    long long ans = 0;
    if (l == 1 && r == m)
      ans = 0;
    else if (l == 1)
      ans = suf[r + 1].calc();
    else if (r == m)
      ans = pre[l - 1].calc();
    else
      ans = merge(suf[r + 1], pre[l - 1], ri[m]).calc();
    std::cout << ans << '\n';
  }
  return 0;
}