题目链接：Here
这一题是我今年省赛最大的遗憾啊。诶。。。想想就觉得伤心啊。这一题其实不难，但是比赛时，我已经先到了怎么做，，但是由于鄙人的失误，结果导致我们队后两个小时的时间都耗在那里了。越想越觉得可惜啊。我们现在看看这题的思路吧。
这一题，貌似大多人都是有STL的set做的。其实，这一题可以用线段树做（不知道线段树的童鞋请移步：这里），而且还是简单的单点更新问题。不知道单点更新的同学请移步：这里。虽然我做线段树的题目不是很多，但是我发现了一个规律。利用这个规律就可以更好的判断，此题是否为线段树的题目。
规律：题目中一般有插入删除之类的操作，数据范围一般在10的5次方到10的6次方左右，这样的题目一般都可以用线段树来解（纯属个人经验，如有例外欢迎指出，不过我还没见过不服从这个规律的线段树的题目）。
现在我们言归正传。对于这一题我们应该怎么用线段树处理呢？我们利用结构体，定义两个变量value, cnt。value用来存储输入的值（如果没有输入，那么久给它一个很大的值），cnt用来记录该节点的值被输入的次数。如果输入次数为1的话，那么我们就让 value 的值等于叶子节点的值。这样题目就转化为一个单点更新，区间最值问题了。具体操作，详见代码。
这一题还有一个坑，不知道省赛是是不是这样。就是每一组操作后，它多给了一个空格例如：“b 2 ”这样。千万要注意，不然就是万年RE。
【代码如下】
//因为 log2（1000000）约为 20//所以树的深度为20#include <stdio.h>#define MAXN 1<<20#define Max 1e+6#define INF 0xfffffff#define min(a,b) a<b?a:bstruct ST{int value, cnt;}node[2*MAXN];int father[MAXN];void build(int v, int left, int right){node[v].value = INF;node[v].cnt = 0;if (left == right){father[left] = v;return;}int mid = (left + right) / 2;build(2 * v, left, mid);build(2 * v + 1, mid + 1, right);return;}void Update(int ri){if (ri == 1) return;int fa = ri / 2;int left = node[2 * fa].value;int right = node[2 * fa + 1].value;node[fa].value = min(left, right);Update(fa);}int main(){char ch[5];int T, n, num;scanf("%d", &T);while (T– && scanf("%d", &n)){build(1, 1, Max);while (n–){scanf("%s", ch);if (ch[0] == 'q'){if (node[1].value == INF)printf("none\n");elseprintf("%d\n", node[1].value);}else{scanf("%d", &num);if (ch[0] == 'b')node[father[num]].cnt++;else if (ch[0] == 'c')node[father[num]].cnt–;if (node[father[num]].cnt == 1)node[father[num]].value = num;elsenode[father[num]].value = INF;Update(father[num]);}}}return 0;}（如有错误，欢迎指出，转载请注明出处）
或者在河边放下一盏写着心愿的河灯，祝愿一切安好。
