*[CodeForces - 768B] Code For 1(분치 전략, 아날로그 이분 사상, 아날로그 라인 트리 사상)

문제집:
Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.
Initially Sam has a list with a single element n. Then he has to perform certain operations on this list. In each operation Sam must remove any element x, such that x > 1, from the list and insert at the same position , ,  sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.
Now the masters want the total number of 1s in the range l to r (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?
Input
The first line contains three integers n, l, r (0 ≤ n r - l ≤ 105, r ≥ 1, l ≥ 1) – initial element and the range l to r.
It is guaranteed that r is not greater than the length of the final list.
Output
Output the total number of 1s in the range l to r in the final sequence.
Examples
Input

7 2 5

Output

4

Input

10 3 10

Output

5

Note
Consider first example:
Elements on positions from 2-nd to 5-th in list is [1, 1, 1, 1]. The number of ones is 4.
For the second example:
Elements on positions from 3-rd to 10-th in list is [1, 1, 1, 0, 1, 0, 1, 0]. The number of ones is 5.
제목 대의:
하나의 수 n과 하나의 구간 [l,r](r-l<1e5,n<2^50)을 주고 매번 서열에서 1보다 큰 숫자를 (n/2,n%2,n/2)(그중 n/2는 아래로 정돈)로 나누어 모든 수가 0 또는 1이 될 때까지 [l,r] 구간에 1이 몇 개 있느냐고 묻는다.
문제 해결 보고서:
먼저 숫자를 나누고 o(n) 구간을 조회해 볼까?좀 귀찮은데, 사실 숫자를 나누는 과정에서 답이 나올 수 있어요.
AC 코드:
    

#include
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
ll l,r;
ll dfs(ll n,ll curl,ll curr) {
	if(curl > r || curr < l) return 0 ;
	if(n == 1) return 1;
	ll res = 0;
	ll mid = (curl+curr)/2;
	if(n % 2 == 1 && (mid<=r && mid>=l)) res++;
	return res + dfs(n>>1,curl,mid-1) + dfs(n>>1,mid+1,curr);
}

int main()
{
	ll n,x,len = 1;
	cin>>n>>l>>r;
	x = n;
	while(x > 1) {
		len = len*2+1;
		x>>=1;
	}
	printf("%lld
",dfs(n,1,len));
	return 0 ;
 }

요약:
처음에 코드를 쓸 때 두 군데가 시들었어.
첫 번째: 두 출구를 거꾸로 썼는데 생각해 봐도 틀렸어. 구간 내부에 먼저 써야 돼!!이것은 의심할 여지가 없는 것이다!!
두 번째:if(n% 2 = 1)res++;
 
왜 라인 트리처럼 둘 다 원하는 구간 내부에 있다면 단독으로 하나의 값을 되돌려주지 않았는지는 우리가 미리 렌을 계산했기 때문에 마지막에 나눈 답은 반드시 0이나 1이다. 그 n=1을 통해 무한귀속을 방지할 수 있다.그 다음에 0에 대한 처리는 그res에서 처리하면 됩니다. 왜냐하면 중간의 값만 0과 같은 상황이 나타나고 양쪽의 값은 0이 되는 상황이 나타나지 않습니다. 왜냐하면 2를 제외한 작업이기 때문입니다!!몇 개의 종점 가능한 값을 열거하면 간단하게 증명할 수 있다. 3/2=1,,,2/2=1,,,,1이면 출구이기 때문에 뜯을 때 양쪽에 0이 나타나지 않고 중간에 0이 나타날 수 있다.
그래서 사실 이 문제도 우리가 직접 과정을 모의하여 몇 개의mid값이 짝수인지 찾아야만 0이 나타날 수 있다. 0을 구한 수량이cnt0이라고 가정하면 결과는 r-l-cnt0이다.그러나 사실은 라인 트리build의 과정의,,, 그리고 l, r와의 크기 관계를 찾아야 하기 때문이다.
다른 네트워크의 이분적 사고방식의 코드를 첨부합니다: (아직 보지 않았습니다)

#include 
using namespace std;
typedef long long ll;
ll n, l, r, s = 1, ans;
void solve(ll a, ll b, ll l, ll r, ll d) { //     
	if ( a > b || l > r ) return;
	ll mid = (a+b)/2;
	if ( r < mid )solve(a,mid-1,l,r,d/2);
	else if( mid < l )solve(mid+1,b,l,r,d/2);
	else {
		ans += d%2;
		solve(a,mid-1,l,mid-1,d/2);
		solve(mid+1,b,mid+1,r,d/2);
	}
}
int main() {
	cin >> n >> l >> r;
	long long p = n;
	while ( p >= 2 ) {
		p /= 2;
		s = s*2+1;
	}
	solve(1,s,l,r,n);
	cout << ans << endl;
	return 0;
}