惜败惜败，比赛结束前 2min 想到正解没时间了。

我们只需要把这些元素用线段树维护，在 pushup 的时候询问即可。问的次数大概是 $O(\sum x+ n\log\sum x)$ 级别的。

不知道为什么建树必须要建到 $2^{11}$ 个。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define fa(p) (p>>1)
map<pair<int,int>,int>res;
int ask(int x,int y)
{
	if(res[{x,y}])return res[{x,y}]-2;
	cout<<"? "<<x<<' '<<y<<endl;
	int ans;cin>>ans;
	res[{x,y}]=ans+2;res[{y,x}]=(ans^1)+2;
	return ans;
}
struct SMTree
{
	struct node{int l,r,mn;}tr[N<<2];
	int a[N];
	void pushup(int p)
	{
		if(tr[lc(p)].mn&&tr[rc(p)].mn)
		{
			if(ask(tr[lc(p)].mn,tr[rc(p)].mn))tr[p].mn=tr[rc(p)].mn;
			else tr[p].mn=tr[lc(p)].mn;
		}
		else tr[p].mn=tr[lc(p)].mn+tr[rc(p)].mn;
	}
	void bt(int p,int l,int r)
	{
		tr[p]={l,r,0};
		if(l==r)
		{
			a[l]=p;
			return;
		}
		int mid=(l+r)>>1;
		bt(lc(p),l,mid);bt(rc(p),mid+1,r);
	}
	void change(int p,int x,int k)
	{
		if(tr[p].l>x||tr[p].r<x)return ;
		if(tr[p].l==tr[p].r)
		{
			tr[p].mn=k;
			return;
		}
		change(lc(p),x,k);change(rc(p),x,k);
	}
	void push(int l,int r)
	{
		map<int,int>mp;deque<int>q;mp.clear();
		for(int i=l;i<=r;i++)if(fa(a[i])&&!mp[fa(a[i])])mp[fa(a[i])]=1,q.push_back(fa(a[i]));
		while(!q.empty())
		{
			int x=q.front();q.pop_front();
			pushup(x);
			if(fa(x)&&!mp[fa(x)])mp[fa(x)]=1,q.push_back(fa(x));
		}
	}
}tr;
signed main()
{
	int n,len=0,lst=0;cin>>n;
	tr.bt(1,1,2048);
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		if(lst)tr.push(lst,lst);
		for(int j=len+1;j<=len+x;j++)tr.change(1,j,j);
		tr.push(len+1,len+x);
		lst=tr.tr[1].mn;
		cout<<"! "<<lst<<endl;
		tr.change(1,lst,0);
		len+=x;
	}
	return 0;
}

我们维护一种外向树关系，小的数向大的数连边。对于每新加的 $x_i$ 个数建一颗线段树。建树的时候处理出大小关系：左右子树中小的连向左右子树中大的。如下图：（图中为了方便是数字连数字，实际写的时候要下标连下标）

然后，我们将 $1$ 数字删去，此时线段树优势在于，删去数字 $1$ 只需要删去其指向的边。如下图：

然后变成许多森林，需要将这些森林合并，具体的，我们对 $[3,2,5]$ 序列再建一颗线段树。那么 $2\to 3$，$3\to 5$。

这样就完成了：删去最小值后，重新将线段树合并，且当前的根节点就是次小值。具体操作时，将根节点的所有儿子们再来一遍线段树即可。

因为这道题每次不断加入新的 $x$ 个数，我们先将这 $x$ 个数构成一棵树，在将其作为根节点的儿子们之一去跑线段树。

总的操作次数为 $O(l+n\log l)$。

#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long

const int N = 4e5 + 5;

int n, sum, stk[N], top;
vector<int> G[N];
map<int, int> vis;

int cmp(int a, int b) {
  cout << "?" << ' ' << a << ' ' << b << endl;
  int x;
  cin >> x;
  return x;
}

int solve(int l, int r) {
  if (l == r) return l;
  int mid = (l + r) >> 1;
  int a = solve(l, mid), b = solve(mid + 1, r);
  if (cmp(a, b)) {
    G[b].push_back(a);
    return b;
  }
  else {
    G[a].push_back(b);
    return a;
  }
}

int solve2(int l, int r) {
  if (l == r) return stk[l];
  int mid = (l + r) >> 1;
  int a = solve2(l, mid), b = solve2(mid + 1, r);
  if (cmp(a, b)) {
    G[b].push_back(a);
    return b;
  }
  else {
    G[a].push_back(b);
    return a;
  }
}

signed main() {
  cin >> n;
  _for(i, 1, n) {
    int x;
    cin >> x;
    sum = sum + x;
    vis[solve(sum - x + 1, sum)] = 1;
    top = 0;
    for (auto v : vis) stk[++top] = v.first;
    int t = solve2(1, top);
    vis.clear();
    for (auto v : G[t]) vis[v] = 1;
    cout << "!" << ' ' << t << endl;
  }
}