結果
問題 | No.2327 Inversion Sum |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:32:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 6,323 bytes |
コンパイル時間 | 4,887 ms |
コンパイル使用メモリ | 269,432 KB |
最終ジャッジ日時 | 2025-02-13 13:32:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
/* author: kyawa */#include<bits/stdc++.h>using namespace std;/*考察*/#include<atcoder/all>using mint = atcoder::modint998244353;class WaveletMatrix{using i64 = int64_t;public:explicit WaveletMatrix() = default;WaveletMatrix(vector<i64> &_v){ __WaveletMatrix(_v);};i64 range_freq(i64 L, i64 R, i64 lower, i64 upper){ return __range_freq(L, R, upper) - __range_freq(L, R, lower);}i64 range_Kthmin(i64 L, i64 R, i64 K){ return __range_Kthmin_assignXOR(L, R, K, 0);}i64 range_Kthmax(i64 L, i64 R, i64 K){ return __range_Kthmin_assignXOR(L, R, R - L - K - 1, 0);}i64 range_successor(i64 L, i64 R, i64 value){ i64 C = __range_freq(L, R, value + 1); return C == R - L ? -1 : __range_Kthmin_assignXOR(L, R, C, 0);}i64 range_predecessor(i64 L, i64 R, i64 value){ i64 C = __range_freq(L, R, value); return C == 0 ? -1 : __range_Kthmin_assignXOR(L, R, C - 1, 0);}i64 range_min_assignXOR(i64 L, i64 R, i64 value){ return __range_Kthmin_assignXOR(L, R, 0, value);}i64 range_max_assignXOR(i64 L, i64 R, i64 value){ return __range_Kthmin_assignXOR(L, R, R - L - 1, value);}i64 range_Kthmin_assignXOR(i64 L, i64 R, i64 K, i64 value){ return __range_Kthmin_assignXOR(L, R, K, value);}i64 range_Kthmax_assignXOR(i64 L, i64 R, i64 K, i64 value){ return __range_Kthmin_assignXOR(L, R, R - L - K - 1, value);}private:vector<i64> Matrix;i64 bitsize;i64 prefixsize;void __WaveletMatrix(vector<i64> v){i64 v_max = *max_element(v.begin(), v.end()) + 1;bitsize = 64 - __builtin_clzll(v_max);prefixsize = v.size()+1;Matrix.resize(prefixsize * bitsize);for(i64 h = bitsize - 1; h >= 0; h--){for(i64 i = 0; i < v.size(); i++){Matrix[i+1 + prefixsize * h] = Matrix[i + prefixsize * h] + (v[i] >> h & 1);}stable_sort(v.begin(), v.end(), [&](auto a, auto b){ return (a >> h & 1) < (b >> h & 1);});}};i64 __range_freq(i64 L, i64 R, i64 upper){if(upper >= ((i64)1 << bitsize)) return R - L;if(upper < 0) return 0;i64 res = 0;for(i64 h = bitsize - 1; h >= 0; h--){auto [L0, R0, L1, R1] = decomp(L, R, h);if(upper & ((i64)1 << h)){res += R0 - L0;tie(L, R) = {L1, R1};}else{tie(L, R) = {L0, R0};}}return res;};i64 __range_Kthmin_assignXOR(i64 L, i64 R, i64 K, i64 value){i64 res = 0;for(i64 h = bitsize - 1; h >= 0; h--){auto [L0, R0, L1, R1] = decomp(L, R, h);if(value & ((i64)1 << h)){swap(L0, L1); swap(R0, R1);}if(K < R0 - L0){tie(L, R) = {L0, R0};}else{K -= (R0 - L0);res |= (i64)1 << h;tie(L, R) = {L1, R1};}}return res;}tuple<i64,i64,i64,i64> decomp(i64 L, i64 R, i64 h){return tuple<i64,i64,i64,i64>({L - Matrix[L + prefixsize * h],R - Matrix[R + prefixsize * h],prefixsize - 1 - Matrix[prefixsize * (h+1) - 1] + Matrix[L + prefixsize * h],prefixsize - 1 - Matrix[prefixsize * (h+1) - 1] + Matrix[R + prefixsize * h]});}};int64_t inversion(vector<int64_t> &v){if(v.empty()) return 0;vector<int64_t> st = v;sort(st.begin(), st.end());st.erase(unique(st.begin(), st.end()), st.end());vector<int64_t> table(st.size()+1);for(auto e : v){int64_t a = st.size() + (st.begin() - lower_bound(st.begin(), st.end(), e)), b = a - 1;for(;a < table.size(); a += (a & -a)) ++table[a];for(;b > 0; b -= (b & -b)) table[0] += table[b];}return table[0];}template<class S, S (*op)(S, S), S (*e)()>class SegmentTree{public:vector<S> table;int64_t size = 1;SegmentTree(vector<S> vec){while(size < vec.size()) size <<= 1;table.resize(size << 1, e());for(int64_t i = 0; i < (int64_t)vec.size(); i++) table[i + size] = vec[i];for(int64_t i = size - 1; i >= 1; i--) table[i] = op(table[i<<1|0],table[i<<1|1]);}SegmentTree(int64_t siz){while(size < siz) size <<= 1;table.resize(size << 1, e());for(int64_t i = 0; i < siz; i++) table[i + size] = e();for(int64_t i = size - 1; i >= 1; i--) table[i] = op(table[i<<1|0],table[i<<1|1]);}S fold(int64_t l, int64_t r){l += size; r += size;S Lres = e(), Rres = e();while(l < r){if(l & 1) Lres = op(Lres, table[l++]);if(r & 1) Rres = op(table[--r], Rres);l >>= 1; r >>= 1;}return op(Lres, Rres);}void set(int64_t p, S x){p += size;table[p] = x;while(p >>= 1) table[p] = op(table[p<<1|0],table[p<<1|1]);}};int64_t op(int64_t a, int64_t b){return a+b;}int64_t e(){return 0;}int main(){mint res;int64_t N, M; cin >> N >> M;vector<int64_t> P(N, INT64_MAX/4);vector<int64_t> Pinv(N, -1);for(int64_t i = 0; i < M; i++){int64_t p, k; cin >> p >> k; p--; k--;P[k] = p;Pinv[p] = k;}WaveletMatrix wm(P);vector<int64_t> fixed;vector<int64_t> free;for(int64_t i = 0; i < N; i++) if(P[i] != INT64_MAX/4) fixed.push_back(P[i]);for(int64_t i = 0; i < N; i++) if(Pinv[i] == -1) free.push_back(i);res += (N - M) * (N - M - 1) / 2;res += inversion(fixed) * 2;for(int64_t i = 3; i <= N-M; i++) res *= i;if(fixed.size() == 0 or free.size() == 0){cout << res.val() << '\n';return 0;}WaveletMatrix wmf(free);mint pres = 0;SegmentTree<int64_t, op, e> seg(N);for(int64_t i = 0; i < N; i++){if(P[i] == INT64_MAX/4) seg.set(i, 0);else seg.set(i, wm.range_freq(i+1, N, INT64_MAX/4, INT64_MAX/4+1));}for(int64_t i = 0; i < N; i++){if(Pinv[i] == -1){pres += seg.fold(0, N);}else{seg.set(Pinv[i], N - M - seg.fold(Pinv[i], Pinv[i]+1));}}for(int64_t i = 2; i <= (N-M-1); i++) pres *= i;res += pres;cout << res.val() << '\n';}