結果

問題 No.2327 Inversion Sum
ユーザー kyawa
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/* 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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0