最近打比赛分老是上不去，都是小掉一点点，感觉问题其实是在没能完全保证将低于自己分数的题目秒掉。
昨天看了 Um_nik的分享 ，他指出了几个挺有价值的点：
- 没必要过早学习过多的高级算法，先将基础的熟练运用（这跟我之前的感想一样）；
- 并不是通过比赛来学习如何 做出 一道题，比赛的目的是 将会做的题快速地做出来 ；
- 学习如何做题应该是平时在某个题库中大量刷题来完成的；
- 尽可能不要看题解，如果实在不会，就先放着，做下一题，过一段时间再回头看是否能够解决，除非这道题需要一些你现在尚未掌握的特定算法，但通常不是这样的情况。
最近应该会更新一下以前题解写的代码，将代码风格统一，并且将图床已经挂掉的图片重新上传一下。
关于差分，内容跟《算法竞赛进阶指南》以及 这篇分享 大致相同，只是用自己的话来记录一下，加深理解。
差分很多时候与前缀和一起出现，此时一般用来进行区间加的操作，最简单的就不举例了，下面这道题是个很有意思的应用，恰好是上周比赛的题目。
E. New School
题目链接： E. New School
题意：
有 $n$ 位老师和 $m$ 组学生，每组学生至少两人，每位老师和学生都有对应的年龄，可以选择删除一名学生，然后选择 $m$ 位老师与每组学生一一对应，要求组内学生的平均年龄不超过老师的年龄。对于每一位学生，如果将其删除之后，是否存在这样一种分配方案满足上述要求。
解题思路：
先看删除了某一位学生之后的问题，实际上就是两个只包含正数（这里为了方便下面阐述加了这个限制，实际上不一定）数组，长度为 $n$ 的 $a$ 和长度为 $m$ 的 $b$ ，其中 $n\geq m$ ，问是否可以从 $a$ 中取出 $m$ 个数，使得 $a_j\geq b_i$ 。
这是一个可以扩展的模型，这个模型恰好就可以用差分和前缀和去解决：
- 对于 $a$ 的每个数，将 $[1,a_i]$ 加 $1$ ；
- 对于 $b$ 的每个数，将 $[1,b_i]$ 减 $1$ ；
- 如果整个数值范围内，没有一个位置上的数值是负数，那么就可以满足要求。
画图验证一下，不难理解。
如果是单独的问题，直接用数组即可，但这道题相当于是多次询问，因此要多次进行区间加和求整个值域最小值的操作，可以用线段树来完成。
首先算出没有删除学生时，每组学生的平均年龄，用整数来存，要向上取整，然后像上面所述，建立线段树后将每个老师的年龄进行区间加操作，然后对每组学生的平均年龄进行区间减操作。
然后按组枚举每位学生，对于每组，先把之前减去的平均年龄加上，然后对于每位学生，算出该组删掉这位学生后的平均年龄，进行区间加后检查是否有位置的数值为负数，一组结束后，将整组学生的平均年龄再次减去即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
public:
struct Node {
// remember to set default value
int add = 0, mn = 0;
void apply(int l, int r, int v) {
// [l, r] is range of this node
assert(l <= r);
add += v;
mn += v;
}
};
inline Node unite(const Node &a, const Node &b) const {
Node res{};
res.mn = min(a.mn, b.mn);
return res;
}
inline void pushdown(int u, int l, int r) {
assert(u >= 0 && u < 2 * n && l <= r);
int mid = (l + r) >> 1;
int lson = u + 1, rson = u + ((mid - l + 1) << 1);
// [l, r] is range of tr[u]
// pushdown from u into lson and rson
// remember to clear lazy tag in u
if (tr[u].add != 0) {
tr[lson].apply(l, mid, tr[u].add);
tr[rson].apply(mid + 1, r, tr[u].add);
tr[u].add = 0;
}
}
inline void pushup(int u, int lson, int rson) {
tr[u] = unite(tr[lson], tr[rson]);
}
int n;
vector<Node> tr;
void build(int u, int l, int r) {
if (l == r) {
return;
}
int mid = (l + r) >> 1;
int lson = u + 1, rson = u + ((mid - l + 1) << 1);
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(u, lson, rson);
}
template <typename T>
void build(int u, int l, int r, const vector<T> &v) {
if (l == r) {
tr[u].apply(l, r, v[l]);
return;
}
int mid = (l + r) >> 1;
int lson = u + 1, rson = u + ((mid - l + 1) << 1);
build(lson, l, mid, v);
build(rson, mid + 1, r, v);
pushup(u, lson, rson);
}
inline Node query(int u, int l, int r, int ql, int qr) {
// [l, r] is range of tr[u]
// [ql, qr] is range of query
if (ql <= l && r <= qr) {
return tr[u];
}
int mid = (l + r) >> 1;
int lson = u + 1, rson = u + ((mid - l + 1) << 1);
pushdown(u, l, r);
Node res{};
if (qr <= mid) {
res = query(lson, l, mid, ql, qr);
} else if (ql > mid) {
res = query(rson, mid + 1, r, ql, qr);
} else {
res = unite(query(lson, l, mid, ql, qr), query(rson, mid + 1, r, ql, qr));
}
pushup(u, lson, rson);
return res;
}
template <typename... T>
inline void modify(int u, int l, int r, int ml, int mr, const T&... v) {
// [l, r] is range of tr[u]
// [ml, mr] is range of modification
if (ml <= l && r <= mr) {
tr[u].apply(l, r, v...);
return;
}
int mid = (l + r) >> 1;
int lson = u + 1, rson = u + ((mid - l + 1) << 1);
pushdown(u, l, r);
if (ml <= mid) {
modify(lson, l, mid, ml, mr, v...);
}
if (mr > mid) {
modify(rson, mid + 1, r, ml, mr, v...);
}
pushup(u, lson, rson);
}
SegmentTree(int _n) : n(_n) {
assert(n > 0);
tr.resize(2 * n - 1);
build(0, 0, n - 1);
}
template <typename T>
SegmentTree(const vector<T> &v) {
n = (int) v.size();
assert(n > 0);
tr.resize(2 * n - 1);
build(0, 0, n - 1, v);
}
inline Node query(int ql, int qr) {
assert(ql >= 0 && ql <= qr && qr < n);
return query(0, 0, n - 1, ql, qr);
}
inline Node query(int p) {
assert(p >= 0 && p < n);
return query(0, 0, n - 1, p, p);
}
template <typename... T>
inline void modify(int ml, int mr, const T&... v) {
assert(ml >= 0 && ml <= mr && mr < n);
modify(0, 0, n - 1, ml, mr, v...);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
const int N = 100010;
SegmentTree st(N);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
// 老师
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
st.modify(1, a[i], 1);
}
vector<int> sz(m);
// 学生
vector<vector<int>> b(m);
// 每组学生的年龄和
vector<long long> tot(m);
for (int i = 0; i < m; i++) {
cin >> sz[i];
b[i].resize(sz[i]);
for (int j = 0; j < sz[i]; j++) {
cin >> b[i][j];
tot[i] += b[i][j];
}
st.modify(1, (int) ((tot[i] + sz[i] - 1) / sz[i]), -1);
}
for (int i = 0; i < m; i++) {
// 把该组平均年龄先加上
st.modify(1, (int) ((tot[i] + sz[i] - 1) / sz[i]), 1);
for (int j = 0; j < sz[i]; j++) {
// 算出新的平均年龄
int newAvg = (int) ((tot[i] - b[i][j] + sz[i] - 2) / (sz[i] - 1));
st.modify(1, newAvg, -1);
cout << (st.query(1, N - 1).mn >= 0 ? 1 : 0);
st.modify(1, newAvg, 1);
}
st.modify(1, (int) ((tot[i] + sz[i] - 1) / sz[i]), -1);
}
cout << '\n';
for (int i = 0; i < n; i++) {
st.modify(1, a[i], -1);
}
for (int i = 0; i < m; i++) {
st.modify(1, (int) ((tot[i] + sz[i] - 1) / sz[i]), 1);
}
}
return 0;
}
100. 增减序列
题目链接： 100. 增减序列
题意：
给定一个长度为 $n$ 的数列，每次可以选择一个区间 $[l,r]$ ，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
解题思路：
最终状态下所有数都一样，意味着差分数组 $b$ 中， $b_{1\dots n-1}$ （下标从 $0$ 开始）数值都为 $0$ 。而进行区间加，相当于在差分数组上对 $b_l$ 加 $1$ ，对 $b_{r+1}$ 减 $1$ ，区间减同理。而对于 $b_0$ 和 $b_{n}$ 来说，是可以随便取的，它们正好是决定了整个数组的数值。
所以问题转化成：
- 至少操作多少次，可以使 $b_{1\dots n-1}$ （下标从 $0$ 开始）数值都为 $0$ ；
- $b_0$ 有多少种取值。
贪心地，当 $b_{1\dots n-1}$ 中有正有负，就可以一次改变两个数，如果只剩下正数或只剩下负数，那么只能将这个数与 $b_0$ 或 $b_n$ 配对，因此最少操作数应该是 $max(pos,neg)$ ，其中 $pos$ 表示正数和， $neg$ 表示负数的绝对值之和，而 $b_0$ 的取值范围是 $1+|pos-neg|$ 。
本题是差分的最常见应用，也就是进行区间加减，主要考察了数组形态和差分数组的关系。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
long long pos = 0, neg = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i > 0) {
b[i] = a[i] - a[i - 1];
if (b[i] > 0) {
pos += b[i];
} else {
neg -= b[i];
}
}
}
cout << max(pos, neg) << '\n';
cout << abs(pos - neg) + 1 << '\n';
return 0;
}
101. 最高的牛
题目链接： 101. 最高的牛
题意：
有 $n$ 头牛呈一行排列，如果两头牛之间的牛都比它们矮，那么这两头牛可以互相看见，只给出身高最高的牛，以及 $m$ 对关系，每对关系表示哪些牛可以互相看见，问所有牛身高的最大取值是多少。
解题思路：
初始时令所有牛都为最大值，对于每对关系 $[l,r]$ ，意味着 $[l+1,r-1]$ 中的牛，肯定会比在 $l$ 和 $r$ 的牛要矮至少 $1$ 个单位，因此可以将 $[l+1,r-1]$ 进行区间减 $1$ 的操作，最后通过前缀和求出每个位置的值就是最大取值。
这题个人认为就是考察观察能力和差分在基础的区间加减的应用。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, p, h, m;
cin >> n >> p >> h >> m;
--p;
vector<int> b(n);
b[0] = h;
vector<pair<int, int>> a(m);
for (auto &[x, y] : a) {
cin >> x >> y;
--x;
--y;
if (x > y) {
swap(x, y);
}
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
for (auto &[l, r] : a) {
++l, --r;
if (l <= r) {
b[l] -= 1;
if (r + 1 < n) {
b[r + 1] += 1;
}
}
}
for (int i = 0; i < n; i++) {
if (i > 0) {
b[i] += b[i - 1];
}
cout << b[i] << '\n';
}
return 0;
}
下面两道题是一样的，唯一区别是后面一道需要离散化。
4007. 非零段划分
题目链接： 4007. 非零段划分
题意：
先在原题里查看非零段的定义，然后选择一个数 $p$ ，序列中小于 $p$ 的数全部变成 $0$ ，问非零段个数最多为多少。
解题思路：
分析时，想象成一个二维的柱状图，然后选择一条线 $y=p$ ，问以 $y=p$ 横轴，以上的连续段最多为多少。
常规的想法就是排序枚举，枚举 $y$ ，有些 $y$ 是没有意义的，所以只需要枚举序列中的数即可。
当 $y$ 取到 $a_i$ 时，如果 $a_i>a_{i-1}$ 且 $a_i>a_{i+1}$ ，此时会减少一个非零段，如果 $a_i<a_{i-1}$ 且 $a_i<a_{i+1}$ ，此时会增加一个非零段，特殊地定义边界值为 $0$ 。
当然还有非常巧妙的差分做法。
首先像常规做法一样规定边界值为 $0$ ，然后从左到右，画一个折线图，然后想象成一维，将其压缩到 $y$ 轴上，只看非降序的段，每一段进行区间加 $1$ ，整个数轴的最大值就是答案。
排序枚举代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
a.erase(unique(a.begin(), a.end()), a.end());
n = (int) a.size();
const int N = 10010;
vector<vector<int>> idx(N);
set<int> S;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
S.insert(a[i]);
}
idx[a[i]].emplace_back(i);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] <= 0) {
continue;
}
int j = i;
while (j < n && a[j] > 0) {
j++;
}
++cnt;
i = j;
}
int res = cnt;
for (auto &u : S) {
for (auto &i : idx[u]) {
int l = 0, r = 0;
if (i - 1 >= 0) {
l = a[i - 1];
}
if (i + 1 < n) {
r = a[i + 1];
}
cnt -= (int) (l < a[i] && a[i] > r);
cnt += (int) (l > a[i] && a[i] < r);
}
res = max(res, cnt);
}
cout << res << '\n';
return 0;
}
差分代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
const int N = 10010;
vector<int> b(N);
for (int i = 0; i < n; i++) {
int last = (i == 0 ? 0 : a[i - 1]);
if (a[i] > last) {
b[last] += 1;
b[a[i]] -= 1;
}
}
int res = 0, sum = 0;
for (int i = 0; i < N; i++) {
sum += b[i];
res = max(res, sum);
}
cout << res << '\n';
return 0;
}
2014. 岛
题目链接： 2014. 岛
题意：
同上。
解题思路：
同上。
排序枚举代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
vector<int> val;
for (int i = 0; i < n; i++) {
cin >> a[i];
val.emplace_back(a[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for (int i = 0; i < n; i++) {
a[i] = (int) (upper_bound(val.begin(), val.end(), a[i]) - val.begin());
}
a.erase(unique(a.begin(), a.end()), a.end());
n = (int) a.size();
int m = (int) val.size();
vector<vector<int>> idx(m + 1);
set<int> S;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
S.insert(a[i]);
}
idx[a[i]].emplace_back(i);
}
int cnt = 1;
int res = cnt;
for (auto &u : S) {
for (auto &i : idx[u]) {
int l = 0, r = 0;
if (i - 1 >= 0) {
l = a[i - 1];
}
if (i + 1 < n) {
r = a[i + 1];
}
cnt -= (int) (l < a[i] && a[i] > r);
cnt += (int) (l > a[i] && a[i] < r);
}
res = max(res, cnt);
}
cout << res << '\n';
return 0;
}
差分代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> val;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
val.emplace_back(a[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for (int i = 0; i < n; i++) {
a[i] = (int) (upper_bound(val.begin(), val.end(), a[i]) - val.begin());
}
int m = (int) val.size();
vector<int> b(m + 1);
for (int i = 0; i < n; i++) {
int last = (i == 0 ? 0 : a[i - 1]);
if (a[i] > last) {
b[last] += 1;
b[a[i]] -= 1;
}
}
int res = 0, sum = 0;
for (int i = 0; i <= m; i++) {
sum += b[i];
res = max(res, sum);
}
cout << res << '\n';
return 0;
}
以下是最近做的一些有意思的题目。
E - Shiritori
题目链接： E - Shiritori
题意：
给定 $n$ 个字符串，两人轮流使用一个字符串，第一个人没有限制，此后每个人取字符串时，取出的字符串前三个字符必须与对方取的上一个字符串最后三个字符相等，每个字符串可以重复取，不能取的人失败。对于每个字符串，若规定它为第一个取的字符串，两人都在最优操作下，问最终谁是胜者。
解题思路：
在此题中三个字符组成的情况有 $52^3$ 种，不多，可以将每种情况都视作一个点，对于某个字符串 $s_i$ ，将其前缀三个字符形成的字符串和后缀三个字符形成的字符串连边，会发现实际上每次取字符串的操作相对应就是从某个点走到另一个点。
比如当前从 $u$ 走到 $v$ ，如果 $v$ 没有出边，那么走完这一步之后就结束了，这步的操作者胜利。由于两人都进行最优操作，设这样的 $v$ ，也就是没有出边的点为必败点，如果某个点能够走到必败点，那么这个点就是必胜点；如果某个点的所有出边都是走到必胜点，那么这个点就只能成为必败点；其它点就是平局的点。
在实际的实现中，为了方便，对上述图建立其反图，并记录入度，初始时入度为 $0$ 的点都是必败点，进入队列，用队列进行宽搜，遍历每个还没有走过的邻点，入度减少 $1$ ，如果当前点是必败点，邻点直接必胜，必胜的点就直接入队了；如果当前点是必胜点，它的邻点可能选择不走当前点，因为走过来会失败，但如果入度成为 $0$ ，就意味着所有邻点都是必胜点，那么就只能失败了，成为必败点，并且入队。
最后遍历字符串，检查其 后缀 即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int m = 0;
vector<string> s(n);
map<string, int> mp;
for (int i = 0; i < n; i++) {
cin >> s[i];
string l = s[i].substr(0, 3);
if (!mp.count(l)) {
mp[l] = m++;
}
string r = s[i].substr((int) s[i].size() - 3, 3);
if (!mp.count(r)) {
mp[r] = m++;
}
}
vector<int> deg(m);
vector<vector<int>> g(m);
for (int i = 0; i < n; i++) {
string l = s[i].substr(0, 3);
string r = s[i].substr((int) s[i].size() - 3, 3);
g[mp[r]].emplace_back(mp[l]);
deg[mp[l]] += 1;
}
vector<int> q;
// -1 为平局， 0 为必败， 1 为必胜
vector<int> st(m, -1);
for (int i = 0; i < m; i++) {
if (deg[i] == 0) {
q.emplace_back(i);
st[i] = 0;
}
}
for (int qq = 0; qq < (int) q.size(); qq++) {
int u = q[qq];
for (auto &v : g[u]) {
if (st[v] == -1) {
--deg[v];
if (st[u] == 0) {
q.emplace_back(v);
st[v] = 1;
} else if (deg[v] == 0) {
q.emplace_back(v);
st[v] = 0;
}
}
}
}
for (int i = 0; i < n; i++) {
int t = mp[s[i].substr((int) s[i].size() - 3, 3)];
if (st[t] == -1) {
cout << "Draw\n";
}
if (st[t] == 0) {
cout << "Takahashi\n";
}
if (st[t] == 1) {
cout << "Aoki\n";
}
}
return 0;
}
E - Digit Products
题目链接： E - Digit Products
题意：
有多少个正数 $x$ 满足 $x\leq n$ ，且 $x$ 的十进制下每个数字的乘积最多为 $k$ 。
解题思路：
要求 $x\leq n$ ，应该想到数位 DP ，这里的 $k$ 比较大，开不了数组，所以用记忆化搜索，将 $f[i][limit][zero][cur]$ 定义为前 $i$ 个数，当前乘积为 $cur$ ， $limit$ 表示是否已经确定 $cur<n$ ， $zero$ 表示前面是否全部都为 $0$ ，属性是个数。
如果已经将所有数都遍历到了，就根据 $cur$ 是否小于等于 $n$ ，以及凑成的数是否为正数返回，这里一定要检查 $zero$ 是否为 $0$ ，而不能检查 $cur>0$ ，因为像 $101$ 这样的数，乘积为 $0$ ，但却是正数。
如果当前状态已经搜索过，也可以直接返回。
否则就可以在当前的数后面添加数字，根据 $limit$ ，如果已经确定 $cur<n$ ，那么 $[0,9]$ 都可以放，否则只能放 $[0,digit[pos]]$ ，这是数位 DP 的常规套路，往下搜索时，要更新 $cur$ ，如果当前是整个数的最高位，也就是前面全都是 $0$ ，当前放入了第一个非零数，下一层的 $cur$ 就是这个非零数，否则应该将放入的数乘以 $cur$ 。
注意事项：
往数位 DP 的方向想不难，但搜索的细节还是挺多的，而且很抽象，记录答案的数组也很奇特。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
long long x, k;
cin >> x >> k;
vector<int> digit;
while (x > 0) {
digit.emplace_back(x % 10);
x /= 10;
}
reverse(digit.begin(), digit.end());
int n = (int) digit.size();
vector<vector<vector<map<long long, long long>>>> f(n + 1, vector<vector<map<long long, long long>>>(2, vector<map<long long, long long>>(2)));
function<long long(int, int, int, long long)> dp = [&](int pos, int limit, int zero, long long cur) -> long long {
if (pos == n) {
return (long long) (cur <= k && zero == 0);
}
if (f[pos][limit][zero].count(cur)) {
return f[pos][limit][zero][cur];
}
int mx = (limit ? digit[pos] : 9);
long long res = 0;
for (int i = 0; i <= mx; i++) {
res += dp(pos + 1, limit && i == mx, zero && i == 0, zero ? i : i * cur);
}
return f[pos][limit][zero][cur] = res;
};
cout << dp(0, 1, 1, 0) << '\n';
return 0;
}
E. Lexicographically Small Enough
题目链接： E. Lexicographically Small Enough
题意：
给定两个字符串 $s$ 和 $t$ ，每次操作可以交换 $s$ 中任意相邻两个字符的位置，问最少操作多少次可以使得 $s$ 的字典序严格小于 $t$ 。
解题思路：
因为操作是交换相邻的两个字符，所以要往逆序对方向去想，因为要使 $s$ 的字典序尽可能小，其实就是一个排序的过程，而排序的最小操作数其实就是逆序数。
可以枚举在哪一位开始出现严格小于，如果是第 $i$ 位，那么之前的位置字符都是相同的，也就是共同前缀，枚举所有小于 $t_i$ 的字符（如果有的话），就贪心地用尚未固定在共同前缀的且最靠左的字符放到这个位置上，用之前形成共同前缀的操作数以及这个字符需要走的距离来更新答案即可
如果已经不能凑成共同前缀，直接结束。
计算需要走的距离可以用树状数组来维护。
这道题需要一定的前置知识：对于两个字符串 $s,t$ ，每次操作可以交换 $s$ 中任意相邻两个字符的位置，问最少操作多少次可使 $s=t$ 。这个问题同样是用树状数组来做，做法也是相似的，这题实际上就是这个问题的升级版。
代码如下：
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class Fenwick {
public:
vector<T> fenw;
int n;
Fenwick(int _n) : n(_n) {
fenw.resize(n);
}
inline void add(int x, T v) {
assert(x >= 0 && x < n);
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
inline T get(int x) {
T res{};
while (x >= 0) {
res += fenw[x];
x = (x & (x + 1)) - 1;
}
return res;
}
inline T get(int l, int r) {
assert(l >= 0 && l < n && r >= 0 && r < n);
T res = get(r);
if (l - 1 >= 0) {
res -= get(l - 1);
}
return res;
}
inline int kthMin(int k) {
// kthMax = n - kthMin + 1
assert(k >= 1 && k <= n);
int cnt = 0, x = 0;
for (int i = (int) log2(n); i >= 0; i--) {
x += (1 << i);
if (x >= n || cnt + fenw[x - 1] >= k) {
x -= (1 << i);
} else {
cnt += fenw[x - 1];
}
}
return x;
}
};
// struct Node {
// int a = ...; // don't forget to set default value
// inline void operator += (Node &other) {
// ...
// }
// };
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
string s, t;
cin >> n >> s >> t;
const int C = 26;
vector<vector<int>> idx(C);
for (int i = 0; i < n; i++) {
idx[s[i] - 'a'].emplace_back(i);
}
Fenwick<int> fen(n);
for (int i = 0; i < n; i++) {
fen.add(i, 1);
}
const long long INF = (long long) 4e18;
long long res = INF;
vector<int> ptr(C);
long long cur = 0;
for (int i = 0; i < n; i++) {
int x = (int) (t[i] - 'a');
for (int y = 0; y < x; y++) {
if (ptr[y] < (int) idx[y].size()) {
res = min(res, cur + fen.get(idx[y][ptr[y]] - 1));
}
}
if (ptr[x] >= (int) idx[x].size()) {
break;
}
cur += fen.get(idx[x][ptr[x]] - 1);
fen.add(idx[x][ptr[x]], -1);
ptr[x] += 1;
}
if (res == INF) {
res = -1;
}
cout << res << '\n';
}
return 0;
}
我也想上分 呜呜
呜呜我也想变红名
%%
好