結果

問題 No.1300 Sum of Inversions
ユーザー kenta255
提出日時 2020-11-27 22:33:36
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,356 ms / 2,000 ms
コード長 3,074 bytes
コンパイル時間 10,076 ms
コンパイル使用メモリ 280,068 KB
最終ジャッジ日時 2025-01-16 07:56:29
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
#define num_l(a,v) POSL(a,v) //v未満の要素数
#define num_eql(a,v) POSU(a,v) //v以下の要素数
#define num_h(a,v) (a.size() - POSU(a,v)) //vより大きい要素数
#define num_eqh(a,v) (a.size() - POSL(a,v)) //v以上の要素数


template <typename T>
class Seg_Tree{
public: // 0-index
	vector<T> dat;
	T initial,M;
	int n;
	T unite(T a,T b){//
		return ( a + b ) % M;
	}
	Seg_Tree(int n0_=1,T initial_=1,T M_=1){
		initsize(n0_,initial_,M_);
	}
	void initsize(int n0,T initial_,T M_){
		M = M_;
		initial = initial_;
		int k=1;
		while(1){
			if(n0<=k){
				n=k;
				dat.resize(2*n-1);
				for(int i=0;i<2*n-1;i++)dat[i]=initial;
				break;
			}
			k*=2;
		}
	}
 
	//i banme wo x nisuru
	void update(int i,T x){
		i += n-1;
		dat[i] = x;
		while(i>0){
			i = (i-1) / 2;
			dat[i] = unite(dat[i*2+1],dat[i*2+2]);
		}
	}
 
	//[a,b)
	T query0(int a,int b,int k,int l,int r){
		if(r<=a || b<=l)return initial;
		if(a<=l && r<=b)return dat[k];
		else{
			T vl = query0(a,b,k*2+1,l,(l+r)/2);
			T vr = query0(a,b,k*2+2,(l+r)/2,r);
			return unite(vl,vr);
		}
	}
 
	//return [a,b)
	T query(int a,int b){
		return query0(a,b,0,0,n);
	}
};


int main(){
	ll N;
	cin >> N;
	vector<ll> A(N);
	vector<P> B(N);
	FOR(i,0,N){
		cin >> A[i];
		B[i] = {A[i],i};
	}
	SORT(B);
	ll mod = 998244353;
	Seg_Tree<ll> sum0(N,0,mod),num0(N,0,mod);//small
	Seg_Tree<ll> sum1(N,0,mod),num1(N,0,mod);//big
	
	map<ll,ll> count;
	FOR(i,0,N){
		sum1.update(i,A[i]);
		num1.update(i,1);
		count[A[i]]++;
	}

	ll ans = 0;
	FOR(i,0,N){
		int k = count[ B[i].first ];
		FOR(j,i,i+k){
			sum1.update(B[j].second , 0);
			num1.update(B[j].second , 0);
		}
		FOR(j,i,i+k){
			ll num1_ = num1.query(0,B[j].second);
			ll num0_ = num0.query(B[j].second+1,N+1);
			( ans += (B[j].first * num1_ % mod * num0_) % mod ) %= mod;
			( ans += (sum1.query(0,B[j].second) * num0_) % mod ) %= mod;//右
			( ans += (sum0.query(B[j].second+1,N) * num1_) % mod ) %= mod;//左
		}	
		FOR(j,i,i+k){
			sum0.update(B[j].second , B[j].first);
			num0.update(B[j].second , 1);
		}
		count[B[i].first] = 0;
		i += k-1;
	}

	cout << ans << endl;

}
0