BOJ 19651. 수열과 쿼리 39

19651번: 수열과 쿼리 39 (acmicpc.net)

solved.ac: Diamond V (2024.09.06)

 

나이브하게 처리하는 것은 상당히 노답이므로, 문제를 변형시킬 필요가 있습니다.

등차수열에서 주로 사용되는 성질로 A[i-1] + A[i+1] = 2A[i]를 이용합시다.

 

새로운 배열을 생각해서 B[i] = A[i-1] + A[i+1] - 2A[i]이라 하면,

세 수 A[i-1], A[i], A[i+1]가 등차수열을 이룰 시 B[i] = 0이 됩니다.

따라서 쿼리의 답은 (연속해서 0인 B[i]의 개수) + 2가 됩니다. 이는 금광세그 트릭을 이용하면 구할 수 있습니다.

 

업데이트의 경우 세 수가 모두 포함되거나 포함되지 않을 경우 변화량은 없으므로,

쿼리 [s, e]에 대해 B[s - 1], B[s], B[e], B[e + 1]만 업데이트됩니다.

 

자세한 풀이는 코드를 참고해 주세요.

#include <iostream>
#include <vector>

using namespace std;
typedef long long int LL;

/*
B[i] = A[i-1] + A[i+1] - 2A[i]로 정의하면, (연속한 0의 개수 + 2)를 구하는 문제로 바뀐다.
구간 [s, e]에 (x + nd)를 더한다고 해 보자.

B[s - 1] = A[s - 2] + A[s] - 2A[s - 1]에서, 변화량은 x이다.
B[s] = A[s - 1] + A[s + 1] - 2A[s]에서, 변화량은 d - x이다.

B[e] = A[e - 1] + A[e + 1] - 2A[e]에서, 변화량은 (s - e - 1)d - x이다.
B[e + 1] = A[e] + A[e + 2] - 2A[e + 1]에서, 변화량은 (e - s)d + x이다.
*/

/* 연속한 0의 개수 관리: 금광 세그 */
struct seg
{
bool all;
int lmax, rmax, mx, sz;
};

LL arr[400001];
seg tree[400001];

seg merge(seg &l, seg &r)
{
  seg res;
  res.all = l.all && r.all;
  res.lmax = (l.all ? l.sz + r.lmax : l.lmax);
  res.rmax = (r.all ? l.rmax + r.sz : r.rmax);
  res.mx = max(max(l.mx, r.mx), l.rmax + r.lmax);
  res.sz = l.sz + r.sz;
  return res;
}

void update(int node, int s, int e, int idx, int val)
{
  if(idx < s || e < idx) return;
  if(s == e) // update
  {
    arr[node] += val;
    tree[node].sz = 1;
    
    if(arr[node] == 0)
    {
      tree[node].lmax = 1; tree[node].rmax = 1; 
      tree[node].mx = 1;   tree[node].all = true;
    }
    else
    {
      tree[node].lmax = 0; tree[node].rmax = 0;
      tree[node].mx = 0;   tree[node].all = false;
    }
    return;
  }

  int m = (s + e) / 2;
  update(node * 2, s, m, idx, val);
  update(node * 2 + 1, m + 1, e, idx, val);

  tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

seg query(int node, int s, int e, int l, int r)
{
  if(r < s || e < l) return {true, 0, 0, 0, 0};
  if(l <= s && e <= r) return tree[node];

  int m = (s + e) / 2;
  seg left = query(node * 2, s, m, l, r);
  seg right = query(node * 2 + 1, m + 1, e, l, r);
  return merge(left, right);
}

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

  int n;
  cin >> n;

  vector<int> init(n + 1);
  for(int i = 1; i <= n; i++) cin >> init[i];
  for(int i = 2; i < n; i++) update(1, 1, n, i, init[i - 1] + init[i + 1] - 2 * init[i]);

  int Q;
  cin >> Q;
  while(Q--)
    {
      int op;
      cin >> op;

      if(op == 1)
      {
        int s, e, x, d;
        cin >> s >> e >> x >> d;

        update(1, 1, n, s - 1, x);
        update(1, 1, n, s, d - x);
        update(1, 1, n, e, (s - e - 1) * d - x);
        update(1, 1, n, e + 1, (e - s) * d + x);
      }
      else
      {
        int l, r;
        cin >> l >> r;
        cout << query(1, 1, n, l + 1, r - 1).mx + 2 << '\n';
      }
    }
}