結果
問題 | No.2327 Inversion Sum |
ユーザー |
👑 ![]() |
提出日時 | 2023-05-28 14:56:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 4,890 bytes |
コンパイル時間 | 1,114 ms |
コンパイル使用メモリ | 88,092 KB |
最終ジャッジ日時 | 2025-02-13 12:15:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\fenwicktree-atcoder.hpp"#include <cassert>#include <vector>namespace nachia {template <class T> struct FenwickTree {public:FenwickTree() : _n(0){}explicit FenwickTree(int n, T ZERO) : _n(n), a(n, ZERO){}void add(int p, T x){assert(0 <= p && p < _n);p++;while(p <= _n){a[p-1] += T(x);p += p & -p;}}T sum(int r){assert(0 <= r && r <= _n);return sumr(r);}T sum(int l, int r){assert(0 <= l && l <= r && r <= _n);return sumr(r) - sumr(l);}private:int _n;std::vector<T> a;T sumr(int r){T s = 0;while(r > 0){s += a[r-1];r -= r & -r;}return s;}};} // namespace nachia#line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\range-query\\point-add-range-sum.hpp"namespace nachia {template<class T> using PointAddRangeSum = FenwickTree<T>;} // namespace nachia#line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\coordinate-compress.hpp"#include <algorithm>namespace nachia{template<class Elem>class CoordinateCompress {std::vector<Elem> G;std::vector<int> res;std::vector<int> resinv;std::vector<Elem> mRealval;Elem mMaxcoord;bool ok = true;void calc() {if (ok) return;int n = G.size();resinv.resize(n);for(int i=0; i<n; i++) resinv[i] = i;sort(resinv.begin(), resinv.end(), [this](int l, int r) -> bool { return G[l] < G[r]; });res.resize(n);mRealval.clear();int p = 0;res[resinv[0]] = p;mRealval.push_back(G[resinv[0]]);for(int i=1; i<n; i++){if(G[resinv[i-1]] < G[resinv[i]]){ mRealval.push_back(G[resinv[i]]); p++; }res[resinv[i]] = p;}mMaxcoord = p;ok = true;}public:int push(Elem x) {ok = false;int p = G.size();G.push_back(x);return p;}int operator[](int i) {calc();return res[i];}Elem realval(int x) {calc();return mRealval[x];}Elem maxcoord() {calc();return mMaxcoord;}};template<class Elem>std::vector<int> CoordinateCompressInstant(const std::vector<Elem>& A, bool disjoint = false){int n = A.size();std::vector<int> ord(n);for(int i=0; i<n; i++) ord[i] = i;if(disjoint){std::sort(ord.begin(), ord.end(), [&](int l, int r) -> bool { return (A[l] != A[r]) ? (A[l] < A[r]) : (l < r); });std::vector<int> res(n, 0);for(int i=0; i<n; i++) res[ord[i]] = i;return res;}std::sort(ord.begin(), ord.end(), [&](int l, int r) -> bool { return A[l] < A[r]; });std::vector<int> res(n, 0);for(int i=1; i<n; i++) res[ord[i]] = res[ord[i-1]] + ((A[ord[i-1]] < A[ord[i]]) ? 1 : 0);return res;}} // namespace nachia#line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\inversion.hpp"namespace nachia{// x must be coord-compressed enoughlong long Inversion(std::vector<int> x){if(x.empty()) return 0;int N = 1 + *std::max_element(x.begin(), x.end());nachia::PointAddRangeSum<int> rs(N, 0);long long ans = 0;for(int a : x){if(a+1 != N) ans += rs.sum(a+1, N);rs.add(a, 1);}return ans;}} // namespace nachia#line 2 "..\\Main.cpp"#include <iostream>#include <string>#line 6 "..\\Main.cpp"#include <atcoder/modint>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using Modint = atcoder::static_modint<998244353>;int main(){int N, M; cin >> N >> M;vector<pair<int,int>> PK(M);rep(i,M){int p, k; cin >> p >> k; p--; k--;PK[i] = { p, k };}sort(PK.begin(), PK.end());vector<int> K;for(auto a : PK) K.push_back(a.second);Modint f = 1;for(int i=1; i<=N-M; i++) f *= i;vector<int> ck(N+1, 1); ck[0] = 0;vector<int> cp(N+1, 1); cp[0] = 0;for(auto [p,k] : PK){ ck[k+1]--; cp[p+1]--; }rep(i,N) ck[i+1] += ck[i];rep(i,N) cp[i+1] += cp[i];if(N == M){ cout << Modint(nachia::Inversion(K)).val() << endl; return 0; }Modint q = 0;for(auto [p,k] : PK) q += Modint(cp[p]) * (ck[N] - ck[k]);for(auto [p,k] : PK) q += Modint(cp[N] - cp[p]) * (ck[k]);q /= (N-M);q += Modint(N-M) * Modint(N-M-1) / 4;q += nachia::Inversion(K);q *= f;cout << q.val() << endl;return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;