526互联

【每日一题】Problem 443B. Kuriyama Mirai's Stones

发布时间 2023-06-26 23:19:07作者: HelloEricy

原题

解决思路

  1. 两个数组，一个未排序，一个排序；
  2. 使用前缀和的方式减少时间复杂度
#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int n; std::cin >> n;
  std::vector<int> v(n + 1, 0);
  for (int i = 1; i <= n; ++i) std::cin >> v[i];
  std::vector<int> u(v);
  std::sort(u.begin() + 1, u.end());

  std::vector<long long> vsum(n + 1, 0), usum(n + 1, 0);
  for (int i = 1; i <= n; ++i) {
    vsum[i] += vsum[i - 1] + v[i];
    usum[i] += usum[i - 1] + u[i];
  }
  
  int m; std::cin >> m;
  for (int i = 0; i < m; ++i) {
    int type, l, r;
    std::cin >> type >> l >> r;
    if (type == 1) {
      std::cout << vsum[r] - vsum[l - 1] << std::endl;
    } else {
      std::cout << usum[r] - usum[l - 1] << std::endl;
    }
  }
  return 0;
}