結果

問題 No.1300 Sum of Inversions
コンテスト
ユーザー Izayoi_R_sakura
提出日時 2020-11-27 22:19:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,214 ms / 2,000 ms
コード長 4,658 bytes
コンパイル時間 1,853 ms
コンパイル使用メモリ 144,168 KB
最終ジャッジ日時 2025-01-16 07:42:34
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <math.h>
#include <random>
#include <chrono>
using namespace std ;
using ll = long long ;
using ld = long double ;
template<class T> using V = vector<T> ;
template<class T> using VV = V<V<T>> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
ll mod = 998244353 ;
long double pie = acos(-1) ;
ll INF = 1000000000000 ;

void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
void fix_cout(){cout << fixed << setprecision(20) ;}
template<class T> void chmax(T &a,T &b){if(a<b) a = b ;}
template<class T> void chmin(T &a,T &b){if(a>b) a = b ;}

template<class T>
class SGT{
    public :
    int n ;
    vector<T> num ;
    function<T(T,T)> f ;
    T d ;

    // コンストラクタ：サイズ、関数、単位元を指定
    SGT(size_t n_,function<T(T,T)> f_,T d_) : f(f_),d(d_){
        n = 1 ;
        while(n<n_) n *= 2 ;
        num = vector<T>(2*n-1,d) ;
    }

    // sz個のaで前から初期化
    void init(int sz,T a){
        for(int i=0;i<sz;i++) num[i+n-1] = a ;
        for(int i=n-2;i>=0;i--) num[i] = f(num[i*2+1],num[i*2+1]) ;
    }

    // 配列aで前から初期化
    void init(vector<T> &a){
        for(int i=0;i<a.size();i++) num[i+n-1] = a[i] ;
        for(int i=n-2;i>=0;i--) num[i] = f(num[i*2+1],num[i*2+2]) ;
    }

    // 0-indexedでp番目をaで上書き
    void update(int p,T a){
        p += n-1 ;
        num[p] = a ;
        while(p){
            p = (p-1)/2 ;
            num[p] = f(num[p*2+1],num[p*2+2]) ;
        }
    }

    // 0-indexedでp番目にaを加算
    void add(int p,T a){
        p += n-1 ;
        num[p] += a ;
        while(p){
            p = (p-1)/2 ;
            num[p] = f(num[p*2+1],num[p*2+2]) ;
        }        
    }
    
    T query(int a,int b,int cur=0,int l=0,int r=-1){
        if(r<0) r = n ;
        if(r<=a||b<=l) return d ;
        if(a<=l&&r<=b) return num[cur] ;
        T r1 = query(a,b,cur*2+1,l,(l+r)/2) ;
        T r2 = query(a,b,cur*2+2,(l+r)/2,r) ;
        return f(r1,r2) ;
    }

    T operator[](int p){
        return num[p+n-1] ;
    }

    int bsr(int a,int b,T x,function<bool(T,T)> check,int l=0,int r=-1,int cur=0){
        if(r<0) r = n ;
        cout << l << " " << r << " " << cur << endl ;
        if(!check(num[cur],x)||r<=a||b<=l) return a-1 ;
        if(cur>=n-1) return cur-(n-1) ;
        int right = bsr(a,b,x,check,(l+r)/2,r,cur*2+2) ;
        if(right==a-1){
            return bsr(a,b,x,check,l,(l+r)/2,cur*2+1) ;
        }else{
            return right ;
        }
    }

    int bsl(int a,int b,T x,function<bool(T,T)> check,int l=0,int r=-1,int cur=0){
        if(r<0) r = n ;
        if(!check(num[cur],x)||r<=a||b<=l) return b ;
        if(cur>=n-1) return cur-(n-1) ;
        int left = bsl(a,b,x,check,l,(l+r)/2,cur*2+1) ;
        if(left==b){
            return bsl(a,b,x,check,(l+r)/2,r,cur*2+2) ;
        }else{
            return left ;
        }
    }
} ;

int main(){
	int n ; cin >> n ;
	V<ll> a(n) ;
	map<ll,int> pos ;
	for(int i=0;i<n;i++){
		cin >> a[i] ;
		pos[a[i]]++ ;
	}
	int  cnt = 0 ;
	for(auto &p:pos){
		p.second = cnt ;
		cnt++ ;
	}
	// for(auto p:pos){
	// 	cout << p.first << " " << p.second << endl ;
	// }
	SGT<ll> mx(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	SGT<ll> mn(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	SGT<ll> s1(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	SGT<ll> s2(pos.size(),[](ll a,ll b){return a+b ;},0) ;
	V<ll> cnt1(n,0),cnt2(n,0),cnt3(n,0),cnt4(n,0) ;
	for(int i=0;i<n;i++){
		cnt1[i] = mx.query(pos[a[i]]+1,mx.n) ;
		mx.add(pos[a[i]],1) ;
	}
	for(int i=n-1;i>=0;i--){
		cnt2[i] = mn.query(0,pos[a[i]]) ;
		mn.add(pos[a[i]],1) ;
	}
	for(int i=0;i<n;i++){
		cnt3[i] = s1.query(pos[a[i]]+1,s1.n) ;
		s1.add(pos[a[i]],cnt1[i]) ;
	}
	for(int i=n-1;i>=0;i--){
		cnt4[i] = s2.query(0,pos[a[i]]) ;
		s2.add(pos[a[i]],cnt2[i]) ;
	}
	ll ans = 0 ;
	for(int i=0;i<n;i++){
		ans += a[i]%mod*((cnt1[i]*cnt2[i]%mod+cnt3[i]+cnt4[i])%mod)%mod ;
		ans %= mod ;
		// cout << ans << endl ;
	}
	cout << ans << endl ;
	// for(auto i:cnt1) cout << i << " " ; cout << endl ;
	// for(auto i:cnt2) cout << i << " " ; cout << endl ;
	// for(auto i:cnt3) cout << i << " " ; cout << endl ;
	// for(auto i:cnt4) cout << i << " " ; cout << endl ;
}
0