NOI 七

A.

构造题。

观察要求带 \(\left\lfloor n\log n \right\rfloor\) ，思考什么东西带 \(\log\) ，考虑分治。

将序列对半分开，发现操作右侧是和左侧无关的，操作完右侧之后直接操作 \(1\) 就可以将左侧翻到右侧。

那么只要左右采取类似的构造方式，次数大概就是 \(O(n\log n)\) 的（可以归纳证明）。

然后只需要递归构造就好了，注意传个参数表示是否需要翻转。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 2e5 + 7;
typedef long long ll;
typedef unsigned ui;
typedef std::pair<int, int> PII;bool FIRPOS;int T, n, a[LN], tot;bool ENDPOS;#define md ((l + r) >> 1)
void solve(int l, int r, int op) {if (l == r) return a[l] = ++tot, void();if (!op) solve(md + 1, r, op), solve(l, md, op ^ 1);else solve(l, md, op), solve(md + 1, r, op ^ 1);
}
ll qry() { ll ans = 0;lep(i, 1, n) {rep(j, n, 1) if (a[j] == i) {ans += n - j + 1;std::reverse(a + j, a + n + 1);break;}}return ans;
}int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock(), Test;std::cin >> Test;while (Test--) {std::cin >> n, tot = 0;solve(1, n, 0);lep(i, 1, n) std::cout << a[i] << ' ';std::cout << '\n' << qry() << '\n';}#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

B.

推式子获得不考虑管道的答案，记 \(t(a, b, c, d)\) 为 \((a, b)\rightarrow (c, d)\) 经过管道数量的最大值。

去掉对称和翻转的情况，只剩下了左上 - 右下这种走向。

我们将每个管道的终点拿出来考虑，对于一个起点 \((a, b)\) 和一个终点 \(t\) ，记 \(f(a, b, t)\) 为 \((a, b)\) 到 \(t\) 经过管道数量的最大值。

那么对于不同的 \(f\) 值，\(t\) 形如：

如果要容斥计算的话太困难了，我们直接将面积并的贡献全部变成 \(1\) 。

每个值为 \(f\) 的 \(t\) 左上一定有值为 \(f-1\) , \(f-2\) , \(\cdots\) 所以贡献是对的。

面积并的话就提前排好序，依次计算即可。

然后考虑如何处理 \(f\) ，容易得到一个倒着递推的做法。

然后发现，\(f(a, b, t)\) 只能从右侧，下侧，或者起点为 \((a, b)\) 的管道的终点转移过来。

所以如果将起点的横纵坐标看作值域上的断点，分成了 \(m\) 块，那么整体就被分成了 \(m^2\) 块，每个块内的 \(f(\cdots, t)\) 值是相等的。

复杂度降到 \(O(m^3)\) 。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 500 + 7;
const int mod = 1e9 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int n, m, ans, P, X, Y, f[LN * LN][LN], ren[LN];
std::vector <int> dx, dy, ct[LN];
std::vector <std::array<int, 3> > eg[LN * LN];
std::vector <std::array<int, 4> > gi, go;bool ENDPOS;il int add(int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
il void upa(int&u, int v) { u = add(u, v); }
il int mul(ll u, ll v) { return u * v >= mod ? u * v % mod : u * v; }
il void upm(int&u, int v) { u = mul(u, v); }
il int MyPow(int a, int b) { int ans = 1; for (; b; b >>= 1, upm(a, a)) if (b & 1) upm(ans, a); return ans; }
il int id(int a, int b) { return (a - 1) * Y + b; }
il PII trn(int c) { int a = (c + Y - 1) / Y, b = c - (a - 1) * Y; return { a, b }; }
void solve(std::vector <std::array<int, 4> > g) { int a, b, c, d, p;if (!g.size()) return;dx.push_back(0), dy.push_back(0), dx.push_back(n), dy.push_back(n), P = g.size();for (auto t : g) dx.push_back(t[0]), dy.push_back(t[1]);std::sort(dx.begin(), dx.end()), dx.erase(std::unique(dx.begin(), dx.end()), dx.end()), X = dx.size() - 1;std::sort(dy.begin(), dy.end()), dy.erase(std::unique(dy.begin(), dy.end()), dy.end()), Y = dy.size() - 1;p = 0;for (auto t : g) {a = std::lower_bound(dx.begin(), dx.end(), t[0]) - dx.begin(),b = std::lower_bound(dy.begin(), dy.end(), t[1]) - dy.begin();c = std::lower_bound(dx.begin(), dx.end(), t[2]) - dx.begin(),d = std::lower_bound(dy.begin(), dy.end(), t[3]) - dy.begin();eg[id(a, b)].push_back({id(c, d), t[2], t[3]}), ren[p] = p; ++p;}PII tmp;std::memset(f, 0, sizeof(f));rep(i, X * Y, 1) { tmp = trn(i);lep(j, 0, P - 1) {if (tmp.first < X) f[i][j] = f[i + Y][j];if (tmp.second < Y) f[i][j] = std::max(f[i][j], f[i + 1][j]);for (auto t : eg[i]) if (t[1] <= g[j][2] and t[2] <= g[j][3])f[i][j] = std::max(f[i][j], f[t[0]][j] + 1);}eg[i].clear();}std::sort(ren, ren + P, [=](const int&x, const int&y){ return g[x][2] == g[y][2] ? g[x][3] < g[y][3] : g[x][2] < g[y][2]; });ll val;lep(i, 1, X * Y) {lep(j, 0, P - 1)if (f[i][ren[j]] > 0) ct[f[i][ren[j]]].push_back(ren[j]);tmp = trn(i), val = mul(2, mul(dx[tmp.first] - dx[tmp.first - 1], dy[tmp.second] - dy[tmp.second - 1]));lep(j, 1, m) {p = n + 1;for (auto v : ct[j]) {if (g[v][3] < p)upa(ans, mod - mul(p - g[v][3], mul(val, n - g[v][2] + 1))), p = g[v][3];}ct[j].clear();}}dx.clear(), dy.clear();
}int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock(), a, b, c, d, p;std::cin >> n >> m;lep(i, 1, m) {std::cin >> a >> b >> c >> d;b < d ? gi.push_back({a, b, c, d}) : go.push_back({a, n - b + 1, c, n - d + 1});}upa(ans, mul(mul(n, n - 1), mul(2 * n - 1, MyPow(6, mod - 2))));upa(ans, mul(mul(n, n - 1), MyPow(2, mod - 2)));upm(ans, 2 * mul(n, n));solve(gi), solve(go);std::cout << ans << '\n';#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}