Segment Tree

時間限制:?1 Sec??內(nèi)存限制:?512 MB
提交:?107??解決:?23
[提交] [狀態(tài)] [命題人: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.

?

樣例輸入

復制樣例數(shù)據(jù)

3 3 4 5

樣例輸出

1
0
1
?

題目大意：

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

解題思路：

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

?以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; }

?

總結(jié)

以上是生活随笔為你收集整理的【线段树】Segment Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。