백준 16978 - 수열과 쿼리 22

https://www.acmicpc.net/problem/16978

힌트

x번째 원소 갱신을 하기 전 x - 1번째 원소 갱신을 한 세그먼트 트리의 구간합을 구할 수 있다.

 

각 쿼리를 보존하여 적절한 시기에 처리하도록 한다.

---

풀이

특정 시점까지 갱신이 적용되었을 때의 구간 합을 구하는 문제이다.

 

조금만 생각해보면 구간 합은 원소의 갱신에 미치는 영향이 없다는 사실을 깨달을 수 있다.

 

그렇다면 0번째 원소 갱신을 수행 후 구간 합 연산 -> 1번째 원소 갱신 수행 -> 1번째 원소 갱신을 수행 후 구간 합 연산 -> 2번째 원소 갱신 수행 ->... 이처럼 계산하면 질의마다 올바른 값을 얻을 수 있다.

 

그런데 어떻게 구현해야 될까?

 

세그먼트 트리를 초기화만 해주고 입력받는 쿼리들에 대해 바로 계산하지 않고 보존하도록 한다.

 

원소 갱신 쿼리를 보관하는 배열과 구간 합 쿼리를 보관하는 배열에 각각 넣어주면 된다.

 

구간 합 쿼리를 보관할 때는 다음 2차원 선형 자료구조를 이용하는 것이 적당할 것이다.

 

query_sum[x] := x번째 원소 갱신이 끝난 다음 구간 합을 구하는 쿼리를 모은 벡터

 

이때 해당 쿼리의 번호(index)도 같이 보관하도록 한다.

 

이러면 구간 합 -> 갱신 -> 구간 합 -> 갱신... 과정을 배열 순회로 구현할 수 있게 된다.

 

query_sum을 순회하면서 현재 index에 해당하는(index번째 원소까지 갱신했을 경우) 구간 합을 구해 쿼리 번호와 함께 정답을 모아두는 벡터에 넣도록 한다.

 

현재 index의 구간 합을 모두 구했으면 index + 1번째 원소 갱신을 수행한다.

 

그다음 index + 1에 해당하는 구간 합을 모두 구한다... 이를 반복하면 모든 구간 합 쿼리의 결과를 얻을 수 있다.

 

마지막으로 정답을 모은 벡터를 쿼리 번호를 기준으로 정렬하여 순서를 복원한 후 차례로 답을 출력하면 된다.

 

이렇게 입력으로 들어오는 쿼리에 대해 바로 반응하지 않고 전처리를 거친 후 계산하는 것을 오프라인 쿼리라고 부른다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;

vector<vector<int>> discreate_sum[100001];
vector<pii> discreate_query;
vector<pil> res;
int ar[1000001];
int n, q;

inline int mid(int s, int e) { return s + (e - s) / 2; }

ll init(vector<ll> &tree, int node, int start, int end)
{
  if (start == end) return tree[node] = ar[end];
  int m = mid(start, end);
  return tree[node] = init(tree, node * 2, start, m) + init(tree, node * 2 + 1, m + 1, end);
}

void update(vector<ll> &tree, int node, int start, int end, int idx, ll diff)
{
  if (start > idx || end < idx) return;
  tree[node] += diff;
  if (start != end)
  {
    int m = mid(start, end);
    update(tree, node * 2, start, m, idx, diff);
    update(tree, node * 2 + 1, m + 1, end, idx, diff);
  }
}

ll sum(vector<ll> &tree, int node, int start, int end, int l, int r)
{
  if (start > r || end < l) return 0;
  if (l <= start && end <= r) return tree[node];
  int m = mid(start, end);
  return sum(tree, node * 2, start, m, l, r) + sum(tree, node * 2 + 1, m + 1, end, l, r);
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  cin >> n;

  for (int i = 1; i <= n; ++i)
    cin >> ar[i];
  vector<ll> segtree(n * 4);
  init(segtree, 1, 1, n);
  
  cin >> q;

  for (int i = 0; i < q; ++i)
  {
    int a, b, c, d;
    cin >> a;

    if (a == 1)
    {
      cin >> b >> c;
      discreate_query.push_back({b, c});
    }
    else
    {
      cin >> b >> c >> d;
      discreate_sum[b].push_back({c, d, i});
    }
  }

  for (int i = 0; i <= q; ++i)
  {
    for (int j = 0; j < discreate_sum[i].size(); ++j)
    {
      res.push_back({discreate_sum[i][j][2], sum(segtree, 1, 1, n, discreate_sum[i][j][0], discreate_sum[i][j][1])});
    }

    if (i >= discreate_query.size())
      continue;
    ll diff = discreate_query[i].second - ar[discreate_query[i].first];
    update(segtree, 1, 1, n, discreate_query[i].first, diff);
    ar[discreate_query[i].first] = discreate_query[i].second;
  }

  sort(res.begin(), res.end());

  for (int i = 0; i < res.size(); ++i)
    cout << res[i].second << '\n';
}

제출 기록