結果

問題 No.1300 Sum of Inversions
ユーザー kkktymkkktym
提出日時 2020-11-27 22:48:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 693 ms / 2,000 ms
コード長 5,748 bytes
コンパイル時間 1,652 ms
コンパイル使用メモリ 122,420 KB
最終ジャッジ日時 2025-01-16 08:08:46
ジャッジサーバーID
(参考情報)
judge5 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <limits>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
template<class T> inline int sz(T &a) { return a.size(); }
using ll = long long; using ld = long double;
using pi = pair<int,int>; using pl = pair<ll,ll>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
const int inf = numeric_limits<int>::max();
const ll infll = numeric_limits<ll>::max();
// Modint
// modint<MOD>
template<ll MOD>
struct modint{
ll x;
ll mod = MOD;
modint(ll x=0):x(x%MOD){}
modint& operator+=(const modint a){
if((x+=a.x)>=MOD) x-=MOD;
return *this;
}
modint& operator-=(const modint a){
if((x += MOD-a.x)>=MOD) x-=MOD;
return *this;
}
modint& operator*=(const modint a){
(x*=a.x)%=MOD;
return *this;
}
modint operator+(const modint a) const{
modint res(*this);
return res+=a;
}
modint operator-(const modint a) const{
modint res(*this);
return res-=a;
}
modint operator*(const modint a) const{
modint res(*this);
return res*=a;
}
modint pow(ll t) const{
if(!t) return 1;
modint a = pow(t>>1);
a*=a;
if(t&1) a*=*this;
return a;
}
//for prime mod
modint inv() const{
return pow(MOD-2);
}
modint& operator/=(const modint a){
return (*this) *= a.inv();
}
modint operator/(const modint a) const{
modint res(*this);
return res/=a;
}
};
using mint = modint<998244353>;
//----------------------------
//
// 使
///********************************
// auto f = [&](int a,int b){ return a+b;}; // :
// int id = 0; //:0
// SegTree<decltype(f),int> seg(f,id);
//************************************
//----------------------------
template <typename F,typename T>
struct SegTree{
// merge,identify
T identity;
F merge;
int size;
vector<T> dat;
// fid
SegTree(F f,T id):merge(f),identity(id){}
// nsizen2
void init(int n){
size = 1;
while(size<=n) size *= 2;
dat.assign(size*2-1,identity);
}
// 0(n)
void build(vector<T> vec){
rep(i,vec.size()) dat[size-1+i] = vec[i];
dfs(0);
}
T dfs(int k){
if(k>=size-1) return dat[k];
else return dat[k] = merge(dfs(2*k+1),dfs(2*k+2));
}
// index ka
void update(int k,T a){
k += size - 1;
dat[k] = a;
while(k > 0){
k = (k-1)/2;
dat[k] = merge(dat[2*k+1],dat[2*k+2]);
}
}
// index ka
void add(int k,T a){
k += size - 1;
dat[k] += a;
while(k > 0){
k = (k-1)/2;
dat[k] = merge(dat[2*k+1],dat[2*k+2]);
}
}
// [a,b)(k,l,r)=(0,0,size)
T query(int a,int b,int k,int l,int r){
if(r<=a||b<=l) return identity;
if(a<=l&&r<=b) return dat[k];
else return merge(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
}
T query(int a,int b){
return query(a, b, 0, 0, size);
}
//
void show(){
int index = 0;
int num = 1;
while(index<size){
rep(i,num){
if(dat[i+index]==identity) cout << "e ";
else cout << dat[i+index] << " ";
}
cout << "\n";
num *= 2;
index = index*2+1;
}
}
};
// .
//
template <typename T>
class Compress{
public:
vector<T> a; //
vector<int> data; //
map<T, int> mp; // key->, val->
void add(T val) {
a.emplace_back(val);
}
void build() {
vector<T> vals = a;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
rep(i,sz(a)) {
int id = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
// id + 11-indexed
mp[a[i]] = id;
data.push_back(id);
}
}
int a2data(T val) {
return mp.lower_bound(val)->second;
}
void test() {
vector<T> v = {3, 3, 1, 6, 1};
for(auto val: v) add(val);
build();
for(auto val: data) cout << val << " ";
cout << "\n";
// 1 1 0 2 0
cout << a2data(2) << "\n";
// 1
}
};
int main()
{
auto f = [&](mint a,mint b){ return a+b;}; // :
mint id(0); //:0
SegTree<decltype(f),mint> seg(f,id), seg2(f,id);
int n; cin >> n;
vl a(n);
rep(i,n) cin >> a[i];
Compress<ll> cp;
rep(i,n) {
cp.add(a[i]);
}
cp.build();
seg.init(n);
seg2.init(n);
vector<mint> cntl(n),cntr(n),suml(n),sumr(n);
rep(i,n) {
cntl[i] = seg.query(cp.data[i]+1, n);
seg.add(cp.data[i], mint(1));
suml[i] = seg2.query(cp.data[i]+1, n);
seg2.add(cp.data[i], a[i]);
}
seg.init(n);
seg2.init(n);
for (int i = n-1; i >= 0; --i) {
cntr[i] = seg.query(0, cp.data[i]);
seg.add(cp.data[i], mint(1));
sumr[i] = seg2.query(0, cp.data[i]);
seg2.add(cp.data[i], a[i]);
}
mint res;
rep(i,n) {
res += suml[i] * cntr[i];
res += sumr[i] * cntl[i];
res += mint(a[i]) * cntr[i] * cntl[i];
}
cout << res.x << "\n";
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0