CodeForce - Code For 1(768B)

문제(링크)

문제 설명 :
N, L, R 이 주어집니다.
2보다 크거나 같은 모든 수 x에 대해 다음 작업을 수행합니다.

왼쪽 = x / 2
중간 = x % 2
오른쪽 = x / 2

가장 마지막엔 0 과 1 로만 구성된 배열이 나오개 되는데, 이때 L번째~R번째에 있는 1의 개수를 구하는 문제입니다.

풀이:
먼저, 가장 간단하게 생각하면 0 과 1 의 최종 배열을 구한 뒤 구간을 돌며 1의 개수를 구하는 법을 생각해 볼 수 있습니다. 하지만 N 값이 2^50 이기 때문에 최종 배열의 길이가 2^50을 훌쩍 넘어갑니다.(최종 배열의 1의 개수는 항상 N개 입니다.)

따라서 배열을 만들지 않고 재귀함수를 이용하여 L, R 구간에 포함될 경우 1의 개수를 카운트하는 식으로 풀이하였습니다.(세그먼트 트리의 탐색과 유사합니다.)

10에 대해 최종 배열까지의 과정을 나타내면 다음과 같습니다.

여기서 각 노드마다 자신의 start, mid, end 값을 지정해줍니다.
즉, 노드 10의 start = 1, mid = 8, end = 15 입니다.
또 왼쪽 노드 5의 start = 1, mid = 4, end = 7 입니다.

이제 각 노드들을 왼쪽, 자기 자신(now % 2) , 오른쪽으로 탐색해가며 leaf노드까지 내려갑니다.
R < start || L > end 인 경우 자신의 자식 노드들도 구간에 포함되지 않으므로 더 이상 탐색할 필요가 없어 시간을 단축할 수 있습니다.
또, 자기 자신의 인덱스인 mid도 구간에 포함되는지 여부를 판단하여 더해주어야 합니다.

위 방법을 쓰려면 최종 배열의 총 길이를 알아야 하는데, 위 트리의 대칭성을 이용해 재귀 함수로 구할 수 있었습니다.(getLeng())

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#include<vector>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>

long long N, l, r;
long res = 0;
long long pos = 0;
long long leng = 0;

long long getLeng(long long now) {

 if (now == 1) {
  return 1;
 }
 if (now == 0) {
  return 1;
 }
 
 long long temp = getLeng(now / 2);
 long long pos = temp;

 if (pos >= l && pos <= r)
  res += now / 2;

 pos++;

 if (pos >= l && pos <= r)
  res += now % 2;

 pos += temp;

 if (pos >= l && pos <= r)
  res += now / 2;

 return pos;
}

long long recul(long long now, long long s, long long e) {
 long long mid = (s + e) / 2;
 if (s > r || e < l) return 0;
 //구간에 포함되지 않으면 계산x

 if (now == 1) {
  return 1;
 }
 if (now == 0) {
  return 0;
 }

 long long ret = 0;
 ret += recul(now / 2, s, mid - 1);
 
 if (l <= mid && r >= mid)
  ret += now % 2;
 ret += recul(now / 2, mid + 1, e);

 return ret;
}

int main(void) {
 FIO;

 cin >> N >> l >> r;

 leng = getLeng(N);

 cout << recul(N, 1, leng);
}