本题解是官方题解的 AI 中文翻译。

子任务 1. 如果所有 $w_i = 1$，那么答案就是最短路长度减去 $p$，可以用 Dijkstra 算法在 $O(m \log n)$ 内找到。

子任务 4. 如果所有 $s_i \leq 100$，可以设计状态 $dp[v][ans] = \text{最大剩余金钱}$，转移方式类似 Dijkstra 算法。注意到答案不会超过 $S \cdot n$，其中 $S = \max s_i$。因此总复杂度为 $O(S \cdot n \cdot (n + m) \cdot \log n)$。

子任务 2. 注意表演可以“延后”进行。当我们钱不够过某条边时，可以在已经经过的顶点中提前多次表演，以获取最多的钱。如果图是一个两端分别为 $1$ 和 $n$ 的链（bamboo），只需在前缀中维护 $w_i$ 最大的顶点，每当钱不够时就在该顶点表演。这样复杂度为 $O(n)$。

完整解法. 借鉴子任务 2 的思路，可以设计状态 $dp[v][best] = (\textit{最少表演次数}, \textit{最大剩余金钱})$，其中 $v$ 表示当前所在顶点，$best$ 表示已经经过的、$w_i$ 最大的顶点。可以证明，最优策略是先最小化表演次数，再最大化剩余金钱。该动态规划的转移方式与子任务 4 类似，总复杂度为 $\mathcal{O}(mn \log n)$。

Problem Link

可以把我们的操作看成询问区间中假币标号和。

首先我们有一个朴素的做法，对值域倍增分块，那么如果一个区间中假币个数 $\le 1$ 可以直接判断出来，否则按 $[l,mid],[mid+1,r]$ 分治即可。

但是这样如果有两个标号接近的假币依然可以把询问次数变成 $k\log n$ 级别。

考虑每次取恰当的 $mid$ 使得两侧都有假币。

如果我们知道区间中的假币数量，则取 $mid$ 为标号平均值必定合法。

那么对 $c$ 二分，检验只要看对应的 $mid$ 是否合法，可以证明询问次数为 $2k\log k$ 级别。

如果每次根据区间内元素和动态计算 $c$ 的范围，此时的询问次数非常接近题目限制，还需要一点常数优化。

我们用上递归过程中所有的信息来优化 $c$ 的范围，直接在搜索的过程中记录 $c$ 的上下界，并且分治的时候优先递归 $c$ 取值范围较小的一侧。

还要去掉顶层值域分块，通过一些平凡的判断来处理 $c=1$ 的影响。

时间复杂度 $\mathcal O(k\log n)$。

代码：

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
vector <int> q;
ll qry(int x,ll z) {
	cout<<"? "<<x<<endl;
	ll o; cin>>o;
	return 1ll*x*(x+1)/2-o-z;
}
int n,k;
void add(int x) { q.push_back(x); }
int ql(ll w,int L) {
	int x=0;
	for(;w>=L;++x,w-=L,++L);
	return x;
}
int qr(ll w,int R) {
	int x=0;
	for(;R&&w>=R;++x,w-=R,--R);
	return x;
}
int dfs(int l,int r,int cl,int cr,ll o,ll w) {
	if(!w) return 0;
	if(l<=w&&w<=2*l) return add(w),1;
	cl=max({1,cl,qr(w,r)}),cr=min(cr,ql(w,l));
	if(cr<=1) return add(w),1;
	int cm=(cl+cr+1)>>1,mid=w/cm;
	ll v=mid<l?0:mid>=r?w:qry(mid,o);
	if(!v) return dfs(mid+1,r,cl,cm-1,o,w);
	if(v==w) return dfs(l,mid,cm+1,cr,o,w);
	int xl=max(qr(v,mid),cl-ql(w-v,mid+1)),xr=min(ql(v,l),cr-qr(w-v,r));
	int yl=max(qr(w-v,r),cl-ql(v,l)),yr=min(ql(w-v,mid+1),cr-qr(v,mid)),c=0;
	if(xr-xl<=yr-yl) {
		c+=dfs(l,mid,xl,xr,o,v);
		c+=dfs(mid+1,r,cl-c,cr-c,o+v,w-v);
	} else {
		c+=dfs(mid+1,r,yl,yr,o+v,w-v);
		c+=dfs(l,mid,cl-c,cr-c,o,v);
	}
	return c;
}
void solve() {
	cin>>n>>k,q.clear();
	dfs(1,n,k,k,0,qry(n,0));
	sort(q.begin(),q.end());
	cout<<"! "; for(int x:q) cout<<x<<" ";
	cout<<endl; int o; cin>>o;
}
signed main() {
	int _; cin>>_;
	while(_--) solve();
	return 0;
}