ak了，代码做了点改动来更易读，有可能有地方有点小问题。

A

给你一个数组，每次操作你能选两个数，把较小的放到数组头部，较大的数放数组尾部，问最少多少次操作能将数组变为升序。

类似于贪心？或者说dp？感觉是乱搞搞。

#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n;
  cin >> n;
  vector<int> dp(n + 1, 0);
  int nm = n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    dp[x] = dp[x - 1] + 1;
    nm = min(nm, max(x - dp[x], n - x));
  }
  cout << nm << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

B

给你一棵树，n个操作，每个操作有两种：

+ 1 x 表示输出x节点所有子节点权值和

+ 2 x 表示将x的最重子节点与自己旋转，最重子节点指的是它的所有子节点里子树节点数量最多的节点

模拟一下就行了

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
vector<int> g[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<long long> a(n);
  for (auto &x : a) cin >> x;
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<long long> cnt(n), val(n), f(n);
  auto cmp = [&](int x, int y) {
    return cnt[x] != cnt[y] ? cnt[x] > cnt[y] : x < y;
  };
  vector<set<int, decltype(cmp)>> sons(n, set<int, decltype(cmp)>(cmp));
  auto dfs = [&](auto &dfs, int now, int fa) -> void {
    f[now] = fa;
    for (auto x : g[now]) {
      if (x != fa) {
        dfs(dfs, x, now);
        cnt[now] += cnt[x];
        val[now] += val[x];
        sons[now].insert(x);
      }
    }
    cnt[now]++;
    val[now] += a[now];
  };
  dfs(dfs, 0, -1);
  int root = 0;
  auto remove_from = [&](int x, int fa) {
    sons[fa].erase(x);
    val[fa] -= val[x];
    cnt[fa] -= cnt[x];
  };
  auto insert_into = [&](int x, int fa) {
    cnt[fa] += cnt[x];
    val[fa] += val[x];
    sons[fa].insert(x);
  };
  while (m--) {
    int t, x;
    cin >> t >> x;
    t--;
    x--;
    if (t == 0) {
      cout << val[x] << "\n";
    } else {
      if (sons[x].empty()) continue;
      if (x == root) {
        int t = *sons[x].begin();
        remove_from(t, x);
        insert_into(x, t);
        root = t;
        f[t] = -1;
        f[x] = t;
        continue;
      }
      int ff = f[x];
      int s = *sons[x].begin();
      remove_from(x, ff);
      remove_from(s, x);
      insert_into(x, s);
      insert_into(s, ff);
      f[x] = s;
      f[s] = ff;
    }
  }
  return 0;
}

C

给n个点，两个点距离表示为他们横纵坐标差的绝对值的最小值。求任意两点最大距离。

二分答案

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<array<long long, 2>> v(n);
  for (auto &x : v) cin >> x[0] >> x[1];
  sort(v.begin(), v.end());
  vector<int> ymina(n), ymaxa(n);
  vector<int> yminb(n), ymaxb(n);
  long long ymin = v[0][1];
  long long ymax = v[0][1];
  for (int i = 0; i < n; i++) ymina[i] = ymin = min(ymin, v[i][1]);
  for (int i = 0; i < n; i++) ymaxa[i] = ymax = max(ymax, v[i][1]);
  ymin = v.back()[1];
  ymax = v.back()[1];
  for (int i = n - 1; i >= 0; i--) yminb[i] = ymin = min(ymin, v[i][1]);
  for (int i = n - 1; i >= 0; i--) ymaxb[i] = ymax = max(ymax, v[i][1]);
  long long l = 0, r = 2e9 + 1;
  auto check = [&](long long t) {
    int r = 0;
    for (int i = 0; i < n; i++) {
      while (r < n && v[r][0] - v[i][0] < t) r++;
      if (r == n) return false;
      long long a[] = {ymina[i], ymaxa[i]};
      long long b[] = {yminb[r], ymaxb[r]};
      for (auto x : a)
        for (auto y : b)
          if (abs(x - y) >= t) return true;
    }
    return false;
  };
  while (l < r) {
    long long mid = (l + r) / 2;
    if (l + 1 == r) {
      if (check(r))
        l++;
      else
        r--;
    }
    if (check(mid))
      l = mid;
    else
      r = mid;
  }
  cout << l;
  return 0;
}