Segment Tree

時間限制:?1 Sec??內存限制:?512 MB
提交:?107??解決:?23
[提交] [狀態] [命題人:admin]

題目描述

Mcginn opens the code which he wrote 25 years ago.

Clever Mcginn wants to know how many positive interger n satis?ed that the maximum c can reach whencall function build(1 , 1 , n) in the main function is m.
There are T test cases. Each case contains one integer m.

?

輸入

Input is given from Standard Input in the following format:
T
m1
m2
.
.
.
mT
Constraints
1 ≤ T ≤ 100
1 ≤ m ≤ 1018

?

輸出

For each m print one line denotes the answer.

?

樣例輸入

復制樣例數據

3
3
4
5

樣例輸出

1
0
1
?

題目大意：

先輸入一個整數t，其下t行每行輸入一個整數m，代表的是線段樹的最后一個節點的數值，問有多少范圍滿足這種線段樹。

解題思路：

首先我們可以知道，對于節點x，在線段樹中其左節點為x*2，右節點為x*2+1，并且左子數包含的點等于右子樹包含的點數或者等于右子樹包含的點數加一，所以對于每一個節點，用l代表此節點包含的最小能包含幾個數，r代表此節點包含的最多能包含幾個數，c代表當前節點的層數。

?以57為例：

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;cin>>t;while(t--) {ll m;cin>>m;if(m%2==0) cout<<0<<endl;else {bool ju=false;ll l,r,x,c;l=1LL;r=1LL;x=m;c=0;while(x>1) {ll l1,l2,r1,r2;/*cout<<l<<" "<<r<<" "<<x<<" "<<c<<endl;*/if(x&1) {l2=l;r2=r;if(c==0) {l1=1;r1=1;}else {l1=l;r1=min(r2+1,1LL<<c);if(r1<l1) {ju=true;break;}}l=l1+l2;r=r1+r2;if(r<l) {ju=true;break;}x=(x-1)>>1;c++;}else {l1=l;r1=r;if(c==0) {l2=0;r2=0;}else {if(l==1) l2=1;else l2=l-1;r2=min(r1,1LL<<(c-1));if(r2<l2) {ju=true;break;}}l=l1+l2;r=r1+r2;if(r<l) {ju=true;break;}x=x>>1; c++;}}if(ju) cout<<0<<endl;else cout<<r-l+1<<endl;}}return 0;
}

?