提出 #72781837

---

ソースコード 拡げる

/**
 *    author:  MOAZ_KING
 *    created: 26.01.2026 22:15:10
**/
#include <bits/stdc++.h>
using namespace std;
struct Node {
  int64_t sum;
  Node() { sum = 0; }
  Node(int64_t x) { sum = x; }
  void operator=(const Node other) { sum = other.sum; }
};
template <typename T, typename U, class fun = function<T(const T &, const T &)>>
struct SegmentTree {
  int n;
  vector<T> tree;
  fun merge;
  int left(int node) { return 2 * node + 1; }
  int right(int node) { return 2 * node + 2; }
  void update(int idx, U val) { update(0, 0, n - 1, idx, val); }
  T query(int l, int r) { return query(0, 0, n - 1, l, r); }
  SegmentTree() { }
  SegmentTree(const vector<U> &v, const fun &f) : merge(f) { build(v); }
  void build(const vector<U> &v) {
    n = v.size();
    int sz = 1;
    while (sz < n) {
      sz <<= 1;
    }
    tree.resize(2 * sz, T());
    build(0, 0, n - 1, v);
  }
  void build(int node, int l, int r, const vector<U> &v) {
    if (l == r) {
      tree[node] = T(v[l]);
      return;
    }
    int m = l + r >> 1;
    build(left(node), l, m, v);
    build(right(node), m + 1, r, v);
    tree[node] = merge(tree[left(node)], tree[right(node)]);
  }
  void update(int node, int l, int r, int idx, U &val) {
    if (l == r) {
      tree[node].sum += val;
      return;
    }
    int m = l + r >> 1;
    if (idx <= m) {
      update(left(node), l, m, idx, val);
    } else {
      update(right(node), m + 1, r, idx, val);
    }
    tree[node] = merge(tree[left(node)], tree[right(node)]);
  }
  T query(int node, int l, int r, int lx, int rx) {
    if (l >= lx && r <= rx) {
      return tree[node];
    }
    int m = l + r >> 1;
    T l_ans = lx <= m ? query(left(node), l, m, lx, rx) : Node();
    T r_ans = rx > m ? query(right(node), m + 1, r, lx, rx) : Node();
    return merge(l_ans, r_ans);
  }
};
Node merge_q(const Node &a, const Node &b) {
  return Node(a.sum + b.sum);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> v(n);
  for (int &i : v) {
    cin >> i;
  }
  auto tmp(v);
  sort(tmp.begin(), tmp.end());
  for (int i = 0; i < n; i++) {
    v[i] = lower_bound(tmp.begin(), tmp.end(), v[i]) - tmp.begin();
  }
  vector<int> x(n);
  SegmentTree<Node, int> seg_cnt(x, merge_q);
  SegmentTree<Node, int> seg_sum(x, merge_q);
  int64_t ans = 0;
  for (int i = 0; i < n; i++) {
    if (v[i]) {
      ans += seg_cnt.query(0, v[i] - 1).sum * tmp[v[i]] - seg_sum.query(0, v[i] - 1).sum;
    }
    seg_cnt.update(v[i], 1);
    seg_sum.update(v[i], tmp[v[i]]);
  }
  cout << ans << '\n';
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In instantiation of 'T SegmentTree<T, U, fun>::query(int, int, int, int, int) [with T = Node; U = int; fun = std::function<Node(const Node&, const Node&)>]':
./Main.cpp:21:39:   required from 'T SegmentTree<T, U, fun>::query(int, int) [with T = Node; U = int; fun = std::function<Node(const Node&, const Node&)>]'
   21 |   T query(int l, int r) { return query(0, 0, n - 1, l, r); }
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~
./Main.cpp:89:27:   required from here
   89 |       ans += seg_cnt.query(0, v[i] - 1).sum * tmp[v[i]] - seg_sum.query(0, v[i] - 1).sum;
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~
./Main.cpp:58:23: warning: implicitly-declared 'constexpr Node::Node(const Node&)' is deprecated [-Wdeprecated-copy]
   58 |       return tree[node];
      |                       ^
./Main.cpp:11:8: note: because 'Node' has user-provided 'void Node::operator=(Node)'
   11 |   void operator=(const Node other) { sum = other.sum; }
      |        ^~~~~~~~
./Main.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int m = l + r >> 1;
      |             ~~^~~
./Main.cpp: In instantiation of 'void SegmentTree<T, U, fun>::update(int, int, int, int, U&) [with T = Node; U = int; fun = std::function<Node(const Node&, const Node&)>]':
./Main.cpp:20:39:   required from 'void SegmentTree<T, U, fun>::update(int, U) [with T = Node; U = int; fun = std::function<Node(const Node&, const Node&)>]'
   20 |   void update(int idx, U val) { update(0, 0, n - 1, idx, val); }
      |                                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:91:19:   required from here
   91 |     seg_cnt.update(v[i], 1);
      |     ~~~~~~~~~~~~~~^~~~~~~~~
./Main.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int m = l + r >> 1;
      |             ~~^~~
./Main.cpp: In instantiation of 'void SegmentTree<T, U, fun>::build(int, int, int, const std::vector<_ValT>&) [with T = Node; U = int; fun = std::function<Node(const Node&, const Node&)>]':
./Main.cpp:31:10:   required from 'void SegmentTree<T, U, fun>::build(const std::vector<_ValT>&) [with T = Node; U = int; fun = std::function<Node(const Node&, const Node&)>]'
   31 |     build(0, 0, n - 1, v);
      |     ~~~~~^~~~~~~~~~~~~~~~
./Main.cpp:23:67:   required from 'SegmentTree<T, U, fun>::SegmentTree(const std::vector<_ValT>&, const fun&) [with T = Node; U = int; fun = std::function<Node(const Node&, const Node&)>]'
   23 |   SegmentTree(const vector<U> &v, const fun &f) : merge(f) { build(v); }
      |                                                              ~~~~~^~~
./Main.cpp:84:44:   required from here
   84 |   SegmentTree<Node, int> seg_cnt(x, merge_q);
      |                                            ^
./Main.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int m = l + r >> 1;
      |             ~~^~~

ジャッジ結果