当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7204:Shinobu Loves Segment Tree

题目描述
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.
输入解释
The first line of the input contains a single integer $t(1 \le t \le 10^5)$ --- the number of test cases.

Each of the next $t$ lines contains two integers $n, x(1 \le n \le 10^9, 1 \le x \le 4\times 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

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-7204

最后修改于 2022-09-15T06:17:21+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/2000MS(Java/Others) 524288/262144K(Java/Others)