原题链接
补题调了四个小时，力竭了。
解析
考虑二分。
考虑如何 check。设当前要判断中位数是否能 \(\ge x\)，那么最终应该至少有 \(\frac{N+M+1}{2}\) 根棍子的长度 \(\ge x\)，后文中称这些长度 \(\ge x\) 的棍子为长棍子。于是我们希望尽可能拆分长度大于等于 \(2x\) 的棍子，因为这样可以产生另一根长棍子。除此之外，剩下的操作次数可以用来拆分长度为 \(2x-1\) 或介于 \([2,x-1]\) 之间的棍子，此时不会对长棍子数目产生影响；也可以用来拆分长度介于 \([x,2x-2]\) 之间的棍子，但是由于每拆一个会少一根长棍子，所以要保证拆分之后仍然有 \(\frac{N+M+1}{2}\) 根长棍子。
最终如果拆分次数没有用完或者长棍子数目少于 \(\frac{N+M+1}{2}\)，则说明中位数 \(< x\)，反之说明中位数 \(\ge x\)。
考虑如何实现拆分，一个思路是将所有可能拆出的长度列出来然后从大到小拆。事实上，拆解后不同长度的个数是可以接受的。
对于一个偶数，会拆成两个相同的数，贡献一个长度。
对于一个奇数，会拆成一个奇数一个偶数，若大的那个是偶数，设为 \(2x\)，则小的那个是 \(2x - 1\)，下一步拆分分别会分为两个 \(x\) 和 一个 \(x\) 一个 \(x - 1\)，若大的那个是奇数同理。也就是说这种奇偶组合每拆分一次也只贡献两个长度。
于是总的不同长度个数就是 \(O(N \log \max A)\) 的。考虑到全奇数的情况，我选择把数组开到 \(6 \times 10^6\)。
时间复杂度 \(O((N \log \max A)\log(N \log \max A) + N(\log \max A)^2)\)。
代码
注意 long long。
#include <bits/stdc++.h>
#define ls(p) ((p) << 1)
#define rs(p) (((p) << 1) | 1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 5e5 + 5,M = 6e6,mod = 998244353;
int a[N];
ll cnt[M];
int get(int x,vector<int> &v){int l = 0,r = v.size() - 1;while(l < r){int mid = l + r >> 1;if(v[mid] > x) l = mid + 1;else r = mid;}return l;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int T;cin>>T;while(T--){int n;ll m;cin>>n>>m;vector<int> v;v.push_back(1); for(int i=1;i<=n;i++){cin>>a[i];int x = a[i];while(x >= 2){v.push_back(x);if(x & 1){if((x / 2) & 1){v.push_back(x / 2 + 1);x = x / 2;}else{v.push_back(x / 2);x = x / 2 + 1;}}else{x /= 2;}}}cerr<<v.size();sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());reverse(v.begin(),v.end());sort(a + 1,a + n + 1,greater<int>());int l = 1,r = 1e9;while(l < r){ int mid = l + r + 1 >> 1;ll t = m,sum = 0; for(int i=0;i<v.size();i++){cnt[i] = 0;}int x = 0;for(int i=1;i<=n;i++){while(v[x] > a[i]) x++;cnt[x]++;sum += v[x] >= mid;}int pos1 = 0,pos2 = 0; for(int i=0;i<v.size() - 1 && t;i++){ll c = min(t,cnt[i]);if(v[i] >= mid && (v[i] + 1) / 2 < mid){ll x = max(0ll,sum - (n + m + 1) / 2);c = min(c,x);}cnt[i] -= c;if(v[i] >= mid) sum -= c;t -= c;while(v[pos1] > v[i] / 2) pos1++;while(v[pos2] > (v[i] + 1) / 2) pos2++; cnt[pos1] += c;cnt[pos2] += c;if(v[pos1] >= mid) sum += c;if(v[pos2] >= mid) sum += c;}if(t){r = mid - 1;continue;}if(sum >= (n + m + 1) / 2) l = mid;else r = mid - 1;} cout<<l<<'\n';}return 0;
}