imos법 imos method いもす法

이 게시글에서는 imos법에 대해 배우고 관련 문제를 푼다.

imos법이란?

이름의 유래는 작성자도 잘 알지 못하지만 일본에서 온 것으로 추정된다.

 

imos법은 다음과 같은 형태를 가진 문제를 풀 때 사용할 수 있다.

N차원 직교 좌표계에서 특정 범위(구간)에 x를 더하기

 

위와 같은 쿼리가 연속으로 주어질 때 imos법을 사용하면 일부 좌표를 마킹하여 d차원일 때 $O(N^{d})$의 시간 복잡도로 공간을 채울 수 있다.

선분에서의 imos법

특정 구간에 1을 더하길 원한다고 해보자.

 

imos법은 구간이 시작되는 점에 1을 더하고 구간을 벗어나는 가장 첫 번째 점에 1을 뺀 뒤 이 사이를 누적합으로 더해가며 스위핑 한다.

 

위에서 말한 대로 스위핑을 하면 해당 구간에 1을 더한 결과를 얻을 수 있다.

 

1부터 5까지 1을 더하는 예시를 보도록 하자.

 

1

0

0

0

0

-1

 

범위가 1 이상 5 이하이므로 구간의 시작인 1에 1을 더하고 구간을 벗어나는 첫 번째 점인 6에 1을 뺀 상태이다.

 

2부터 6까지 $ar[i] = ar[i] + ar[i - 1]$을 해가며 스위핑을 해보자.

 

1

1

1

1

1

0

 

보다시피 1~5 범위의 구간이 모두 1로 채워진 것을 확인할 수 있다.

 

구간을 더하는 쿼리만 있을 때 imos법을 사용하면 구간에 1을 더하는 쿼리가 몇 개, 아니 몇천만 개가 들어오던지 간에 $O(N)$으로 해결할 수 있는 강력한 알고리즘이다.

 

imos법을 사용해서 푸는 문제를 하나 살펴보자.

 

https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_c

C - Lamps

 

전구의 초기 intensity가 주어지는데 이렇게 해서 밝혀진 각 칸의 밝기가 동일한 위치에 있는 전구의 다음 intensity가 된다고 한다.

 

이를 K번 반복한 후 각 전구의 intensity를 구해야 한다.

 

이 문제는 전구 하나에 대해 위 시뮬레이션을 하다 보면 대략 $\log K$번 시행했을 때 모든 칸이 도달할 수 있는 최대 intensity로 채워진다는 발견을 해야 한다.

 

이를 발견하면 나머지는 imos법으로 시뮬레이션을 돌려가며 $\log K$번 이상 시행했을 때 모든 칸이 최대 밝기로 채워져 있으면 시뮬레이션을 중단하는 방법으로 시간 안에 해결을 할 수 있다.

 

imos법의 구현에 관해서는 위 문제에서 AC를 받은 소스를 참고하라.

 

C - Lamps

#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>;

int ar[200000];
int b[200000];
int n, k;

void solve()
{
  cin >> n >> k;

  for (int i = 0; i < n; ++i)
    cin >> ar[i];
  
  for (int i = 0; i < k; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      int l = max(0, j - ar[j]);
      int r = min(n - 1, j + ar[j]);

      ++b[l];
      if (r + 1 < n)
        --b[r + 1];
    }

    for (int j = 1; j < n; ++j)
      b[j] += b[j - 1];
    
    copy(b, b + n, ar);
    memset(b, 0, sizeof b);
    if (i > log2(k) && equal(ar + 1, ar + n, ar))
      break;
  }

  for (int i = 0; i < n; ++i)
    cout << ar[i] << ' ';
}

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

 

전구가 밝히는 범위를 적절히 지정하여 imos법을 시행하고 있다.

좌표의 범위가 클 때의 적용

그렇다면 좌표가 $10^{9}$ 이상의 값을 가질 수 있다면 어떻게 될까?

 

https://atcoder.jp/contests/abc221/tasks/abc221_d

D - Online games

 

이 문제는 N이 적당히 작다면 바로 배열에서 imos법을 시행할 수 있지만 각 범위의 길이가 최대 10억이라 이를 배열에 표현하기에는 무리가 있다.

 

이럴 때는 각 변화가 일어나는 좌표와 그 차분을 pair 묶은 후 벡터에 넣고 정렬하여 관리할 수 있다.

 

그 뒤 반복문으로 각 pair를 살펴볼 때마다 차분을 반영하여 i번째 구간에 몇 명이 존재하는지 알 수 있으며 $length = sweep(i + 1, first) - sweep(i, first)$로 구간의 길이를 알 수 있다.

 

문제에서는 1명부터 N명까지 동시 접속한 날을 각각 구하는 것이므로 ans[현재 구간에 존재하는 사람]에 구간의 길이를 더해나가면서 풀 수 있다.

 

보다 자세한 구현은 아래 링크를 참조하자.

 

https://atcoder.jp/contests/abc221/submissions/26323040

Submission #26323040 - AtCoder Beginner Contest 221

imos법으로 2차원 직교 좌표계에서 사각형 채우기

물론 imos법은 2차원 도형을 채울 때도 그 위력을 발휘한다.

 

이번엔 2차원 좌표계에서 사각형을 채우는 법을 알아보자.

 

3*3 사각형을 완성하고자 할 때는 다음과 같이 수를 채워야 한다.

 

1			-1
-1			1

 

모든 행에 대해 오른쪽으로 스위핑을 하면

 

1	1	1	0
-1	-1	-1	0

 

그다음 모든 열에 대해 아래쪽으로 스위핑을 하면

 

1	1	1	0
1	1	1
1	1	1
0	0	0	0

 

이렇게 $O(N^{2})$로 사각형을 완성할 수 있다.

imos법으로 2차원 좌표계에서 직각삼각형 채우기

물론 직각삼각형을 채우는 것 또한 가능하다. 너비가 3이고 높이가 3인 직각삼각형을 만들길 원한다고 해보자.

1
1	1
1	1	1

 

직각삼각형의 경우에는 다음과 같이 6개의 좌표를 변화시켜야 한다.

 

1	-1
-1				1
	1			-1

 

모든 행에 대해 오른쪽으로 스위핑을 하면

 

1	0
-1	-1	-1	-1	0
	1	1	1	0

 

모든 열에 대해 아래쪽으로 스위핑을 하면

 

1	0
1
1
0	-1	-1	-1	0
	0	0	0	0

 

마지막으로 남동쪽 대각선 방향으로 스위핑을 하면

 

1	0
1	1
1	1	1
0	0	0	0	0
	0	0	0	0

 

이렇게 직각삼각형이 완성된다. 좌우 반전한 형태에 대해서는 남서쪽 대각선으로 스위핑을 하면 될 것이다.

 

백준 저지에서 정사각형 imos법을 할 수 있는 연습 문제를 제공하니 풀어보자.

 

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

25826번: 2차원 배열 다중 업데이트 단일 합

직교 좌표계가 아닌 좌표계에서의 imos법

특정한 쿼리에 대해 시간 단축을 기대할 수 있는 것 외에도 imos법의 장점은 직교 좌표계가 아닌 좌표계에서도 적용이 가능하다는 것이다.

 

특정 구간에서의 누적합과 스위핑이 가능한 조건이기만 하면 imos법을 적용시킬 수 있다.

 

다음 문제를 봐보자.

 

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

5541번: 釘 (Nails)

 

삼각형 모양을 한 좌표계에서 삼각형들의 세 꼭짓점 정보가 M개 주어질 때 삼각형들로 덮은 영역을 구하는 문제이다.

 

잘 보면 문제에서 만들어진 삼각형은 바로 위에서 다룬 직각삼각형을 채우는 방법과 완전히 동일한 방법으로 imos법을 시행할 수 있음을 발견할 수 있다.

 

주어지는 쿼리에 대해 적절한 좌표에 1을 더하거나 빼고 imos법을 시행하면 $O(N^{2})$의 시간 복잡도로 해결할 수 있다.

 

Nails

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

#include <bits/stdc++.h>

using namespace std;

int n, m;
int ar[5005][5005];
int ans;

void solve()
{
  cin >> n >> m;

  for (int i = 0; i < m; ++i)
  {
    int a, b, c;
    cin >> a >> b >> c;
    ++ar[a][b];
    --ar[a][b + 1];
    --ar[a + c + 1][b];
    ++ar[a + c + 2][b + 1];
    ++ar[a + c + 1][b + c + 2];
    --ar[a + c + 2][b + c + 2];
  }

  for (int i = 0; i < 5005; ++i)
    for (int j = 1; j < 5005; ++j)
      ar[i][j] += ar[i][j - 1];
  for (int i = 0; i < 5005; ++i)
    for (int j = 1; j < 5005; ++j)
      ar[j][i] += ar[j - 1][i];
  
  for (int i = 1; i < 5005; ++i)
  {
    int r = 2;
    int arrow = i + 1;

    while (r < 5005 && arrow < 5005)
    {
      ar[r][arrow] += ar[r - 1][arrow - 1];
      ++r;
      ++arrow;
    }
  }

  for (int i = 2; i < 5005; ++i)
  {
    int c = 2;
    int arrow = i + 1;

    while (arrow < 5005 && c < 5005)
    {
      ar[arrow][c] += ar[arrow - 1][c - 1];
      ++arrow;
      ++c;
    }
  }
  
  for (int i = 0; i < 5005; ++i)
    for (int j = 0; j < 5005; ++j)
      ans += (ar[i][j] > 0);

  cout << ans;
}

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

 

imos법은 이렇게 특정 상황에서 유연하면서도 강력한 해법이 될 수 있으니 익혀두면 도움이 될 것이다.

 

imos법을 이용해서 풀 수 있는 문제들을 수록한 블로그를 링크하면서 게시글을 마친다.

 

https://blog.hamayanhamayan.com/entry/2017/07/04/020117

競技プログラミングにおけるimos法・累積和問題まとめ - はまやんはまやんはまやん