백준 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

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

사전 지식

imos법을 알면 풀이를 쉽게 이해할 수 있다. 이 포스트에서는 imos법을 알고 있다는 가정 하에 설명하도록 한다.

공차가 1인 등차 수열

이 문제는 공차가 1인 등차수열을 구간에 더하면서 포인트 쿼리를 수행한다.

 

여기서 포인트 쿼리를 구간 쿼리로 바꿔보자.

 

점 x에 떨어진 별의 개수가 아닌 구간 [1, x]의 합을 구하는 쿼리로 바꾼다.

 

왜 이렇게 쿼리를 바꾸냐면 쿼리 1을 스위핑 덧셈 문제로 바꾸기 위함이다.

 

얘를 들어 다음 배열을 살펴보자.

 

1

2

3

4

5

 

이 배열의 원소들 $a_{1}, a_{2},... $을 $imos(i) - imos(0)$의 형태로 구하려면 어떻게 할까?

 

1

1

1

1

1

-5

 

이렇게 배열을 구성하고 imos법으로 스위핑을 하면

 

1

2

3

4

5

0

 

이렇게 원본 배열이 복원되었음을 발견할 수 있다.

 

즉, 우리는 기존의 배열 대신 $a_{i} - a_{i - 1}$을 원소로 하여 스위핑을 하기 전의 배열 상태를 만들면 점 x에 떨어진 별의 개수는 구간 [0, x]의 합을 계산하여 얻을 수 있음을 알 수 있다.

Lazy propagation

그러면 문제에 말한 쿼리는 이렇게 바뀐다.

 

쿼리 1 : 구간 [L, R]에 1을 더한다. 그리고 점 R + 1에 R - L + 1을 뺀다.(imos법)

쿼리 2 : 구간 [L, R]의 합을 출력한다.

 

위의 쿼리는 lazy propagation으로 풀 수 있으므로 그렇게 풀면 간단히 정답을 받을 수 있다.

 

전체 코드

#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 ll = long long;
using pii = pair<int, int>;
 
int n, q;
int ar[100001];
int arr[100001];
 
template<typename T>
class lazy_segtree
{
public:
  vector<T> lazy, tree;
 
  lazy_segtree(int _n) : lazy(_n * 4), tree(_n * 4) {}
 
  T init(int node, int from, int to, int* _ar)
  {
    if (from == to) return tree[node] = _ar[to];
    int mid = (from + to) >> 1;
    return tree[node] = init(node << 1, from, mid, _ar) + init(node * 2 + 1, mid + 1, to, _ar);
  }
 
  void push(int node, int from, int to)
  {
    if (!lazy[node]) return;
    tree[node] += lazy[node] * (to - from + 1);
    if (from != to)
    {
      lazy[node << 1] += lazy[node];
      lazy[(node << 1) + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
 
  void add(int node, int from, int to, int l, int r, T val)
  {
    push(node, from, to);
    if (from > r or to < l) return;
    if (l <= from and to <= r)
    {
      lazy[node] += val;
      push(node, from, to);
      return;
    }
    int mid = (from + to) >> 1;
    add(node * 2, from, mid, l, r, val);
    add(node * 2 + 1, mid + 1, to, l, r, val);
    tree[node] = tree[node << 1] + tree[node * 2 + 1];
  }
 
  T sum(int node, int from, int to, int l, int r)
  {
    push(node, from, to);
    if (from > r or to < l) return 0;
    if (l<= from and to <= r) return tree[node];
    int mid = (from + to) >> 1;
    return sum(node << 1, from, mid, l, r) + sum(node * 2 + 1, mid + 1, to, l, r);
  }
};
 
void solve()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
    arr[i] = ar[i] - ar[i - 1];
  }
  lazy_segtree<ll> tree(n * 4);
  tree.init(1, 1, n, arr);
 
  cin >> q;
  while (q--)
  {
    int op, l, r;
    cin >> op >> l;
    if (op == 1)
    {
      cin >> r;
      tree.add(1, 1, n, l, r, 1);
      tree.add(1, 1, n, r + 1, r + 1, -(r - l + 1));
    }
    else
    {
      cout << tree.sum(1, 1, n, 1, l) << '\n';
    }
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록