백준 17408 - 수열과 쿼리 24

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

 

값을 바꾸는 것은 극히 기본적인 세그먼트 트리의 연산이지만 구간 내 두 원소의 합 중 최댓값을 가져오는 연산이 쉽지 않을 수 있다.

 

다시 생각하면 구간 내 두 원소의 합 중 최댓값은 구간 내에서 가장 큰 값 2개를 가지고 있는 것과 동일하며 해당 쿼리는 구간 내에서 가장 큰 2개의 값을 보존하는 문제로 바뀐다.

 

가장 큰 2개의 값을 보관하기 위해 C++ 기준 pair를 관리하는 세그먼트 트리를 구성하자. 그러면 왼쪽 절반 L에서 가장 큰 두 값을 저장하는 pair와 오른쪽 절반 R에서 가장 큰 두 값을 저장하는 pair를 가지고 다음 그림처럼 구간을 갱신할 수 있다.

 

 

위 그림처럼 가장 큰 두 개의 값을 들고 다니면 된다. 아는 사람은 짐작할 수 있다시피 이 과정은 슬라이딩 윈도우로도 이해할 수 있다.

 

pair comp에서 target으로 슬라이딩을 하는 함수는 다음과 같이 짤 수 있다.

 

void shift(pii &comp, pii &target)
{
  if (comp.first >= target.second)
  {
    target.first = target.second;
    target.second = comp.first;
  }
  else if (comp.first > target.first)
  {
    target.first = comp.first;
  }

  if (comp.second >= target.second)
  {
    target.first = target.second;
    target.second = comp.second;
  }
  else if (comp.second > target.first)
  {
    target.first = comp.second;
  }
}

 

세그먼트 트리로 각 구간을 빠르게 슬라이딩하는 코드를 구현하면 정답을 받을 수 있다.

 

전체 코드 - update 연산을 할 때 tree[node]를 갱신하기 전 0으로 비워 오래된 찌꺼기 값을 제거해야 함을 유의하자.

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int ar[100001];
int n, q;
 
void shift(pii &comp, pii &target)
{
  if (comp.first >= target.second)
  {
    target.first = target.second;
    target.second = comp.first;
  }
  else if (comp.first > target.first)
  {
    target.first = comp.first;
  }
 
  if (comp.second >= target.second)
  {
    target.first = target.second;
    target.second = comp.second;
  }
  else if (comp.second > target.first)
  {
    target.first = comp.second;
  }
}
 
pii init(vector<pii> &tree, int node, int start, int end)
{
  if (start == end)
  {
    tree[node].second = ar[end];
    return tree[node];
  }
  int m = start + (end - start) / 2;
  pii left = init(tree, node * 2, start, m);
  pii right = init(tree, node * 2 + 1, m + 1, end);
  shift(left, tree[node]);
  shift(right, tree[node]);
  return tree[node];
}
 
void update(vector<pii> &tree, int node, int start, int end, int idx, int val)
{
  if (idx < start || end < idx) return;
  if (start == end)
  {
    tree[node].second = val;
    return;
  }
  int m = start + (end - start) / 2;
  update(tree, node * 2, start, m, idx, val);
  update(tree, node * 2 + 1, m + 1, end, idx, val);
  tree[node] = {};
  shift(tree[node * 2], tree[node]);
  shift(tree[node * 2 + 1], tree[node]);
}
 
pii query(vector<pii> &tree, int node, int start, int end, int l, int r)
{
  if (start > r || end < l) return {0, 0};
  if (l <= start && end <= r) return tree[node];
  int m = start + (end - start) / 2;
  pii pl = query(tree, node * 2, start, m, l, r);
  pii pr = query(tree, node * 2 + 1, m + 1, end, l, r);
  pii ret;
  shift(pl, ret);
  shift(pr, ret);
  return ret;
}
 
void solve()
{
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> ar[i];
  vector<pii> segtree(n * 4);
  init(segtree, 1, 1, n);
 
  cin >> q;
  while (q--)
  {
    int t, a, b;
    cin >> t >> a >> b;
 
    if (t == 1)
    {
      update(segtree, 1, 1, n, a, b);
    }
    else
    {
      pii res = query(segtree, 1, 1, n, a, b);
      cout << res.first + res.second << '\n';
    }
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
 
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

 

제출 기록

보너스 (884ms짜리 제출)

무식하게 멀티셋을 쓰는 방법도 있다. 어쨌든 통과한다.

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int ar[100001];
int n, q;
 
multiset<int> init(vector<multiset<int>> &tree, int node, int start, int end)
{
  if (start == end)
  {
    tree[node].insert(ar[end]);
    return tree[node];
  }
  int m = start + (end - start) / 2;
  auto l = init(tree, node * 2, start, m);
  auto r = init(tree, node * 2 + 1, m + 1, end);
  vector<int> tmp(l.size() + r.size());
  merge(l.begin(), l.end(), r.begin(), r.end(), tmp.begin());
  multiset<int> ret(tmp.begin(), tmp.end());
  while (ret.size() > 2)
  {
    ret.erase(ret.begin());
  }
  return tree[node] = ret;
}
 
void update(vector<multiset<int>> &tree, int node, int start, int end, int idx, int val)
{
  if (end < idx || idx < start) return;
  if (start == end)
  {
    tree[node].clear();
    tree[node].insert(val);
    return;
  }
  int m = start + (end - start) / 2;
  update(tree, node * 2, start, m, idx, val);
  update(tree, node * 2 + 1, m + 1, end, idx, val);
  auto l = tree[node * 2];
  auto r = tree[node * 2 + 1];
  tree[node].clear();
  for (auto x : l)
  {
    tree[node].insert(x);
    if (tree[node].size() > 2)
      tree[node].erase(tree[node].begin());
  }
  for (auto x : r)
  {
    tree[node].insert(x);
    if (tree[node].size() > 2)
      tree[node].erase(tree[node].begin());
  }
}
 
multiset<int> query(vector<multiset<int>> &tree, int node, int start, int end, int l, int r)
{
  if (end < l || start > r) return {};
  if (l <= start && end <= r) return tree[node];
  int m = start + (end - start) / 2;
  auto ls = query(tree, node * 2, start, m, l, r);
  auto rs = query(tree, node * 2 + 1, m + 1, end, l, r);
  vector<int> tmp(ls.size() + rs.size());
  merge(ls.begin(), ls.end(), rs.begin(), rs.end(), tmp.begin());
  multiset<int> ret(tmp.begin(), tmp.end());
  while (ret.size() > 2)
  {
    ret.erase(ret.begin());
  }
  return ret;
}
 
void solve()
{
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> ar[i];
  vector<multiset<int>> segtree(n * 4);
  init(segtree, 1, 1, n);
 
  cin >> q;
  while (q--)
  {
    int t, a, b;
    cin >> t >> a >> b;
 
    if (t == 1)
    {
      update(segtree, 1, 1, n, a, b);
    }
    else
    {
      auto res = query(segtree, 1, 1, n, a, b);
      cout << *res.rbegin() + *next(res.rbegin(), 1) << '\n';
    }
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
 
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}