无A
题目大意： 规定每一位采用的进制。求十进制数在该进制下的表示。
难度： ~900
按照题意，模拟进位的过程即可。（注意要求输出前导零）
Code:
void solve() {string s; cin >> n >> m;cin >> s >> m;for (int i = n - 1; i >= 0; i--) {int cur = s[i] - '0';ans[i] = m % cur;m /= cur;}for (int i = 0; i < n; i++) {cout << ans[i];}
}
B
题目大意： 构造含 \(1\) 至 \(n\) 各两次的排列，以最小化 \(\sum_{i=1}^{n}(n-i)\left|d_i+i-n\right|\) 的值，其中 \(d_i\) 是排列中两个 \(i\) 之间的距离。
难度： 1900
显然 \(i=n\) 放的位置不改变答案。因此考虑最后放。
考虑构造 \(d_i=n-i\) \((1\leq i \leq n-1)\) 的方案，\(n\) 为奇数和偶数时，分别如下（以 \(n=5,6\) 为例）。
将奇数偶数聚在一起放置，最后空出的位置放 \(n\) 。这样可保证目标式的值为 \(0\) ，达到最小。
Code
void solve() {n = read();for (int i = 1; i < n; i += 2) {a[(i + 1) / 2] = i;a[(i + 1) / 2 + n - i] = i;}for (int i = 2; i < n; i += 2) {a[2 * n + 1 - i / 2] = i;a[2 * n + 1 - i / 2 - n + i] = i;}for (int i = 1; i <= 2 * n; i++) {if (!a[i]) a[i] = n;}FOR(i, 1, 2 * n) cout << a[i] << " ";
}
D
题目大意： 给定一棵有向树型图，此外每个节点有一个指回根节点的边。要求维护两种操作：修改边权以及查询两点之间的最短路径。
难度： 2100
为了方便叙述，下面设树的根节点是 \(r\) ，询问中起点是 \(u\) ，终点是 \(v\) ，修改中的终点是 \(x\) .
此外，将节点 \(i\) 与根节点的距离记为 \(sum_i\) .
观察后不难发现，最短路径有两种情形。
一、\(v\) 在 \(u\) 的子树内。那么无论选择何时返回 \(r\) 再前往 \(v\) ，路径都包含从 \(u\) 到 \(v\) 的简单路径。所以这种情形下答案就是简单路径的长度，也就是 \(sum_v-sum_u\) .
二、\(v\) 不在 \(u\) 的子树内。那么路径一定如下构成：\(u\rightarrow t \rightarrow r \rightarrow v\) ，其中的 \(t\) 是 \(u\) 子树中的节点。
\[\begin{align*}
w_{u\rightarrow v}&=w_{u\rightarrow t} + w_{t\rightarrow r}+w_{r\rightarrow v}\\
&=sum_t - sum_u+w_{t\rightarrow r}+sum_v
\end{align*}
\]
由于询问中 \(u\) 和 \(v\) 确定，我们只需维护每一个节点的 \(sum_t + w_{t\rightarrow r}\) 值，然后在 \(u\) 的子树中找出最小值即可。
修改操作同样有两种情形。
一、修改的是树边。那么 \(x\) 的子树内所有节点对应的 \(sum\) 值会改变相同的值。结合查询的要求，这似乎可以用线段树维护，但同子树内的节点编号不一定连续，难以维护。为了解决这个问题，我们将节点按照其 \(dfs\) 序重新编号，这样就可以保证同子树内节点的编号是一个连续的区间，从而可以用线段树的区间修改来维护。
二、修改的不是树边。只需对 \(sum_t+v_{t\rightarrow r}\) 做单点修改即可。
总的来说，我们根据 \(dfs\) 序重排后建立两棵线段树。第一棵维护 \(sum\) 值，支持区间修改和单点查询；第二棵维护 $sum_i + w_{i\rightarrow r} $ 值，支持区间修改和区间最值查询。在修改和查询时根据上文所说执行对应操作即可。
赛时思路完全正确，也完成了代码。但调试能力太差，未能场切。
Code:
#include <bits/stdc++.h>
using namespace std;#define int long long
#define FOR(i,j,k) for (int i = j; i <= k; i++)const int N = 4e5 + 10;
const int INF = 1e16;int T;int n, m, k, q;int a[N], b[N];vector<pair<int, int> > e[N << 2];inline int read() {char ch = getchar(); int x = 0, f = 1;while ((ch > '9' || ch < '0') && ch != '-') ch = getchar();if (ch == '-') { ch = getchar(); f = - 1; }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}struct sgt {#define mid (l + r) / 2struct Info {int val, len, mn, tag;} info[N << 2];int a[N];void pushup(int p) {info[p].val = info[p << 1].val + info[p << 1 | 1].val;info[p].len = info[p << 1].len + info[p << 1 | 1].len;info[p].mn = min(info[p << 1].mn, info[p << 1 | 1].mn);}void pushdown(int p, int l, int r) {if (info[p].tag) {info[p << 1].tag += info[p].tag;info[p << 1 | 1].tag += info[p].tag;info[p << 1].mn += info[p].tag;info[p << 1 | 1].mn += info[p].tag;info[p << 1].val += info[p].tag * (mid - l + 1);info[p << 1 | 1].val += info[p].tag * (r - mid);info[p].tag = 0;}}void build(int p, int l, int r) {if (l == r) {info[p].val = a[l];info[p].len = 1;info[p].mn = a[l];info[p].tag = 0;return;}build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);pushup(p);}void pmodify(int p, int l, int r, int x, int v) {if (l == r && l == x) {info[p].val = v;info[p].mn = v;return;}pushdown(p, l, r);if (x <= mid) pmodify(p << 1, l, mid, x, v);else pmodify(p << 1 | 1, mid + 1, r, x, v);pushup(p);}void rmodify(int p, int l, int r, int L, int R, int v) {if (L <= l && r <= R) {info[p].val += (r - l + 1) * v;info[p].tag += v;info[p].mn += v;return;}if (R < l || L > r) return;pushdown(p, l, r);rmodify(p << 1, l, mid, L, R, v);rmodify(p << 1 | 1, mid + 1, r, L, R, v);pushup(p);}int query(int p, int l, int r, int L, int R) {if (L <= l && r <= R) return info[p].val;if (R < l || L > r) return 0;pushdown(p, l, r);int res = 0;res += query(p << 1, l, mid, L, R);res += query(p << 1 | 1, mid + 1, r, L, R);pushup(p);return res;}int querymin(int p, int l, int r, int L, int R) {if (L <= l && r <= R) return info[p].mn;if (R < l || L > r) return INF;pushdown(p, l, r);int res = 0;res = querymin(p << 1, l, mid, L, R);res = min(res, querymin(p << 1 | 1, mid + 1, r, L, R));pushup(p);return res;}
} t, tt;int nowmax = 0;
int idx[N], nd[N], rg[N][2], dep[N], f[N][30];vector<int> sum;void dfs1(int fa, int u) {dep[u] = dep[fa] + 1;nowmax++;idx[u] = nowmax;nd[nowmax] = u;rg[idx[u]][0] = nowmax;for (auto v : e[u]) {if (v.first == fa) continue;dfs1(u, v.first);}rg[idx[u]][1] = nowmax;
}void dfs2(int fa, int u) {for (auto v : e[u]) {if (v.first == fa) continue;sum[idx[v.first]] = sum[idx[u]] + v.second;dfs2(u, v.first);}
}int lca(int u, int v) {if (dep[u] < dep[v]) swap(u, v);for (int i = 20; i >= 0; i--)if ((dep[u] - (1 << i)) >= dep[v])u = f[u][i];if (u == v) return u;for (int i = 20; i >= 0; i--) {if (f[u][i] == f[v][i]) continue;u = f[u][i]; v = f[v][i];}return f[u][0];
}void dfs3(int u, int fa) {f[u][0] = fa;for (int i = 1; (1 << i) <= dep[u]; i++) f[u][i] = f[f[u][i - 1]][i - 1];for (auto v : e[u]) {if (v.first == fa) continue;dfs3(v.first, u);}
}int rec[N][5];void solve() {n = read(); q = read();FOR(i, 1, n) b[i] = INF;FOR(i, 1, n - 1) {rec[i][1] = read();rec[i][2] = read();rec[i][3] = read();e[rec[i][1]].push_back(make_pair(rec[i][2], rec[i][3]));}FOR(i, n, 2 * n - 2) {rec[i][1] = read();rec[i][2] = read();rec[i][3] = read();b[rec[i][1]] = rec[i][3];}sum.resize(n + 1);dfs1(0, 1);dfs2(0, 1);dfs3(1, 0);FOR(i, 1, n) t.a[i] = sum[i];t.build(1, 1, n);FOR(i, 1, n) tt.a[i] = b[nd[i]] + sum[i];tt.build(1, 1, n);while (q--) {int op = read();int u = read(), v = read();if (op == 1) {if (u >= n) {int tsum = t.query(1, 1, n, idx[rec[u][1]], idx[rec[u][1]]);tt.pmodify(1, 1, n, idx[rec[u][1]], v + tsum);b[rec[u][1]] = v;rec[u][3] = v;} else {int root = idx[rec[u][2]];t.rmodify(1, 1, n, rg[root][0], rg[root][1], v - rec[u][3]);tt.rmodify(1, 1, n, rg[root][0], rg[root][1], v - rec[u][3]);rec[u][3] = v;}} else {if (lca(u, v) == u) {int s1 = t.query(1, 1, n, idx[u], idx[u]);int s2 = t.query(1, 1, n, idx[v], idx[v]);cout << s2 - s1 << '\n';} else {int ans = t.query(1, 1, n, idx[v], idx[v]);int ans2 = tt.querymin(1, 1, n, rg[idx[u]][0], rg[idx[u]][1]);int ans3 = t.query(1, 1, n, idx[u], idx[u]);cout << ans + ans2 - ans3 << '\n';}}}
}signed main() {solve();return 0;
}