题目

交互题。每次产生一个 的排列 。

每次询问 ，得到 中数的种类数。

要求在 (easy)/(medium)/(hard) 次询问内找到 的位置。。

很厉害的一道题目！然而自己只想到 medium 的做法。但是很喜欢！

题解

easy version

看到 和 ，感觉像是 。于是猜是二分。

然后发现 的情况相当于把每个 配对，最后剩下无法配对的是 和 （ 为偶数时）。考虑把 是奇数和偶数的情况分开解决。

当 为奇数时，我们考虑先把 删去，于是把这个序列分成两个区间时，两个区间内的、无法配对的数的数量是相等的。然后我们把 扔到某一边，这边的无法配对的数的数量会增加，我们就能判定 在哪一边了。

考虑怎么求无法配对的数的数量。设一次询问 的答案为 ，那么 显然就是配对的对数，因此未配对的对数就是 ，也就是 。

于是我们可以通过两次操作把目标范围缩小一半，并且操作次数是十分优秀的 。

然后考虑 为偶数怎么做。发现只是在奇数的情况下多了一个 的干扰。然后我们发现一个区间 含有 当且仅当 ，于是我们可以提前把 的位置二分出来，然后套用奇数的方法，加下特判就好了。操作次数是并不十分优秀的 。但是能够通过 easy version。

medium version

考虑优化 easy version 的做法。

我们发现每次把排列划分成两段时，如果 在同侧，我们其实是不用处理的，直接往未配对较多的一边跳就行；在异侧时，我们得到的 的新范围内一定不会再有 。于是我们发现异侧的情况最多仅有一次，而且我们只需要知道 在哪一边即可。于是我们可以把操作次数优化到 。足以通过 medium version。

hard version

我们发现 最大只有 ，恰好无法通过 hard version。考虑继续优化。

考虑偶数情况一定会经过 的区间，这个区间是较好处理的。分为两种情况。

1. 还未出现 异侧，即 对应的分别是 ；

2. 出现了 异侧，即 其中一个是 ，另一个不一定。

第一种情况是好处理的，通过询问 或 判断其中一个是否为 即可。第二种情况则稍难一些。

由于我们现在的区间为 ，则我们之前一定询问过 这些区间。我们可以利用这些信息。

• 假如 说明加上 之后，和 中的区间匹配上了一个数，于是判断 是否等于 便能得到 这个位置是和前面匹配上的数还是 ；

• 否则，一定有 ，这种情况的处理方式和上面是对称的。

于是我们在 的区间上优化掉了一次操作，操作次数变为 ，可以通过 hard version。

代码

#include <bits/stdc++.h>

bool flg, lft;
int n;
std::map < std::pair<int, int>, int > mp;

int qry(int l, int r, int k)
{
  if (l == r) { return 1; }
  if (l > r) { return 0; }
  if (k == 2 and mp.find({l, r}) != mp.end()) { return mp[{l, r}]; }
  int res = 0;
  printf("? %d %d %d\n", l, r, k); fflush(stdout);
  scanf("%d", &res);
  if (k == 2) { mp[{l, r}] = res; }
  return res;
}

int solve1(int l, int r)
{
  if (l == r) { return l; }
  int k = l + ((r - l) >> 1), x = 2 * qry(1, k, 2) - k, y = 2 * qry(k + 1, n, 2) - (n - k);
  if (x > y) { return solve1(l, k); } else { return solve1(k + 1, r); }
}

int solve0(int l, int r)
{
  if (l == r) { return l; }
  if (r - l == 1)
  {
    if (!flg)
    { 
      if (l > 1) { return ((qry(1, l, n) == 2) ? r : l); }
      else { return qry(r, n, n) == 2 ? l : r; };
    }
    if (qry(1, r, 2) == qry(1, l - 1, 2) + 1)
    {
      if (qry(1, l, 2) == qry(1, l - 1, 2)) { return r; } else { return l; }
    }
    else
    {
      if (qry(r, n, 2) == qry(r + 1, n, 2)) { return l; } else { return r; }
    }
  }
  int k = l + ((r - l) >> 1); int x = 2 * qry(1, k, 2) - k, y = 2 * qry(k + 1, n, 2) - (n - k);
  if (x == y)
  {
    if (!flg)
    {
      if (qry(1, k, n) == 2) { flg = lft = true; } else { flg = true; }
    }
    if (lft) { solve0(k + 1, r); } else { return solve0(l, k); }
  }
  if (x > y) { return solve0(l, k); } else { return solve0(k + 1, r); }
}

int main()
{
  scanf("%d", &n);
  if (n & 1) { printf("! %d\n", solve1(1, n)); } else { printf("! %d\n", solve0(1, n)); }
}