結果

問題 No.1300 Sum of Inversions
ユーザー rabimea
提出日時 2025-07-01 22:09:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,231 bytes
コンパイル時間 2,182 ms
コンパイル使用メモリ 207,928 KB
実行使用メモリ 17,604 KB
最終ジャッジ日時 2025-07-01 22:09:14
合計ジャッジ時間 8,280 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using ll = long long;
constexpr ll P = 998244353;

constexpr int MaxN = 2e5L;
struct FenwickTree {
  static constexpr int IndexOffset = 2;
  static int Lowbit(int x) { return x&(-x); }
  std::vector<ll> b;
  FenwickTree() { b = std::vector<ll>(MaxN + 1 + IndexOffset); }
  void Reset() { fill(b.begin(), b.end(), 0); }
  void Add(int p, ll x) {
    p += IndexOffset;
    for(; p <= MaxN + IndexOffset; p += Lowbit(p)) {
      b[p] += x;
    }
  }
  ll Query(int p) {
    p += IndexOffset;
    ll r = 0;
    for(; p; p -= Lowbit(p)) {
      r += b[p];
    }
    return r;
  }
};

// sum of a_i
ll Solve1(int n, std::vector <int> a, std::vector <int> orig_a) {
  ll r = 0;
  FenwickTree tree_cnt, tree_sum;
  for(int i = n - 1; i >= 0; i --) {
    ll cnt = tree_cnt.Query(a[i] - 1);
    ll sum = tree_sum.Query(a[i] - 1);
    r += ll(orig_a[i]) * (sum % P) % P;
    tree_cnt.Add(a[i], 1);
    tree_sum.Add(a[i], cnt);
  }
  return r % P;
}

// sum of a_j
ll Solve2(int n, std::vector <int> a, std::vector <int> orig_a) {
  FenwickTree tree;
  std::vector <int> cnt_lu(n), cnt_rd(n);
  for(int i = 0; i < n; i ++) {
    cnt_lu[i] = tree.Query(MaxN) - tree.Query(a[i]);
    tree.Add(a[i], 1);
  }
  tree.Reset();
  for(int i = n - 1; i >= 0; i --) {
    cnt_rd[i] = tree.Query(a[i] - 1);
    tree.Add(a[i], 1);
  }
  ll r = 0;
  for(int i = 0; i < n; i ++) {
    r += ll(orig_a[i]) * cnt_lu[i] % P * cnt_rd[i];
  }
  return r % P;
}

// sum of a_k
ll Solve3(int n, std::vector <int> a, std::vector <int> orig_a) {
  reverse(a.begin(), a.end());
  reverse(orig_a.begin(), orig_a.end());
  for(int &x : a) {
    x = n - x;
  }
  return Solve1(n, a, orig_a);
}

std::vector <int> Descretizate(std::vector <int> v) {
  std::map <int, int> f;
  for(int x : v) {
    f[x] = 0;
  }
  int cnt = 0;
  for(auto &[k, v] : f) {
    v = cnt ++;
  }
  std::vector <int> u = v;
  for(int &x : u) {
    x = f[x];
  }
  return u;
}

int main() {
  std::ios::sync_with_stdio(0);
  int n; std::cin >> n;
  std::vector <int> a(n);
  for(int i = 0; i < n; i ++) {
    std::cin >> a[i];
  }
  std::vector <int> des_a = Descretizate(a);
  std::cout << (Solve1(n, des_a, a) + Solve2(n, des_a, a) + Solve3(n, des_a, a)) % P << '\n';
}
0