結果
| 問題 |
No.1733 Sum of Sorted Subarrays
|
| コンテスト | |
| ユーザー |
 tokusakurai
|
| 提出日時 | 2021-10-20 15:31:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 661 ms / 3,000 ms |
| コード長 | 10,675 bytes |
| コンパイル時間 | 2,529 ms |
| コンパイル使用メモリ | 208,472 KB |
| 最終ジャッジ日時 | 2025-01-25 01:59:39 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, x, n) for (int i = x; i <= n; i++)
#define rep3(i, x, n) for (int i = x; i >= n; i--)
#define each(e, v) for (auto &e : v)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
template <typename T>
bool chmax(T &x, const T &y) {
return (x < y) ? (x = y, true) : false;
}
template <typename T>
bool chmin(T &x, const T &y) {
return (x > y) ? (x = y, true) : false;
}
template <typename T>
int flg(T x, int i) {
return (x >> i) & 1;
}
template <typename T>
void print(const vector<T> &v, T x = 0) {
int n = v.size();
for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
}
template <typename T>
void printn(const vector<T> &v, T x = 0) {
int n = v.size();
for (int i = 0; i < n; i++) cout << v[i] + x << '\n';
}
template <typename T>
int lb(const vector<T> &v, T x) {
return lower_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, T x) {
return upper_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
void rearrange(vector<T> &v) {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
}
template <typename T>
vector<int> id_sort(const vector<T> &v, bool greater = false) {
int n = v.size();
vector<int> ret(n);
iota(begin(ret), end(ret), 0);
sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });
return ret;
}
struct io_setup {
io_setup() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << fixed << setprecision(15);
}
} io_setup;
const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
// const int MOD = 1000000007;
const int MOD = 998244353;
template <int mod>
struct Mod_Int {
int x;
Mod_Int() : x(0) {}
Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
static int get_mod() { return mod; }
Mod_Int &operator+=(const Mod_Int &p) {
if ((x += p.x) >= mod) x -= mod;
return *this;
}
Mod_Int &operator-=(const Mod_Int &p) {
if ((x += mod - p.x) >= mod) x -= mod;
return *this;
}
Mod_Int &operator*=(const Mod_Int &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
Mod_Int &operator/=(const Mod_Int &p) {
*this *= p.inverse();
return *this;
}
Mod_Int &operator++() { return *this += Mod_Int(1); }
Mod_Int operator++(int) {
Mod_Int tmp = *this;
++*this;
return tmp;
}
Mod_Int &operator--() { return *this -= Mod_Int(1); }
Mod_Int operator--(int) {
Mod_Int tmp = *this;
--*this;
return tmp;
}
Mod_Int operator-() const { return Mod_Int(-x); }
Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; }
Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; }
Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; }
Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; }
bool operator==(const Mod_Int &p) const { return x == p.x; }
bool operator!=(const Mod_Int &p) const { return x != p.x; }
Mod_Int inverse() const {
assert(*this != Mod_Int(0));
return pow(mod - 2);
}
Mod_Int pow(long long k) const {
Mod_Int now = *this, ret = 1;
for (; k > 0; k >>= 1, now *= now) {
if (k & 1) ret *= now;
}
return ret;
}
friend ostream &operator<<(ostream &os, const Mod_Int &p) { return os << p.x; }
friend istream &operator>>(istream &is, Mod_Int &p) {
long long a;
is >> a;
p = Mod_Int<mod>(a);
return is;
}
};
using mint = Mod_Int<MOD>;
template <typename Monoid, typename Operator_Monoid>
struct Lazy_Segment_Tree {
using F = function<Monoid(Monoid, Monoid)>;
using G = function<Monoid(Monoid, Operator_Monoid)>;
using H = function<Operator_Monoid(Operator_Monoid, Operator_Monoid)>;
int n, height;
vector<Monoid> seg;
vector<Operator_Monoid> lazy;
const F f;
const G g;
const H h;
const Monoid e1;
const Operator_Monoid e2;
// f(f(a,b),c) = f(a,f(b,c)), f(e1,a) = f(a,e1) = a
// h(h(p,q),r) = h(p,h(q,r)), h(e2,p) = h(p,e2) = p
// g(f(a,b),p) = f(g(a,p),g(b,p))
// g(g(a,p),q) = g(a,h(p,q))
Lazy_Segment_Tree(const vector<Monoid> &v, const F &f, const G &g, const H &h, const Monoid &e1, const Operator_Monoid &e2) : f(f), g(g), h(h), e1(e1), e2(e2) {
int m = v.size();
n = 1, height = 0;
while (n < m) n <<= 1, height++;
seg.assign(2 * n, e1), lazy.assign(2 * n, e2);
copy(begin(v), end(v), seg.begin() + n);
for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
}
Lazy_Segment_Tree(int m, const Monoid &x, const F &f, const G &g, const H &h, const Monoid &e1, const Operator_Monoid &e2) : f(f), g(g), h(h), e1(e1), e2(e2) {
n = 1, height = 0;
while (n < m) n <<= 1, height++;
seg.assign(2 * n, e1), lazy.assign(2 * n, e2);
vector<Monoid> v(m, x);
copy(begin(v), end(v), seg.begin() + n);
for (int i = n - 1; i > 0; i--) seg[i] = f(seg[2 * i], seg[2 * i + 1]);
}
inline Monoid reflect(int i) const { return (lazy[i] == e2 ? seg[i] : g(seg[i], lazy[i])); }
inline void recalc(int i) {
while (i >>= 1) seg[i] = f(reflect(2 * i), reflect(2 * i + 1));
}
inline void eval(int i) {
if (i < n && lazy[i] != e2) {
lazy[2 * i] = h(lazy[2 * i], lazy[i]);
lazy[2 * i + 1] = h(lazy[2 * i + 1], lazy[i]);
seg[i] = reflect(i), lazy[i] = e2;
}
}
inline void thrust(int i) {
for (int j = height; j > 0; j--) eval(i >> j);
}
void apply(int l, int r, const Operator_Monoid &x) {
l = max(l, 0), r = min(r, n);
if (l >= r) return;
l += n, r += n;
thrust(l), thrust(r - 1);
int a = l, b = r;
while (l < r) {
if (l & 1) lazy[l] = h(lazy[l], x), l++;
if (r & 1) r--, lazy[r] = h(lazy[r], x);
l >>= 1, r >>= 1;
}
recalc(a), recalc(b - 1);
}
Monoid query(int l, int r) {
l = max(l, 0), r = min(r, n);
if (l >= r) return e1;
l += n, r += n;
thrust(l), thrust(r - 1);
Monoid L = e1, R = e1;
while (l < r) {
if (l & 1) L = f(L, reflect(l++));
if (r & 1) R = f(reflect(--r), R);
l >>= 1, r >>= 1;
}
return f(L, R);
}
Monoid operator[](int i) { return query(i, i + 1); }
template <typename C>
int find_subtree(int i, const C &check, const Monoid &x, Monoid &M, bool type) {
while (i < n) {
eval(i);
Monoid nxt = type ? f(reflect(2 * i + type), M) : f(M, reflect(2 * i + type));
if (check(nxt, x)) {
i = 2 * i + type;
} else {
M = nxt, i = 2 * i + (type ^ 1);
}
}
return i - n;
}
template <typename C>
int find_first(int l, const C &check, const Monoid &x) { // check((区間[l,r]での演算結果), x)を満たす最小のr
Monoid L = e1;
int a = l + n, b = n + n;
thrust(a);
while (a < b) {
if (a & 1) {
Monoid nxt = f(L, reflect(a));
if (check(nxt, x)) return find_subtree(a, check, x, L, false);
L = nxt, a++;
}
a >>= 1, b >>= 1;
}
return n;
}
template <typename C>
int find_last(int r, const C &check, const Monoid &x) { // check((区間[l,r)での演算結果), x)を満たす最大のl
Monoid R = e1;
int a = n, b = r + n;
thrust(b - 1);
while (a < b) {
if (b & 1 || a == 1) {
Monoid nxt = f(reflect(--b), R);
if (check(nxt, x)) return find_subtree(b, check, x, R, true);
R = nxt;
}
a >>= 1, b >>= 1;
}
return -1;
}
};
template <typename T>
struct Binary_Indexed_Tree {
vector<T> bit;
const int n;
Binary_Indexed_Tree(const vector<T> &v) : n((int)v.size()) {
bit.resize(n + 1);
copy(begin(v), end(v), begin(bit) + 1);
for (int a = 2; a <= n; a <<= 1) {
for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2];
}
}
Binary_Indexed_Tree(int n, const T &x) : n(n) {
bit.resize(n + 1);
vector<T> v(n, x);
copy(begin(v), end(v), begin(bit) + 1);
for (int a = 2; a <= n; a <<= 1) {
for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2];
}
}
void add(int i, const T &x) {
for (i++; i <= n; i += (i & -i)) bit[i] += x;
}
void change(int i, const T &x) { add(i, x - query(i, i + 1)); }
T sum(int i) const {
T ret = 0;
for (; i > 0; i -= (i & -i)) ret += bit[i];
return ret;
}
T query(int l, int r) const { return sum(r) - sum(l); }
T operator[](int i) const { return query(i, i + 1); }
int lower_bound(T x) const {
int ret = 0;
for (int k = 31 - __builtin_clz(n); k >= 0; k--) {
if (ret + (1 << k) <= n && bit[ret + (1 << k)] < x) x -= bit[ret += (1 << k)];
}
return ret;
}
int upper_bound(T x) const {
int ret = 0;
for (int k = 31 - __builtin_clz(n); k >= 0; k--) {
if (ret + (1 << k) <= n && bit[ret + (1 << k)] <= x) x -= bit[ret += (1 << k)];
}
return ret;
}
};
int main() {
int N;
cin >> N;
vector<int> A(N);
rep(i, N) cin >> A[i];
vector<int> v = id_sort(A);
auto f = [](mint a, mint b) { return a + b; };
auto g = [](mint a, mint b) { return a * b; };
auto h = [](mint a, mint b) { return a * b; };
Lazy_Segment_Tree<mint, mint> seg1(N, 1, f, g, h, 0, 1), seg2(N, 1, f, g, h, 0, 1);
vector<mint> ipw(N + 1, 1);
mint tw = mint(2).inverse();
rep(i, N) ipw[i + 1] = ipw[i] * tw;
mint ans = 0;
rep(i, N) {
int e = v[i];
ans += seg1.query(e, N) * seg2.query(0, e + 1) * ipw[i] * A[e];
seg1.apply(e, N, 2), seg2.apply(0, e + 1, 2);
}
cout << ans << '\n';
}