https://codeforces.com/contest/713/problem/B

题目大意

给定 $n \times n \ (n \le 2^16)$ 个方格区域，上面有两个未知的，不相交的，平行于坐标轴的矩形。 可以给出不超过 $200$ 次平行于坐标轴的矩形的询问（左上右下坐标），每次会给出完全包含在询问区域中的矩形个数。 最后需要回答每个矩形的左上右下角的位置

简要题解

对于两个不相交的矩形，必有一条水平线或竖直线分割它们。我们可以尝试分别从上下边界二分这条线。如果二分的位置不重合则说明已经将两个矩形分开，则对单个矩形单独二分四个边界即可。如果二分的位置重合，则说明两个矩形并不是上下排布，而是左右排布的，重新进行二分即可。

这里每次二分花费为 $16$ 左右，一共最多需要进行 $12$ 次二分，不会超出边界（当然实际上下面代码可以复用一些二分的结果，可以做到更低）。

复杂度

$T$：$O(\log(N))$

$S$：$O(1)$

代码实现

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

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

int query(int x1, int y1, int x2, int y2) {
  cout << "? " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
  int ans; cin >> ans;
  return ans;
}

void checktop(int& x1, int y1, int x2, int y2, int t) {
  int l = x1 + 1, r = x2;
  int ans = x1, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (query(mid, y1, x2, y2) >= t) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  x1 = ans;
}

void checkbot(int x1, int y1, int& x2, int y2, int t) {
  int l = x1, r = x2 - 1;
  int ans = x2, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (query(x1, y1, mid, y2) >= t) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  x2 = ans;
}

void checklft(int x1, int& y1, int x2, int y2, int t) {
  int l = y1 + 1, r = y2;
  int ans = y1, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (query(x1, mid, x2, y2) >= t) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  y1 = ans;
}

void checkrgt(int x1, int y1, int x2, int& y2, int t) {
  int l = y1, r = y2 - 1;
  int ans = y2, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (query(x1, y1, x2, mid) >= t) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  y2 = ans;
}

void solve() {
  int n; cin >> n;
  int x1 = 1, y1 = 1, x2 = n, y2 = n;
  // checktop(x1, y1, x2, y2, 2);
  // checkbot(x1, y1, x2, y2, 2);
  // checklft(x1, y1, x2, y2, 2);
  // checkrgt(x1, y1, x2, y2, 2); // 不用在最开始二分边界

  int x11 = x1, y11 = y1, x12 = x2, y12 = y2;
  int x21 = x1, y21 = y1, x22 = x2, y22 = y2;

  checkbot(x11, y11, x12, y12, 1);
  checktop(x21, y21, x22, y22, 1);

  if (x12 >= x21) {
    x12 = x2;
    x21 = x1;
    checklft(x11, y11, x12, y12, 1);
    checkrgt(x21, y21, x22, y22, 1);
  }

  checkbot(x11, y11, x12, y12, 1);
  checktop(x11, y11, x12, y12, 1);
  checklft(x11, y11, x12, y12, 1);
  checkrgt(x11, y11, x12, y12, 1);
  checktop(x21, y21, x22, y22, 1);
  checkbot(x21, y21, x22, y22, 1);
  checkrgt(x21, y21, x22, y22, 1);
  checklft(x21, y21, x22, y22, 1);

  cout << "! " << x11 << ' ' << y11 << ' ' << x12 << ' ' << y12 << ' '
      << x21 << ' ' << y21 << ' ' << x22 << ' ' << y22 << endl;
}

int main() {
  int t = 1; 
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}