2024 信友队 noip 冲刺 10.8

T1

给定 $n$ 个数 { a n } \{a_n\} {an​}，值域在 $[1,m]$ 中，求一个字典序最小的子序列满足是一个 $1\sim m$ 的排列。输出子序列。

$m\le n\le 2\times 10^5$。

考虑一个数字能被选择的条件。假设我们已经把 $k$ 个数选进答案子序列中，那么对于没选择的数 $i$，它能被选当且仅当 $[i,n]$ 中有剩下没选的所有数字。我们考虑对于每个 $i$ 求出 $[i,n]$ 中数的种类数 $f(i)$，然后从大到小枚举 $k$，每次找到一个满足 $f(i)=k$ 的 $a_i$ 最小的数作为答案的下一项。显然 $f(i)$ 从后往前单调不降，那么我们可以求出最靠右的 $f(i)=k$ 的 $i$，那么此时答案项就可以从 $i$ 之前的数中选。

我们用一个线段树维护 $f(i)$，找 $f(i)=k$ 的过程就相当于在线段树上二分，二分时维护区间最大值，每次若有条件那么尽可能往右走，这样就算出了最右边的 $i$。考虑 $a_i$ 被选的影响，可以发现对于 $a_i$ 最右边出现的位置 $a_{pos}$，影响就是对于 $j\in [1,pos]$，$f(j)\leftarrow f(j)-1$，这么操作显然仍然是单调的。我们再拿一棵线段树维护 $a_i$ 的区间最小值，找到 $i$ 后令 $l$ 为当前能选的区间为 $[l,n]$，那么我们取出 $[l,n]$ 中的最小值作为当前的答案，然后我们遍历 $a_i$ 出现的每个位置将其设为 $\infty$，然后就做完了，时间复杂度 $O(n\log n)$​。

赛时自测发现跑的很慢，疯狂卡常铸就了史山代码，赛后发现信友队数据水且评测机强大。

const int maxn = 2e5 + 5;
int n, m, a[maxn], val[maxn]; bool tab[maxn];
int hg[maxn]; vector<int> p[maxn];
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
namespace SegmentTree {int mx[maxn << 2], col[maxn << 2];inline void update(int rt) {mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);}inline void color(int rt, int k) {mx[rt] += k, col[rt] += k;}inline void pushcol(int rt) {if (col[rt] == 0) return ;color(rt << 1, col[rt]), color(rt << 1 | 1, col[rt]);col[rt] = 0;}int query(int l, int r, int rt, int k, int nowl, int nowr) {if (mx[rt] < k) return -1;if (l == r) return l;int mid = (l + r) >> 1; pushcol(rt);if (nowl > mid) return query(rson, k, mid + 1, nowr);else if (mid >= nowr) return query(lson, k, nowl, mid);else {int Rson = query(rson, k, mid + 1, nowr);if (Rson == -1) return query(lson, k, nowl, mid);else return Rson;}}void modify(int l, int r, int rt, int k, int nowl, int nowr) {if (nowl <= l && r <= nowr) return color(rt, k);int mid = (l + r) >> 1;if (nowl <= mid) modify(lson, k, nowl, nowr);if (mid < nowr) modify(rson, k, nowl, nowr);update(rt);}
} using namespace SegmentTree;
const int inf = 1e6;
namespace SegmentTree2 {struct TreeNode {int mn, pos;TreeNode(int m0 = inf, int p0 = inf) { mn = m0, pos = p0; }inline bool operator<(const TreeNode &oth) const {return mn == oth.mn ? pos < oth.pos : mn < oth.mn;}} T[maxn << 2];void pushup(int rt) { T[rt] = min(T[rt << 1], T[rt << 1 | 1]); }TreeNode ask(int l, int r, int rt, int nowl, int nowr) {if (nowl <= l && r <= nowr) return T[rt];int mid = (l + r) >> 1; TreeNode res;if (nowl <= mid) res = min(res, ask(lson, nowl, nowr));if (mid < nowr) res = min(res, ask(rson, nowl, nowr));return res;}void replace(int l, int r, int rt, int k, int now) {if (l == r) return T[rt].mn = k, void(0);int mid = (l + r) >> 1;if (now <= mid) replace(lson, k, now);else replace(rson, k, now);pushup(rt);}
} using namespace SegmentTree2;
void build(int l, int r, int rt) {if (l == r) return mx[rt] = val[l], T[rt] = TreeNode(a[l], l), void(0);int mid = (l + r) >> 1;build(lson), build(rson), update(rt), pushup(rt);
}
inline int read() {char c = getchar();for (; c < '0' || c > '9'; c = getchar());int s = 0;for (; c >= '0' && c <= '9'; c = getchar())s = (s << 3) + (s << 1) + (c ^ 48);return s;
}
int main() {open(photo); n = read(), m = read();for (int i = 1; i <= n; i ++) a[i] = read(), p[a[i]].push_back(i), hg[a[i]] = i;for (int i = n; i >= 1; i --)val[i] = val[i + 1] + (tab[a[i]] == 0 ? tab[a[i]] = 1 : 0);build(1, n, 1);for (int l = 1; m; m --) {int ps = query(1, n, 1, m, l, n);TreeNode tmp = ask(1, n, 1, l, ps);printf("%d ", tmp.mn);for (int x : p[tmp.mn]) replace(1, n, 1, inf, x);modify(1, n, 1, -1, l, hg[tmp.mn]), l = tmp.pos + 1;} // cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";return 0;
}

T2

给定一棵二叉树，其中叶子节点上有物品 $0/1$ 个，且满足非叶子节点都有左右儿子。每次操作可以调整一个物品的位置（仍在叶子节点上），求最少操作次数使得所有非叶子节点左右子树物品数量相差不超过 $1$​。

叶子节点个数 $\le 3\times 10^5$。

赛时糊了一个 $2^n$ 的暴力，这里记 $n$ 为叶子节点个数。显然根节点子树内物品个数是不能变的，故我们从根节点开始，根据当前分配给这个子树（根节点就分配给它全部物品）的物品数量 $k$，分裂讨论：

• 若 $k$ 是奇数，根据题意，有左子树 $\lfloor k/2\rfloor$ 个和右子树 $\lfloor k/2\rfloor$ 个两种情况，此时我们直接暴力分两种情况，将两个答案取 $\min$。
• 若 $k$ 是偶数，显然只有左右子树各占 $\frac{k}{2}$ 个，直接往下递归就行。

分到叶节点时再计算代价，若发现有一个叶子节点分配了 $2$ 个及以上，那么此时无解，返回无穷大即可。我们发现可以给每个点分配到多少物品做个记忆化，此时就能过了。复杂度看着很假，但是……意会浅推一下可以发现奇数不会出现太多，加上记忆化后就稳过了，复杂度 std 上写的是 $O(n\log n)$，原因是一个数最多被削 $\log$ 次。但是我不加记忆化会 T，也不知道为什么。

namespace STD {const ll inf = 1e9;#define abs(x) (((x) > (0)) ? (x) : (-(x)))map<int, ll> tab[maxn];ll dfs(int u, int tg_val) {if (T[u].siz < tg_val) return inf;if (T[u].son0 == 0) return abs(tg_val - T[u].val);if (tab[u].find(tg_val) != tab[u].end()) return tab[u][tg_val];if (tg_val & 1)return tab[u][tg_val] = min(dfs(T[u].son0, tg_val >> 1) + dfs(T[u].son1, (tg_val >> 1) + (tg_val & 1)), dfs(T[u].son0, (tg_val >> 1) + (tg_val & 1)) + dfs(T[u].son1, tg_val >> 1));else return tab[u][tg_val] = dfs(T[u].son0, tg_val >> 1) + dfs(T[u].son1, tg_val >> 1);}int n, all = 0;int main() {for (int i = 1; i <= n; i ++)tab[i].clear();input(n), all = 0;for (int i = 1; i <= n; i ++) all += T[i].val;ll ans = dfs(1, all); ans >= inf ? puts("impossible") : printf("%lld\n", ans >> 1ll);return 0;}
}

T3

给定一个长为 $n$ 的字符串 $S$ 和 $m$ 段区间，对于第 $i$ 段区间 $[l_i,r_i]$，可以操作零次或若干次使得 $S$ 中 $[l_i,r_i]$ 包含的所有字母变成其后继（即 $\text{a}\to \text{b},\text{c}\to \text{d}$，特别的令 $\text{z}$ 的后继是 $\text{a}$），求 $S$ 是否能变成回文串。

$n\le 5\times 10^4$，$m\le 10^5$，字符集为全体小写字母。

赛时想的一个转化：将 $S$ 从中间分开，右边的字符串翻转一下；对于 $[l,r]$ 整个在右边的情况下就翻到左边来，$+1$ 变成 $-1$；若 $[l,r]$ 跨过中间，那么若把右边翻过去重合部分等于没操作，于是直接保留没重合的部分。问题变成给你两个字符串 $S,T$ 和若干区间，每个区间要么让字符变成前驱要么变成后继，求是否可以在操作后 $S$ 变成 $T$。然而这个转化似乎做不了。

区间变后继相当于在模 $26$ 意义下做区间加法。考虑将 $S$ 进行差分，那么 $S$ 为回文当且仅当左右对应位置和为 $0$（具体位置视 $n$ 的奇偶性而定）；一次区间加法相当于 $d_l\leftarrow d_l+1,d_{r+1}\leftarrow d_{r+1}-1$，可以发现这两个位置在操作后和不变（默认模 $26$ 意义下）。若我们把和保持不变的点连无向边，那么就会构成若干连通块。连通块之间无影响，那么最终判一下每个连通块的和为 $0$ 即可。但是为什么总和为 $0$ 就意味着对应位置和为 $0$ 仍不清楚。可能是假的？

代码还没写。

T4

给定二维平面上 $n$ 个点，$i$ 和 $j$ 能够匹配当且仅当 $x_i=x_j$ 或 $y_i=y_j$。求一组两两匹配的方案。

$n\le 10^5$。

赛时并没有写出暴力。一个套路的操作是：考虑将每个 $x$ 建一个点，每个 $y$ 建一个点，称为虚点；然后所有点向对应虚点连边，这样构成若干连通块，显然连通块外的点无法与连通块内进行匹配，那么无解的情况就是存在一个连通块的大小是奇数。我们只在每个连通块中考虑。不妨随便拿一棵生成树出来考虑这么构造：对于所有虚点，显然儿子和父亲都是实点，先把儿子两两配对，若有多的就和父亲进行匹配。这是个不断删子树的过程，正确性显然。

namespace STD {const int maxn = 1e5 + 5;int posx[maxn], posy[maxn], n;struct Point {int x, y;Point(int x0 = 0, int y0 = 0) { x = x0, y = y0; }} a[maxn];namespace Graph {const int N = maxn * 3;struct Edge { int to, nxt; } e[N << 1];int head[N], ecnt = 0;void addEdge(int u, int v) {e[++ ecnt] = Edge { v, head[u] };head[u] = ecnt;}} using namespace Graph;vector<pair<int, int> > way;int siz[maxn]; bool ok, used[maxn], vis[maxn];void addAns(int u, int v) {used[u] = used[v] = 1;way.emplace_back(u, v);} int fa[maxn];void dfs(int u, int f) {vis[u] = 1, fa[u] = f;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (!vis[v]) dfs(v, u);} if (u > n) {int mor = 0;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to; if (fa[v] != u) continue;if (!mor) mor = v;else addAns(mor, v);} if (mor && f && !used[f]) addAns(mor, f);}}int main() {scanf("%d", &n), memset(vis, 0, sizeof(vis)), way.clear();for (int i = 1; i <= n; i ++)scanf("%d %d", &a[i].x, &a[i].y), posx[i] = a[i].x, posy[i] = a[i].y;sort(posx + 1, posx + n + 1), sort(posy + 1, posy + n + 1);int xcnt = unique(posx + 1, posx + n + 1) - posx - 1;int ycnt = unique(posy + 1, posy + n + 1) - posy - 1;for (int i = 1; i <= n; i ++) {int x = lower_bound(posx + 1, posx + xcnt + 1, a[i].x) - posx;int y = lower_bound(posy + 1, posy + ycnt + 1, a[i].y) - posy;a[i] = Point(x, y), addEdge(i, x + n), addEdge(i, y + xcnt + n);addEdge(x + n, y), addEdge(y + xcnt + n, i);} for (int i = 1; i <= n; i ++) if (!vis[i]) dfs(i, 0);for (int i = 1; i <= n; i ++) if (!used[i]) return puts("No"), 0;puts("Yes"); for (auto [x, y] : way) printf("%d %d\n", x, y);return 0;}
}