记录编号	606645	评测结果	AAAAAAAAAA
题目名称	1438.[NOIP 2013]火柴排队	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2025-10-01 16:31:19	内存使用	4.25 MiB

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 1e5 + 10;
const int MOD = 99999997;
using iint = int[MAXN];

int n;
void work(int a[], int b[]) {
  iint c;
  memcpy(c, a, (n + 1) * sizeof(int));
  sort(c + 1, c + n + 1);
  for (int i = 1; i <= n; ++i) {
    b[i] = lower_bound(c + 1, c + n + 1, a[i]) - c;
  }
}

iint a, b, c, d, map, tree;
#define lowbit(x) (x & -x)
void Add(int x, int y) {
  for (; x <= n; x += lowbit(x)) (tree[x] += y) %= MOD;
}

long long Ask(int x) {
  long long res = 0;
  for (; x; x -= lowbit(x)) res = (res + tree[x]) % MOD;
  return res;
}

int main() {
  freopen("MatchNOIP2013.in", "r", stdin);
  freopen("MatchNOIP2013.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
  }

  work(a, c);
  work(b, d);

  for (int i = 1; i <= n; ++i) {
    map[c[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    d[i] = map[d[i]];
  }

  long long ans = 0;
  for (int i = n; i >= 1; --i) {
    ans = (ans + Ask(d[i] - 1)) % MOD;
    Add(d[i], 1);
  }

  cout << ans << endl;
  return 0;
}