………………

## LCA最近公共祖先

LCA就是LCA

### LCA的实现

1.让深的那个节点,$x$往树上爬，直到$deepth_x = deepth_y$；
2.让两个节点一起向上跳，如果碰在一起了，那么就找到了。

ST表的功能很简单：

## 线段树

### 什么是线段树

（1）求最值：给定$i$,$j<=n$，求${a_i, …, a_j}$区间内的最值。
（2）修改元素：给定$k$和$x$，把$a_k$改成$x$。

POJ-2349

## 题目描述

The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.

## 题目描述

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.

POJ-3784

## 题目描述

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.