Chenjb is struggling with data stucture now. He is trying to solve a problem using segment tree. Chenjb is a freshman in programming contest, and he wrote down the following C/C++ code and ran ''Node* root = build(1, n)'' to build a standard segment tree on range [1,n]:
Chenjb submitted his code, but unfortunately, got MLE (Memory Limit Exceeded). Soon Chenjb realized that his program will new a large quantity of nodes, and he decided to reduce the number of nodes by pruning:
You know, Chenjb is a freshman, so he will try different values of k to find the optimal one. You will be given the values of n and k, please tell him the number of nodes that will be generated by his new program.
Node* build(long long l, long long r) {
Node* x = new(Node);
if (l == r) return x;
long long mid = (l + r) / 2;
x -> lchild = build(l, mid);
x -> rchild = build(mid + 1, r);
return x;
}
Chenjb submitted his code, but unfortunately, got MLE (Memory Limit Exceeded). Soon Chenjb realized that his program will new a large quantity of nodes, and he decided to reduce the number of nodes by pruning:
Node* build(long long l, long long r) {
Node* x = new(Node);
if (r - l + 1 <= k) return x;
long long mid = (l + r) / 2;
x -> lchild = build(l, mid);
x -> rchild = build(mid + 1, r);
return x;
}
You know, Chenjb is a freshman, so he will try different values of k to find the optimal one. You will be given the values of n and k, please tell him the number of nodes that will be generated by his new program.