目录
写在前面
比赛地址：https://ac.nowcoder.com/acm/contest/57355。
官方题解写得太好了都感觉没有自己整理的必要。
简单写写有启发性的东西。
我是垃圾。
L
发现进行三次操作后有：
\[(x, y, z)\rightarrow (a_{b_{c_x}}, b_{c_{a_{y}}}, c_{a_{b_{z}}}) \]每个位置仅与三次操作前该位置上的数有关，则显然对于每个位置均存在操作次数为 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;
}