POJ 2309 BST 树状数组基本操作

POJ 2309 BST 树状数组基本操作

Description

Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for there queries. 



<span>POJ 2309 BST 树状数组基本操作</span>

Input

In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 <= X <= 2
31 – 1).

Output

There are N lines in total, the i-th of which contains the answer for the i-th query.

Sample Input

2
8
10

Sample Output

1 15
9 11

本题就考了树状数组的最最基本操作,对于会树状数组的人来说是太水了。

附个精简得不得了的代码,时间效率是O(1)

#include <stdio.h>
int main()
{
	int T, x;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &x);
		printf("%d %d\n", x-(x&(-x))+1, x+(x&(-x))-1);
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119129.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 闫学灿acwing_分组背包问题

    闫学灿acwing_分组背包问题有 N 种物品和一个容量是 V 的背包。物品一共有三类:第一类物品只能用1次(01背包);第二类物品可以用无限次(完全背包);第三类物品最多只能用 si 次(多重背包);每种体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。si=−1 表示第 i 种

  • c语言中求字符串的长度的函数_c语言求最大字符串

    c语言中求字符串的长度的函数_c语言求最大字符串在C语言中求字符串的长度,可以使用sizeof()函数和strlen()函数,后者需要引入string.h(#include<string.h>)因为C语言字符串是以\0结尾表示

  • 最受欢迎的 Linux 怎么是它,Ubuntu 排第六

    最受欢迎的 Linux 怎么是它,Ubuntu 排第六????作者:Linux猿????简介:CSDN博客专家????,C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!????关注专栏:Linux(优质好文持续更新中……)????不多废话,先来看一下排名:图1DistroWatch网站排名上面是排名前30位的最受欢迎的Linux操作系统,可以看到,比较熟悉的操作系统也名列前茅,比如:Ubuntu、Debian、Fedora、Arch、CentOS、UbuntuKylin以及deepin等。上面的排名是

  • MINI PCI-E接口_pcie接口原理图

    MINI PCI-E接口_pcie接口原理图1、PCIe3.0X4下图只用了2Lanes,pcie接口分x1、x4、x8、x16接口,向下兼容。含一对差分CLK时钟信号上图:pciex4引脚定义2、minipcie和msata接口一样minipcie和msata接口定义是一样的,可以相互交换使用。都是只有1对Tx和1对Rx,没有差分CLK时钟信号。下图是msata接口,常用于系统盘。上图:msata盘上图:minipcie引脚定义上图:msata引脚定义…

  • python 画图命令[通俗易懂]

    python 画图命令[通俗易懂]画图importmatplotlib.pyplotaspltplt.rcParams[‘font.sans-serif’]=[‘SimHei’]#用来正常显示中文标签plt.rcParams[‘axes.unicode_minus’]=False#用来正常显示负号plt.figure()plt.plot(x_data,y_data,color="red",linewidth=2)…

  • 素数环

    素数环素数环时间限制:1000 ms|内存限制:65535 KB难度:2素数环时间限制:1000 ms|内存限制:65535 KB难度:2

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号