結果
| 問題 |
No.1300 Sum of Inversions
|
| コンテスト | |
| ユーザー |
 T1610
|
| 提出日時 | 2020-11-30 15:25:00 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,995 ms / 2,000 ms |
| コード長 | 6,571 bytes |
| コンパイル時間 | 10,651 ms |
| コンパイル使用メモリ | 281,680 KB |
| 最終ジャッジ日時 | 2025-01-16 10:24:55 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}
#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << " "
#define dumpL(x) cout << #x << " : " << x << '\n'
#define LINE cout << "line : " << __LINE__ << " "
#define LINEL cout << "line : " << __LINE__ << '\n'
#define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << " "
#define dumpVL(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl
#define STOP assert(false)
#else
#define dump(x)
#define dumpL(x)
#define LINE
#define LINEL
#define dumpV(v)
#define dumpVL(v)
#define STOP assert(false)
#endif
#define mp make_pair
namespace std {
template<class S, class T>
ostream &operator <<(ostream& out, const pair<S, T>& a) {
out << '(' << a.fi << ", " << a.se << ')';
return out;
}
}
template<typename T>
tuple<map<T, int>, vector<T>> zaatu(const vector<vector<T>>& v) {
map<T, int> mp;
for(auto&& u: v) for(auto&& x: u) mp[x] = 0;
vector<T> r;
for(auto& p: mp) {
p.second = r.size();
r.emplace_back(p.first);
}
return {mp, r};
}
template <typename T, typename U> T pow_fast(T x, U n) {
T ret = (T)1;
while(n) {
if(n & (U)1) ret *= x;
x *= x;
n >>= 1;
}
return ret;
}
template <typename ModType, ModType MOD> struct ModInt {
ModType val;
ModInt() : val(0) {}
ModInt(ModType x) : val(x % MOD) {
if(val < 0) val += MOD;
};
operator ModType() const { return val; }
ModInt &operator+=(const ModInt &m) {
val += m.val;
if(val >= MOD) val -= MOD;
return *this;
}
ModInt &operator-=(const ModInt &m) {
val -= m.val;
if(val < 0) val += MOD;
return *this;
}
ModInt &operator*=(const ModInt &m) {
(val *= m.val) %= MOD;
return *this;
}
ModInt &operator/=(const ModInt &m) {
*this *= m.inverse();
return *this;
}
ModInt operator+(const ModInt &m) const { return ModInt(*this) += m; }
ModInt operator-(const ModInt &m) const { return ModInt(*this) -= m; }
ModInt operator*(const ModInt &m) const { return ModInt(*this) *= m; }
ModInt operator/(const ModInt &m) const { return ModInt(*this) /= m; }
ModInt inverse() const { return pow_fast(*this, MOD - 2); }
ModInt pow(ModType n) const {return pow_fast(*this, n); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &rhs) {
os << rhs.val;
return os;
}
friend std::istream &operator>>(std::istream &is, ModInt &rhs) {
ModType value;
is >> value;
rhs = ModInt(value);
return is;
}
};
using mint = ModInt<ll, 998244353LL>;
using ull = unsigned long long;
template <typename T>
struct Node {
static inline const T initVal = 0; //TODO: fix type and value
static inline const T initLazy = 0; //TODO: fix type and value
T val;
T lazy;
ull l, r;
Node<T>* l_node = nullptr;
Node<T>* r_node = nullptr;
Node(ull l, ull r, const T& val = initVal) : l(l), r(r), val(val), lazy(initLazy) {}
T getVal() {
return val + lazy * T(r - l); //TODO: fix
}
T f1(const T& a, const T& b) {
return a+b; //TODO: fix
}
T f2(const T& a, const T& b) {
return a+b; //TODO: fix
}
void push() {
if(r - l > 1) {
auto m = (l+r)/2;
{
if(l_node == nullptr) l_node = new Node(l, m);
if(lazy != initLazy) l_node->lazy = f2(l_node->lazy, this->lazy);
}
{
if(r_node == nullptr) r_node = new Node(m, r);
if(lazy != initLazy) r_node->lazy = f2(r_node->lazy, this->lazy);
}
}
val = getVal();
lazy = initLazy;
}
void fix() {
if(r - l == 1) return;
val = f1(l_node->getVal(), r_node->getVal());
}
T query(ull qL, ull qR) {
if(qR <= l || r <= qL) return initVal;
if(qL <= l && r <= qR) return getVal();
if(r - l == 1) return getVal();
push();
T l_val = l_node->query(qL, qR), r_val = r_node->query(qL, qR);
return f1(l_val, r_val);
}
void update(ull uL, ull uR, const T& uVal) {
if(uR <= l || r <= uL) return;
if(uL <= l && r <= uR) lazy = f2(lazy, uVal);
else {
push();
l_node->update(uL, uR, uVal);
r_node->update(uL, uR, uVal);
fix();
}
}
};
template <typename T>
struct DynamicLazySegTree {
Node<T> root;
DynamicLazySegTree(ull l, ull r, const T& val) : root(l, r, val) {}
DynamicLazySegTree(ull r): root(0, r) {}
T query(ull l, ull r) {
return root.query(l, r);
}
void update(ull l, ull r, const T& val) {
root.update(l, r, val);
}
void output() {
auto l = root.l;
auto r = root.r;
REP(i, l, r) {
cout << " " << query(i, i+1);
}
cout << '\n';
}
};
int main(){
int n;
cin >> n;
vl a(n);
rep(i, n) cin >> a[i];
vector<vl> aa(1, a);
auto [mp, v] = zaatu(aa);
DynamicLazySegTree<mint> seg1(n+10), seg2(n+10);
DynamicLazySegTree<ll> cnt1(n+10), cnt2(n+10);
mint ans = 0;
repr(i, n) {
int cur = mp[a[i]];
// dump(i);dump(cur);dumpL(a[i]);
seg1.update(cur, cur+1, a[i]);
cnt1.update(cur, cur+1, 1);
if(cur > 0) {
seg2.update(cur, cur+1, seg1.query(0, cur)+mint(cnt1.query(0, cur))*mint(a[i]));
cnt2.update(cur, cur+1, cnt1.query(0, cur));
}
if(cur > 0) {
// auto tmp = seg2.query(0, cur) + mint(cnt2.query(0, cur) * a[i]);
// dumpL(tmp);
ans += seg2.query(0, cur) + mint(cnt2.query(0, cur)) * mint(a[i]);
}
// seg1.output();
// cnt1.output();
// seg2.output();
// cnt2.output();
}
cout << ans << '\n';
return 0;
}