250610 模拟赛 T2 题解
题意
给定一棵 \(n\) 个点,以 \(1\) 为根的有根树,第 \(i\) 个点的点权初始为 \(a_i\)。你需要进行 \(q\) 次修改,每次修改给定两个点 \(x,y\),表示交换 \(a_x,a_y\)。你需要在每次操作之后回答一个问题:
记 \(S_u\) 表示 \(u\) 子树内所有点的点权组成的序列,从小到大排好序的结果。记所有 \(S_u\) 中字典序最小的一个为 \(L\),问 \(\sum{[S_u=L]u}\)。
\(n,q\le 2\times 10^5,\ a_i\le 10^9\)
题解
首先注意,\(L\) 肯定是 \(S_1\) 的一个前缀。并且,当且仅当存在一个叶子节点的权值等于 \(1\) 时,\(L=[1]\);其余情况 \(S_u=L\) 的 \(u\) 有且仅有一个。先特判掉叶子的情况。
考虑一个节点 \(u\) 成为答案的条件。容易发现,因为我们只有交换操作,所以 \(S_1\) 是不会改变的。又因为 \(L\) 必须是 \(S_1\) 的前缀,而且 \(L\) 的长度等于答案节点的子树大小,因此一个节点 \(u\) 成为答案当且仅当 \(S_u=S_1[1\sim sz_u]\)。记 \(T_u=S_1[1\sim sz_u]\)。
考虑 \(S_u\) 和 \(T_u\) 匹配的情形:
而不匹配的情形:
1-4 的数量太少
S[u]: 1 1 1 1 2 2 3 3 4 5 5 ...
T[u]: [ 1 1 1 1 2 2 2 3 3 3 3 4 4 4 ] 4 4 4 5 5 5 5 ...
4 太多
S[u]: 1 1 1 1 2 2 2 3 4 4 4 4 4 4
T[u]: [ 1 1 1 1 2 2 2 3 3 3 3 4 4 4 ] 4 4 4 5 5 5 5 ...
\(T_u\) 形如值域上一段前缀,再加上下一个数的一段。记 \(sc[i]\) 表示(离散化之后)\(S_1\) 中小于等于 \(i\) 的数字的数量,\(ac[u]\) 表示最大的满足 \(sc[i]<sz[u]\) 的颜色 \(i\)。例子中,\(ac[i]=3\)。
匹配时,子树内 \(\le ac\) 的数字数量等于 \(sc[ac]\),并且 \(ac+1\) 的数量等于 \(sz[u]-sc[ac]\)。然而,两个维度的信息较难维护,尝试将它们合并成一维。注意到 \(cnt(ac+1)\) 比 \(sz[u]-sc[ac]\) 可大可小,却不会超过 \(sz[u]-cnt(\le ac)\)。即:
并且在匹配时,两个不等号同时取等。这启发我们维护
因为它始终大于等于 \(0\),并且在匹配时取等。
同时我们注意到,在一条根链上随着深度的减小,\(sz\) 单调递增,因此对应的 \(ac\) 也单调递增。对于节点 \(i\) 处的数字 \(a_i\),它会在根链的两个连续区间上分别产生 \(-1,-2\) 的贡献,区间的位置可以使用倍增求得。然后用树剖维护上面的式子,每次修改时进行区间加减,然后查询最小值 \(0\) 出现的位置即可。
不等式可加性
将题目需要的取等关系放在恒成立的不等式中,然后将不等式左右两边分别相加再作差,可以将多个式子压为一个式子。
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 |
|