結果

問題 No.1300 Sum of Inversions
ユーザー GGanari
提出日時 2024-05-24 11:13:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 852 ms / 2,000 ms
コード長 3,048 bytes
コンパイル時間 2,679 ms
コンパイル使用メモリ 211,804 KB
最終ジャッジ日時 2025-02-21 16:35:12
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define INF 1000000001LL
#define MOD 998244353LL
#define long long long
#define all(x) x.begin(),x.end()
using namespace std;

struct Node
{
    long value = 0;
};
class SegTree
{
private:
    vector<Node> arr;
    vector<Node> tree;
    int n;
    Node trash = {0}; //의미없는 값 입력
    Node merge(Node a, Node b)
    {
        //여기를 커스텀 구현
        Node res;
        res.value = (a.value+b.value)%MOD;
        return res;
    }
    Node init(int node, int start, int end)
    {
        if(start == end)
            return tree[node] = arr[start];
        int mid = (start+end)/2;
        return tree[node] = merge(init(node*2,start,mid),init(node*2+1,mid+1,end));
    }
    Node query(int node, int start, int end, int left, int right)
    {
        if(start > right || end < left)
            return trash;
        if(start >= left && end <= right)
            return tree[node];
        
        int mid = (start+end)/2;
        return merge(query(node*2,start,mid,left,right),query(node*2+1,mid+1,end,left,right));
    }
    Node update(int node, int start, int end, int index, long l)
    {
        if(start > index || end < index)
            return tree[node];
        if(start == end)
		{
            tree[node].value+=l;
			return tree[node];
		}
        int mid = (start+end)/2;
        return tree[node]=merge(update(node*2,start,mid,index,l),update(node*2+1,mid+1,end,index,l));
    }
public:
    void init(int l)
    {
        n = l;
        arr = vector<Node>(n);
        tree = vector<Node>(4*n);
    }
    void init(vector<Node> a)
    {
        n = a.size();
        arr = a;
        tree = vector<Node>(4*n);
        init(1,0,n-1);
    }
    void init(vector<long> a)
    {
        n = a.size();
        arr = vector<Node>(n);
        for(int i = 0; i<n; i++)
            arr[i].value = a[i];
        tree = vector<Node>(4*n);
        init(1,0,n-1);
    }
    long query(int left, int right)
    {
		if(left > right)
			return 0;
        return query(1,0,n-1,left,right).value%MOD;
    }
    void update(int index, long val)
    {
        update(1,0,n-1,index,val);
    }
};
int main()
{
	ios_base::sync_with_stdio(0); 
    cin.tie(0);

	int n;
	cin >> n;
	vector<int> arr(n);
	vector<int> sortArr(n);

	for(int i = 0; i<n; i++)
	{
		cin >> arr[i];
		sortArr[i] = arr[i];
	}
	sort(all(sortArr));

	SegTree hapL;
	hapL.init(n);
	SegTree cntL;
	cntL.init(n);
	SegTree hapR;
	hapR.init(n);
	SegTree cntR;
	cntR.init(n);

	for(int i = 0; i<n; i++)
	{
		int v = lower_bound(all(sortArr),arr[i])-sortArr.begin();
		hapR.update(v,arr[i]);
		cntR.update(v,1);
	}
	long res = 0;
	for(int i = 0; i<n; i++)
	{
		int v = lower_bound(all(sortArr),arr[i])-sortArr.begin();
		hapR.update(v,-arr[i]);
		cntR.update(v,-1);
		long l = (hapL.query(v+1,n-1)*cntR.query(0,v-1))%MOD;
		long r = hapR.query(0,v-1)*cntL.query(v+1,n-1)%MOD;
		res+=l+r+(cntR.query(0,v-1)*cntL.query(v+1,n-1)%MOD)*arr[i];
		res%=MOD;
		cntL.update(v,1);
		hapL.update(v,arr[i]);
	}
	cout << res << endl;


	
    return 0;
}
0