好像我经常在某个节气整理一些题目，我也不知道为什么 hh 。

G. Trader Problem

题目链接： G. Trader Problem

题意：

初始时有 $n$ 个物品，橱窗有 $m$ 个物品，每个物品都有一个价格，可以取自己的一个价格为 $x$ 的物品，兑换橱窗中价格不超过 $x+k$ 的物品，多次询问 $k$ ，问最多能得到的物品总价值是多少。

解题思路：

先看单次询问是如何处理的。

因为可以不断交换，所以在所有物品中，可以将 $a_i$ 可以得到的物品看作一个集合，其中 $a_i$ 为初始时自己的物品，最终贪心地从和比较大的集合中取数，对于某个集合，如果有 $na$ 个数来自序列 $a$ ，则最多可以从中取 $na$ 个，取够 $n$ 个数即可。

朴素的思路如此，但由于要处理多组询问，那么必须寻找一些特性，会发现如果存在 $k_1<k_2$ ，那么处理 $k_2$ 时合并掉的集合一定包含处理 $k_1$ 时合并的集合，因此这里启发我们按照从小到大的顺序离线处理 $k$ 。

初始时，每个物品单独成为一个集合，集合内维护两个 multiset ，其中 $choose$ 表示对答案贡献的物品， $other$ 表示不选择的物品，同时记录每个物品的集合编号。然后对所有物品的价值排序，求出相邻物品的价值差，记录每个价值差是由哪两个物品形成的，最后对价值差排序。

处理每次询问时，先把小于等于当前 $k$ 的价值差的形成者的集合合并起来，然后记录当前拥有物品的总价值即可。

合并集合时，可以利用启发式合并的技巧，总是将小集合合并到大集合上。合并时，先把小集合的 $choose$ 和 $other$ 都插入到大集合里，然后比较大集合 $choose$ 的最小值和 $other$ 的最大值，不断更新答案。

这样优化之后，时间复杂度最多是 $O(n(log(logn)))$ ，是满足要求的。

代码如下：

#include <bits/stdc++.h>

using namespace std;

class Dsu {
 public:
  vector<int> p, sz;
  vector<multiset<int>> choose, other;
  long long res;
  int n;
  Dsu(int _n) {
    res = 0;
    n = _n + 1;
    p.resize(n);
    choose.resize(n);
    other.resize(n);
    sz.assign(n, 1);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      if (sz[y] < sz[x]) {
        swap(x, y);
      }
      // 将 x 合并到 y
      for (auto &u : choose[x]) {
        choose[y].insert(u);
      }
      for (auto &u : other[x]) {
        other[y].insert(u);
      }
      choose[x].clear();
      other[x].clear();
      // 更新答案
      while (int(choose[y].size()) && int(other[y].size()) && *prev(other[y].end()) > *choose[y].begin()) {
        res += *prev(other[y].end());
        res -= *choose[y].begin();
        choose[y].insert(*prev(other[y].end()));
        other[y].insert(*choose[y].begin());
        choose[y].erase(choose[y].begin());
        other[y].erase(prev(other[y].end()));
      }
      p[x] = y;
      sz[y] += sz[x];
      return true;
    }
    return false;
  }
  inline int getSize(int x) {
    return sz[get(x)];
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  vector<pair<int, int>> a(n + m);
  Dsu d(n + m);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first;
    d.choose[i].insert(a[i].first);
    a[i].second = i;
    d.res += a[i].first;
  }
  for (int i = n; i < n + m; i++) {
    cin >> a[i].first;
    d.other[i].insert(a[i].first);
    a[i].second = i;
  }
  sort(a.begin(), a.end());
  vector<tuple<int, int, int>> gaps(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    int gap = a[i + 1].first - a[i].first;
    gaps[i] = make_tuple(gap, a[i + 1].second, a[i].second);
  }
  sort(gaps.begin(), gaps.end());
  vector<pair<int, int>> query(k);
  for (int i = 0; i < k; i++) {
    cin >> query[i].first;
    query[i].second = i;
  }
  sort(query.begin(), query.end());
  vector<long long> ans(k);
  int i = 0;
  for (auto &[gap, id] : query) {
    while (i < n + m - 1 && get<0>(gaps[i]) <= gap) {
      d.unite(get<1>(gaps[i]), get<2>(gaps[i]));
      i++;
    }
    ans[id] = d.res;
  }
  for (int i = 0; i < k; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

D. Yet Another Sorting Problem

题目链接： D. Yet Another Sorting Problem

题意：

有一个序列，可以对它进行若干次这样的操作：每次操作选择任意三个不同的位置 $i,j,k$ ，将 $a_i$ 放到 $j$ ， $a_j$ 放到 $k$ ，$a_k$ 放到 $i$ 。问是否能够将序列操作成有序的。

解题思路：

这个问题需要一些可以说是 trick 的结论吧，那就是如果三个数都是不同的，每次这样的操作，一定使得逆序对增加 $2$ 或者减少 $2$ 。放到整个序列上，如果整个序列没有重复的数，这样的操作一定是增加或减少偶数个逆序对，且一定能够使得逆序对数量变成 $0$ 或 $1$ 。因此，如果序列没有重复的数，只需要计算逆序对的奇偶性即可。

如果序列有重复的数，则会可能出现一次操作使得逆序对数量增加或减少 $1$ 的情况，那么就一定可以使整个序列的逆序对变成 $0$ 了。

这里有计算一个序列中，有多少个数对 $(i,j)$ 满足某个条件的模板，用法看注释。

代码如下：

#include <bits/stdc++.h>

using namespace std;

// usage:
//  CountPairs(a, [&](int i, int j) { return i < j; });
//  Counts the number of pairs i < j such that func(a[i], a[j]) is true.
template <typename T, typename F = function<bool(const T &, const T &)>>
long long CountPairs(vector<T> a, const F &func) {
  int n = static_cast<int>(a.size());
  vector<T> temp(n);
  function<long long(int, int)> solve = [&](int l, int r) -> long long {
    if (l >= r) {
      return 0;
    }
    int mid = (l + r) >> 1;
    long long res = solve(l, mid) + solve(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid || j <= r) {
      if (i <= mid && (j > r || func(a[i], a[j]))) {
        temp[k++] = a[i++];
      } else {
        res += i - l;
        temp[k++] = a[j++];
      }
    }
    copy(temp.begin(), temp.begin() + k, a.begin() + l);
    return res;
  };
  return solve(0, n - 1);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &u : a) {
      cin >> u;
    }
    long long pairs = CountPairs(a, [&](int i, int j) { return (i > j); });
    if (int(set<int>(a.begin(), a.end()).size()) < n || pairs % 2 == 0) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
  return 0;
}

E1. Asterism (Easy Version)

题目链接： E1. Asterism (Easy Version)

题意：

一开始有 $x$ 颗糖果，有 $n$ 个对手，可以以任意顺序和对手比赛，如果糖果不少于对手，那么获胜并得到一颗糖果，否则失败，进入下一场比赛。定义 $f(x)$ 为初始糖果数为 $x$ 时满足上述条件的顺序排列的个数，给定一个质数 $p(p\leq n)$ ，求出所有 $x$ ，使得 $f(x)$ 不能被 $p$ 整除。

解题思路：

这个问题有点绕，个人觉得是一个比较“勉强”的题目，出题人为了增加难度，花了不少心思去设定了这样一个条件。

有两个关键点，首先是 $p$ 是质数，也就意味着如果所有 $f(x)$ 的因数都不能被 $p$ 整除，那么 $f(x)$ 就满足条件；其次是目标是赢下所有比赛的排列，可能读完题之后被绕进去就忽略了这个条件，那就无从下手了。

由于 $p\leq n$ ，如果 $x$ 大于等于序列的最大值 $mx$ ，那么满足条件的排列数是 $n!$ ，那么一定不满足条件，因此 $x$ 的上限是 $mx-1$ ，然后 $x$ 的下限可以由二分得到。

得到了 $x$ 的取值范围 $[l,r]$ 后，检查范围内所有数，维护一个可选的数的集合，从第一个位置放到最后一个位置，然后在期间检查候选数是否能够被 $p$ 整除。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n, p;
  cin >> n >> p;
  vector<int> a(n);
  map<int, int> mp;
  for (auto &u : a) {
    cin >> u;
    mp[u] += 1;
  }
  sort(a.begin(), a.end());
  auto check = [&](int x) -> bool {
    for (int i = 0; i < n; i++) {
      if (x < a[i]) {
        return false;
      }
      x += 1;
    }
    return true;
  };
  int mx = *max_element(a.begin(), a.end());
  // 二分求下限
  int l = 0, r = mx;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  // 上限
  r = mx - 1;
  vector<int> res;
  for (int x = l; x <= r; x++) {
    // cnt 为候选数
    int cnt = 0;
    // 一开始小于 x 的数都是可选的
    for (int i = 0; i < n; i++) {
      cnt += (int) (x > a[i]);
    }
    int ans = 1;
    for (int i = 0; i < n; i++) {
      // 先加上当前分数 x+i 加入候选集合的数量
      cnt += mp[i + x];
      // 检测是否能够被 p 整除
      ans *= cnt;
      ans %= p;
      // 放入某个数，候选数量减少
      cnt -= 1;
    }
    if (ans) {
      res.emplace_back(x);
    }
  }
  int rn = int(res.size());
  cout << rn << '\n';
  for (int i = 0; i < rn; i++) {
    cout << res[i] << " \n"[i == rn - 1];
  }
  return 0;
}

F - XOR Matching

题目链接： F - XOR Matching

题意：

给定 $m$ 和 $k$ ，要求构造一个序列，长度为 $2^{m+1}$ ，其中 $[0,2^m-1]$ 每个数恰好出现两次，且两个相同的数之间（包括这两个数）的所有数的异或结果为 $k$ 。

解题思路：

其实这道题本身不太难，我觉得处理特例比普通情况会更难一些。

比较显然的是如果 $k$ 大于 $2^m-1$ ，就一定无解。

然后有一个结论，就是对于 $m\neq 1$ ， $[0,2^m-1]$ 的异或和都是 $0$ 。因此如果 $m\neq 1$ ，可以构造一个形如 $0,1,2,…,2^m-1,k,2^m-1,2^m-2,…,0,k$ 的序列。

那么如果 $m=1$ ，只有 $k=0$ 时有解，为 $1,1,0,0$ ，其余情况都无解。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int m, k;
  cin >> m >> k;612 Byte
  if (k > (1 << m) - 1) {
    cout << "-1";
    return 0;
  }
  if (m == 1) {
    if (k == 0) {
      cout << "0 0 1 1\n";
    } else {
      cout << "-1\n";
    }
    return 0;
  }
  for (int i = 0; i <= (1 << m) - 1; i++) {
    if (i != k) {
      cout << i << ' ';
    }
  }
  cout << k << ' ';
  for (int i = (1 << m) - 1; i >= 0; i--) {
    if (i != k) {
      cout << i << ' ';
    }
  }
  cout << k << '\n';
  return 0;
}

B - Do Not Duplicate

题目链接： B - Do Not Duplicate

题意：

给定一个长度为 $n$ 的序列，将它重复 $k$ 次，从头到尾，对于当前的 $x$ ，如果之前出现过，那么就将它到之前的位置（包含这两个数）全部清除掉，问最后剩下的序列。

解题思路：

看似是一个手写模拟，然后找规律搞一下的题目，但其实思路有些抽象，自己做的时候理解了很久，个人觉得是这几道题中最难的。

首先 $k$ 特别大，而且按照题意的处理过程，最后剩下的数最多不会超过 $n$ ，也就是说虽然整个处理的过程非常冗长，但有可能留到最后的数很少，而且只需要关注最后的部分，因为前面的肯定都已经被清除了。

清除的过程也不难，直接模拟一下就行，进一步观察发现，最后可能留下的数只可能是在最后两次重复中。那么如果找到了第一个能够留下的数，后面的直接模拟一下即可。

找到第一个留下的数，可以用倍增实现，定义数组 $len[i][j]$ 为从位置 $i$ 开始，产生了 $2^j$ 次清除，总共清除掉的数的数量，其中 $len[i][0]$ 通过记录每个数的位置倒着找一遍即可，具体实现看代码注释。

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  long long k;
  cin >> n >> k;
  vector<int> a(n);
  const int N = 200010;
  vector<int> pos(N);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  // pos[x] 为下一个 x 的位置
  for (int i = n - 1; i >= 0; i--) {
    pos[a[i]] = i + n;
  }
  const int K = 61;
  const long long INF = (long long) 2e18;
  // 如果从 i 开始，做不到 2^j 次清除，那么就赋值为正无穷
  vector<vector<long long>> len(n, vector<long long>(K, INF));
  // len[i][0] 为从 i 开始，一次清除操作清除的数的个数
  for (int i = n - 1; i >= 0; i--) {
    len[i][0] = pos[a[i]] - i + 1;
    pos[a[i]] = i;
  }
  for (int j = 1; j < K; j++) {
    for (int i = 0; i < n; i++) {
      len[i][j] = min(INF, len[i][j - 1] + len[(i + len[i][j - 1]) % n][j - 1]);
    }
  }
  // cur 是当前已经加入过的数
  // 只要还能清除，就进行清除，直到第一个留在序列的数的位置
  long long cur = 0;
  for (int j = K - 1; j >= 0; j--) {
    if (cur + len[cur % n][j] <= k * n) {
      cur += len[cur % n][j];
    }
  }
  // 暴力处理最后部分
  vector<bool> st(N);
  vector<int> res;
  while (cur < k * n) {
    if (st[a[cur % n]]) {
      while (true) {
        int v = res.back();
        st[v] = false;
        res.pop_back();
        if (v == a[cur % n]) {
          break;
        }
      }
    } else {
      res.emplace_back(a[cur % n]);
      st[a[cur % n]] = true;
    }
    ++cur;
  }
  int rn = int(res.size());
  for (int i = 0; i < rn; i++) {
    cout << res[i] << " \n"[i == rn - 1];
  }
  return 0;
}