写在前面

比赛地址：https://ac.nowcoder.com/acm/contest/57355。

官方题解写得太好了都感觉没有自己整理的必要。

简单写写有启发性的东西。

我是垃圾。

L

发现进行三次操作后有：

每个位置仅与三次操作前该位置上的数有关，则显然对于每个位置均存在操作次数为 3 的倍数的循环节。求出每个位置上目标状态在循环节上是第几个的，问题变为解线性同余方程组。

    //
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, a[kN], b[kN], c[kN];
int lth[3][3], pos[3][3][kN], p[3];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  int now[3] = {1, 1, 1}, ne[3];
  for (int i = 0; i < 3; ++ i) {
    for (int j = 0; j < 3; ++ j) {
      for (int k = 1; k <= n; ++ k) {
        pos[i][j][k] = -1;
      }
    }
  }

  for (int l = 0, i = l % 3; l <= 3 * n; ++ l, i = l % 3) {
    for (int j = 0; j < 3; ++ j) {
      if (pos[i][j][now[j]] == -1) {
        pos[i][j][now[j]] = lth[i][j]; 
        ++ lth[i][j];
      }
    }
    ne[0] = a[now[1]]; 
    ne[1] = b[now[2]];
    ne[2] = c[now[0]]; 
    for (int j = 0; j < 3; ++ j) now[j] = ne[j];
  }
}
LL exgcd(LL a_, LL b_, LL &x_, LL &y_) {
  if (!b_) {
    x_ = 1, y_ = 0;
    return a_;
  }
  LL d = exgcd(b_, a_ % b_, x_, y_);
  LL temp = x_;
  x_ = y_, y_ = temp - a_ / b_ * y_;
  return d;
}
LL lcm(LL x_, LL y_) {
  LL xx, yy, g = exgcd(x_, y_, xx, yy);
  return x_ / g * y_;
}
LL Solve(int i_) {
  LL M = lth[i_][0], ans = p[0];
  for (int j = 1; j < 3; ++ j) {
    LL A = M, B = lth[i_][j], C = (p[j] - ans % B + B) % B, x, y;
    LL g = exgcd(A, B, x, y);
    if (C % g) return -1;

    x = x * C / g % B, ans += x * M;
    M = lcm(M, B), ans = (ans % M + M) % M;
  }
  return ans;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);

  n = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i <= n; ++ i) b[i] = read();
  for (int i = 1; i <= n; ++ i) c[i] = read();
  Init();
  int q = read();
  while (q --) {
    int key[3] = {}, flag1 = 1;
    for (int i = 0; i < 3; ++ i) key[i] = read();
    for (int i = 0; i < 3; ++ i) {
      int flag2 = 0;
      for (int j = 0; j < 3; ++ j) {
        p[j] = pos[i][j][key[j]];
        if (p[j] == -1) {
          flag2 = 1;
          break;
        }
      }
      if (flag2) continue;
      LL ret = Solve(i);
      if (ret != -1) {
        flag1 = 0;
        printf("%lld\n", 3ll * ret + i);
        break;
      }
    }
    if (flag1) printf("-1\n");
  }
  return 0;
}

H

将一组 \((a, b)\) 看做整体，可以发现它们在原数列中的位置关系是完全没有影响的，于是仅需着眼于 \((a, b)\) 中值的大小关系即可。

早注意到这个性质了但是没太在意，场上一直想着顺序对逆序对、、、钻牛角尖了、、、

于是考虑一对 \((a, b)\) 和 \((c, d)\) 在什么情况下交换才会产生贡献。大力手玩可以发现当且仅当 \(a<b\land c > d\) 或者 \(a>b\land c<d\) 时会产生贡献，贡献为区间 \([a, b] \cap [c,d]\) 的长度乘 2。

于是将所有 \((a, b)\) 按 \(a-b\) 的大小关系分类，对于每一类都在另一类中找与之区间交最大的即可。

实现时可以考虑对于待查找的区间 \([a, b]\)，找到左端点小于 \(a\) 的右端点最大的区间。可以对另一类区间按照左端点升序右端点降序排序后，枚举过程中维护最大的右端点；也可以像我这样先对另一类的区间建树状数组再查询前缀最大值。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 3e6 + 10;
//=============================================================
int n, a[kN], b[kN];
int datanum, data[kN];
LL start, ans;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
namespace Bit1 {
  #define lowbit(x) ((x)&(-x))
  const int kNode = kN;
  int f[kN], lim;
  void Init(int lim_) {
    lim = lim_;
    for (int i = 1; i <= lim; ++ i) f[i] = 0;
  }
  void Insert(int pos_, int val_) {
    for (int i = pos_; i <= lim; i += lowbit(i)) {
      f[i] = std::max(f[i], val_);
    }
  }
  int Query(int pos_) {
    int ret = 0;
    for (int i = pos_; i; i -= lowbit(i)) ret= std::max(ret, f[i]);
    return ret;
  }
  #undef lowbit
}
void Init() {
  n = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i <= n; ++ i) {
    b[i] = read();
    start += 1ll * abs(b[i] - a[i]);
  }
  ans = start;

  for (int i = 1; i <= n; ++ i) data[++ datanum] = a[i];
  for (int i = 1; i <= n; ++ i) data[++ datanum] = b[i];
  std::sort(data + 1, data + 2 * n + 1);
  datanum = 0;
  for (int i = 1; i <= 2 * n; ++ i) {
    if (data[i] != data[i - 1]) data[++ datanum] = data[i];
  }
  for (int i = 1; i <= n; ++ i) {
    a[i] = std::lower_bound(data + 1, data + datanum + 1, a[i]) - data;
    b[i] = std::lower_bound(data + 1, data + datanum + 1, b[i]) - data;
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  Init();
  Bit1::Init(2 * n);
  for (int i = 1; i <= n; ++ i) {
    if (b[i] < a[i]) continue;
    Bit1::Insert(a[i], b[i]);
  }
  for (int i = 1; i <= n; ++ i) {
    if (b[i] > a[i]) continue;
    int maxr = Bit1::Query(b[i]);
    if (maxr == 0) continue;
    LL l = data[b[i]], r = std::min(data[a[i]], data[maxr]);
    ans = std::min(ans, start - 2ll * (r - l));
  }

  Bit1::Init(2 * n);
  for (int i = 1; i <= n; ++ i) {
    if (b[i] > a[i]) continue;
    Bit1::Insert(b[i], a[i]);
  }
  for (int i = 1; i <= n; ++ i) {
    if (b[i] < a[i]) continue;
    int maxr = Bit1::Query(a[i]);
    if (maxr == 0) continue;
    LL l = data[a[i]], r = std::min(data[b[i]], data[maxr]);
    ans = std::min(ans, start - 2ll * (r - l));
  }
  printf("%lld\n", ans);
  return 0;
}