6581: Shinobu Loves Segment Tree
内存限制:256 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
As a cold-blooded, hot-blooded, and iron-blooded vampire, Shinobu likes to build segment trees.
She uses the build() function to build a segment tree, and the process of building the segment tree will increase the value of some numbers.
The specific content of the build() function is as follows:
```
void build(int id, int l, int r){
value[id] += r-l+1;
if(l == r) return;
int mid = (r+l)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
return;
}
```
For example, if Shinobi calls build(1,1,2) once, then value[1] will increase by 2, value[2] and value[3] will increase by 1.
In the long life of a vampire, Shinobu builds a segment tree every day. She has been doing this since day 1, and on the i-th day, she will call build(1,1,i) to build a segment tree.
As a fan of Shinobi, playf got a fan number x. Now he wants to ask you a question: what the value[x] will be at the end of the n-th day ?
Attention: The initial value of all values is 0.
She uses the build() function to build a segment tree, and the process of building the segment tree will increase the value of some numbers.
The specific content of the build() function is as follows:
```
void build(int id, int l, int r){
value[id] += r-l+1;
if(l == r) return;
int mid = (r+l)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
return;
}
```
For example, if Shinobi calls build(1,1,2) once, then value[1] will increase by 2, value[2] and value[3] will increase by 1.
In the long life of a vampire, Shinobu builds a segment tree every day. She has been doing this since day 1, and on the i-th day, she will call build(1,1,i) to build a segment tree.
As a fan of Shinobi, playf got a fan number x. Now he wants to ask you a question: what the value[x] will be at the end of the n-th day ?
Attention: The initial value of all values is 0.
输入
The first line of the input contains a single integer t(1≤t≤10^5) --- the number of test cases.
Each of the next t lines contains two integers n,x(1≤n≤10^9,1≤x≤4×n) --- playf's question.
Each of the next t lines contains two integers n,x(1≤n≤10^9,1≤x≤4×n) --- playf's question.
输出
For each question, print one line contains one integer --- the answer to the i-th question.
样例输入 复制
7
2 3
3 3
4 3
26 49
1000000000 4000000000
1000000000 1
11451419 19810
样例输出 复制
1
2
4
9
0
500000000500000000
4004478229