#874610 (C++17) No.2327 Inversion Sum

• 問題: No.2327 Inversion Sum
• ユーザー: 👑 Nachia
• 提出日時: 2023-05-28 14:56:05
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 19 ms / 2,000 ms
• コード長: 4,890 bytes
• コンパイル時間: 1,050 ms
• コンパイル使用メモリ: 90,356 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-08 06:30:31
• 合計ジャッジ時間: 2,195 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 5,248 KB
testcase_01	AC	16 ms; 5,376 KB
testcase_02	AC	11 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	18 ms; 5,376 KB
testcase_05	AC	4 ms; 5,376 KB
testcase_06	AC	13 ms; 5,376 KB
testcase_07	AC	8 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	AC	16 ms; 5,376 KB
testcase_10	AC	6 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	11 ms; 5,376 KB
testcase_15	AC	19 ms; 5,376 KB
testcase_16	AC	7 ms; 5,376 KB
testcase_17	AC	3 ms; 5,376 KB
testcase_18	AC	4 ms; 5,376 KB
testcase_19	AC	6 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB
testcase_29	AC	2 ms; 5,376 KB
testcase_30	AC	2 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	2 ms; 5,376 KB

ソースコード

#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 enough
long 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;