백준 17955번 Max or Min

어제 처음으로 팀연습하다가 다이아 3을 풀어서 기쁜 마음에 풀이를 작성한다. 심지어 제출 한 번만에 맞췄다!

문제 요약

길이가 $N$인 원형 수열 $a$가 주어진다. $1 \le a_i \le M$ 이다.

이 때 다음과 같은 연산을 할 수 있다. $a_i$를 하나 골라서 인접한 두 수와 $a_i$의 최솟값 혹은 최댓값으로 $a_i$를 바꿔줄 수 있다.

이런 연산을 반복해서 수열 전체를 $k$로 만들기 위한 최소 연산 횟수를 계산해야 한다.

$3 \le N \le 2 \cdot 10^5, 1 \le M \le 10^5$

풀이

실제로 구해야 하는 것은 $1 \le k \le M$인 모든 $k$에 대한 답이지만 일단 이걸 $k$로 고정한 뒤에 최적의 연산 횟수를 구해보자.

일단 $k$가 존재하지 않는 수라면 아예 불가능하다.

그리고 $a_i$가 $k$와 인접해있지 않다면 k로 만드는 것이 불가능하다. 따라서 k와 인접한 수들부터 변경이 일어나야 할 것이다.

이를 통해서 수열이 양 끝이 $k$인 구간에 대해서 전체를 k로 만드는 과정의 최적의 연산횟수를 찾고 그러한 구간들의 연산 횟수를 전부 더해주면 전체를 k로 만드는 연산 횟수가 되는 것을 알 수 있다.

문제에서 예시로 준 수열을 2로 만들어야 한다면 [1, 3]과 [6, 6]을 2로 만드는 연산 횟수를 구하고 합쳐주면 그게 답이 된다.

이제 양 끝의 값이 k이며 중간에는 k가 없는 구간에서 구간 전체를 k로 만드는 문제를 해결해야 한다.

일단 구간의 길이가 L이라면 당연히 L-2번은 연산을 수행해야 한다. 위에서 말했듯이 k로 만들기 위해선 당연히 k와 인접해야 한다.

그리고 k가 최소 혹은 최대여야 한다. 여기서 k가 중간값이라면 추가적인 연산이 한번 더 든다.

예제의 {2, 5, 1, 1, 2}를 전부 2로 만들려면 5를 1로 만든 뒤에 1을 전부 2로 만들면 된다. 이를 통해서 결국 구간을 k로 만들 때 원소의 값이 중요하다기보단 원소의 값이 k보다 큰지 작은지라는 것을 알 수 있다. k보다 작은 원소는 -, 큰 원소는 +로 나타내자.

그러면 원소가 -에서 +로 바뀔때 추가 연산이 필요해진다는 것을 알 수 있다. 이게 얼마나 더 필요할까?

-든 +든 연속해서 있다면 딱 그만큼만 필요하게 된다. {-, +}일 때, {+, -}일 때는 1번 더 필요하게 된다. 그러면 번갈아 나오는 구간의 길이가 3이면 어떨까?

구간의 양상이 {k, -, +, -, k}라면 +를 -로 바꾸면 전부 -가 된다. {k, +, -, +, k}일 때도 -를 +로 바꾸면 전부 +가 된다.

그러면 번갈아 나오는 구간의 길이가 4일때는? 추가 연산이 두 번 필요하다. 5일 때는? 두 번이다. 이런 식으로 번갈아 나오는 구간의 길이가 $L$이라면 전체를 동일한 부호로 만드는 연산의 횟수는 $\lfloor \frac{L}{2} \rfloor$다.

이 때 중요한 것은 더 이상 확장이 불가능할 때까지 늘렸을 때의 구간이어야 한다.

{k, -, +, -, -, +, +, k}에서는 번갈아 나오는 구간이 3짜리와 2짜리가 있다. 따라서 총 연산 횟수는 6 + 1 + 1로 8이다.

그러면 이게 최적일까? 사실 팀연습 중에 푼거라 증명은 제대로 못하고 짰다. 하지만 최적일 거 같다.

더이상 확장이 불가능한 번갈아 나오는 구간을 전부 같은 부호로 바꾸는 작업은 나와 인접한 다른 구간의 끝과 부호가 같아진다는 뜻이다.

왜냐하면 더이상 확장이 불가능하려면 인접하는 두 구간의 끝 부호가 같아야 하기 때문이다. 그러면 양 끝에서부터 그러한 구간들을 전부 같은 부호로 바꿨다고 치자. 전부 k로 만드는 것은 딱 구간의 길이만큼 연산이 추가로 필요하다.

이런 방식으로 항상 저 횟수만큼 연산으로 전부 k로 만들 수 있다. 이걸로 k가 고정되었을 때의 문제를 O(N)에 해결할 수 있다.

이제 모든 k에 대해 구해보자. 원소의 값이 중요한게 아니라 우리가 만들 k와의 대소 관계가 중요하다고 했다.

그러면 k를 1부터 M까지 증가시켜간다고 했을 때 대소 관계는 2번만 변한다. 배열의 변경 횟수가 O(N)이라는 것이다. 원소의 값이 3이라면 k가 1, 2일 땐 3이 더 크고 k가 3일 땐 동일하고 k가 3보다 클 땐 작다.

세그트리로 관리하는것이 가능할 것처럼 생겨먹었다. 여기까진 팀연습하며 굉장히 빨리 왔었는데 어떤 세그를 만들어야 할지 안떠올랐다.

세그트리의 노드별로 이런 값들을 관리하면 값을 계산할 수 있다.

노드가 담당하고 있는 구간의 왼쪽에서 시작하면서 -로 시작하는 번갈아 나오는 구간의 길이, +로 시작하는 번갈아 나오는 구간의 길이, 오른쪽에서 시작하면서 -로 시작하는 번갈아 나오는 구간길이, +로 시작하는 번갈아 나오는 길이. 구간 내의 {-, +}의 갯수, 담당하고 있는 구간의 길이 중간에 위치하는 구간들이 답에 기여하는 값

이렇게 7개를 관리하면 답을 구할 수 있다. 원형 배열이다 보니까 배열 길이를 두배로 늘린 뒤에 구간을 적당히 잡아줄 필요가 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
  int sum, seg_sum;
  int l_minus, l_plus;
  int r_minus, r_plus;
  int len;
  Node() : sum(0), seg_sum(0), l_minus(0), l_plus(0), r_minus(0), r_plus(0), len(0) {};
  Node operator+(Node rhs) {
    Node ret;
    ret.sum = sum + rhs.sum;
    ret.seg_sum = seg_sum + rhs.seg_sum;
    ret.len = len + rhs.len;
    if(r_minus != len && rhs.l_plus != rhs.len) {
      ret.seg_sum += (r_minus + rhs.l_plus) / 2;
    }
    if(r_plus != len && rhs.l_minus != rhs.len) {
      ret.seg_sum += (r_plus + rhs.l_minus) / 2;
    }
    ret.l_minus = l_minus;
    if(l_minus == len) {
      if(len%2 == 0) ret.l_minus += rhs.l_minus;
      else ret.l_minus += rhs.l_plus;
    }
    ret.l_plus = l_plus;
    if(l_plus == len) {
      if(len%2 == 0) ret.l_plus += rhs.l_plus;
      else ret.l_plus += rhs.l_minus;
    }
    ret.r_minus = rhs.r_minus;
    if(rhs.r_minus == rhs.len) {
      if(rhs.len%2 == 0) ret.r_minus += r_minus;
      else ret.r_minus += r_plus;
    }
    ret.r_plus = rhs.r_plus;
    if(rhs.r_plus == rhs.len) {
      if(rhs.len%2 == 0) ret.r_plus += r_plus;
      else ret.r_plus += r_minus;
    }
    return ret;
  }
};

Node tree[1<<20];
vector<int> a(400005);
vector<vector<int>> idx(200005);
int N, M;

void update(int node, int s, int e, int idx, int val) {
  if(idx < s || idx > e) return ;
  if(s == idx && idx == e) {
    Node &tmp = tree[node];
    if(val == 0) {
      tmp.sum = 0;
      tmp.seg_sum = 0;
      tmp.l_minus = 0;
      tmp.l_plus = 0;
      tmp.r_minus = 0;
      tmp.r_plus = 0;
      tmp.len = 1;
    }
    else if(val > 0) {
      tmp.sum = 1;
      tmp.seg_sum = 0;
      tmp.l_minus = tmp.r_minus = 0;
      tmp.l_plus = tmp.r_plus = 1;
      tmp.len = 1;
    }
    else {
      tmp.sum = 1;
      tmp.seg_sum = 0;
      tmp.l_minus = tmp.r_minus = 1;
      tmp.l_plus = tmp.r_plus = 0;
      tmp.len = 1;
    }
    return ;
  }
  int mid = (s+e) >> 1;
  int n1 = node << 1, n2 = node << 1 | 1;
  update(n1, s, mid, idx, val);
  update(n2, mid+1, e, idx, val);
  tree[node] = tree[n1] + tree[n2];
}

Node query(int node, int s, int e, int l, int r) {
  if(e < l || s > r) return Node();
  if(l <= s && e <= r) return tree[node];
  int mid = (s+e) >> 1;
  int n1 = node << 1, n2 = node << 1 | 1;
  Node t1 = query(n1, s, mid, l, r);
  Node t2 = query(n2, mid+1, e, l, r);
  Node t = t1 + t2;
  return t;
}

void init_tree(int node, int s, int e) {
  if(s == e) {
    int val = a[s] != 1;
    Node &tmp = tree[node];
    if(val == 0) {
      tmp.sum = 0;
      tmp.seg_sum = 0;
      tmp.l_minus = 0;
      tmp.l_plus = 0;
      tmp.r_minus = 0;
      tmp.r_plus = 0;
      tmp.len = 1;
    }
    else if(val > 0) {
      tmp.sum = 1;
      tmp.seg_sum = 0;
      tmp.l_minus = tmp.r_minus = 0;
      tmp.l_plus = tmp.r_plus = 1;
      tmp.len = 1;
    }
    else {
      tmp.sum = 1;
      tmp.seg_sum = 0;
      tmp.l_minus = tmp.r_minus = 1;
      tmp.l_plus = tmp.r_plus = 0;
      tmp.len = 1;
    }
    return ;
  }
  int mid = (s+e)>>1;
  int n1 = node << 1, n2 = node << 1 | 1;
  init_tree(n1, s, mid);
  init_tree(n2, mid+1, e);
  tree[node] = tree[n1] + tree[n2];
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  cin >> N >> M;
  for(int i=1;i<=N;++i) {
    cin >> a[i];
    a[N+i] = a[i];
  }
  for(int i=1;i<=2*N;++i) idx[a[i]].push_back(i);
  init_tree(1, 1, 2*N);
  vector<int> ans(M+1);
  for(int i=1;i<=M;++i) {
    if(idx[i].empty()) ans[i] = -1;
    else {
      int l = idx[i].front();
      int r = l + N;
      auto tmp = query(1, 1, 2*N, l, r);
      ans[i] = tmp.sum + tmp.seg_sum;
    }
    for(int x:idx[i]) update(1, 1, 2*N, x, -1);
    for(int x:idx[i+1]) update(1, 1, 2*N, x, 0);
  }
  for(int i=1;i<=M;++i) cout << ans[i] << " \n"[i==M];
  return 0;
}