直接用树上差分差分出链上的值插出来的 trie 就好了。
【提交记录】
首先差分出值域 [l,r], 然后对于值域 [l,r] 分成 [l,mid] 和 [mid+1,r], 然后显然 siz 大于 siz[l,r]/2 的最多只能有一边, 有的话继续二分, 否则 return 无解即可。
【提交记录】
首先, [b,c] 必选, 然后选一段 [a,b) 的后缀和一段 (c,d] 的前缀(都是可空的)。
考虑中位数的定义:最大的小于其的数 < n/2 的数。
使用二分, 每次二分出 mid, 然后由于题目要求中位数尽量大, 所以现在就要决定前缀和后缀使得前缀加后缀加 [b,c] 的值域里小于 mid 的尽量多。(这个东西一般是把≥ mid 的变成 1, < mid 的变成 -1, 然后看看加起来是不是 ≥ 0, 是的话中位数就 ≥ mid)
可以用可持久化线段树把值域可持久化, 这样就可以做了。
【提交记录】
这题我的代码长度可能是少数没压就 2k 以下的((/// w ///)
区间压同一个数进栈,单点弹出,区间求栈顶和。
直接把压栈看成更新版本, 单点弹出看成退一个版本, 用可持久化线段树维护。
仔细想想可以学到许多
【提交记录】
联系客服