#P6025. 线段树
线段树
题目背景
小 W 学习了一种叫做线段树的数据结构。
题目描述
很快,小 W 就发现:线段树实在是太浪费空间了!
比如,一棵 的线段树长下面这样:
可以发现,只有 个节点存储了有用信息,但使用的数组下标到了 。
令 表示一棵 个叶子节点的线段树所占的最大数组下标,现在小 W 想让你求出:
$$f(l)\;\oplus\;f(l+1)\;\oplus\;f(l+2)\;\oplus\cdots \oplus\;f(r) $$其中, 表示异或运算,相当于 C++ 中的^
符号。
输入格式
一行两个整数,表示 ,意义如上。
输出格式
一行一个整数,表示结果。
6 6
13
提示
样例解释
,故答案为 。
提示
如果你不知道什么是线段树:
void build(int k,int l,int r)
{
if(l==r)
{
//do something
//e.g. tree[k]=a[l]
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
//do something
//e.g. tree[k]=tree[k<<1]+tree[k<<1|1]
}
翻译成人话就是:编号为 节点有一个线段 ,如果 ,那么令 ,它有两个子节点,左儿子编号为 ,线段为 ;右儿子编号为 ,线段为 ,然后在子节点上递归建树。
调用build(1,1,n)
后就建好了一棵线段树,即编号为 的结点的线段为 。
数据范围
对于 的数据,。
对于 的数据,。
对于 的数据,,答案在long long
范围内。