我的高雄之旅之一 —— 落地之后
其实我去高雄的主要目的不是去旅游，而是去参加ACM-ICPC 2010 Regional Kaohsiung Site的。稍微解释下，ACM（Association for Computing Machinery）是美国计算机协会，ICPC（International Collegiate Programming Contest）是ACM所主办的国际大学生程序设计竞赛，要求参赛队伍（不超过3个人组成一队）在规定的时间（5小时一般）内在一定程度上解决一些问题（一般10题左右）。
从上海浦东机场出发，乘坐EVA AIR（长荣航空，我觉得英文名字听牛叉的）的班机直接前往高雄，机型为波音747-400，我还是第一次坐这么大的飞机。经济舱座位一排有10个吧，前面貌似还有双层的。面前还有一个显示屏，是放在前面一个座位背后的，于是每个机厢的第一排座位就悲剧了。显示屏实际上是个小电脑，触屏的，虽然感应不是很好，飞行的时候你可以自己选择看TV啦，听音乐啦，或者看电影，还有游戏玩（手柄自己从扶手上掰下来吧）。原本想看看特洛伊的，不过觉得飞行时间比较短，以及看了前面一点没看懂，就去找音乐听了。
1个小时45分钟后就在高雄降落了，机场不是很大，但是一个问题是：怎么这么热啊？我穿了一件外套+长袖，还是觉得保暖系统过于给力。还有一个问题是没有发现Doggy所说的“真善忍”，这个，也好。出站后就看到了两个NSYSU的志愿者，带我们去旁边的台湾银行换了点儿新台币。为了避免手续费过于强大，我们几个人和着上去兑换了，我出了RMB100，然后春哥给了我NTD450。汇率貌似是1：4.46**，手续费要收NTD30。机场兑换货币还是比较实惠的，后来去外面一些百货的是1：4.1等等。
在志愿者的安排下我们上了的士。这个的士司机属于中年大叔级别，以及他好给力啊！一路狂飙，看仪表盘上数值一般都在100+km/h，是老手，据说还闯了不少红灯，人不彪悍枉少年啊！。这时候台湾大选已经结束了，不然据说会看到一些宣传车什么的比较热闹，当然现在还剩下一些零星的宣传广告还没有撤除。好吧反正没关心过宝岛的OOXX，没一个认识的。目的地是国军英雄馆，听这名字我觉得好生牛叉啊。不过在春哥的解说下，把他想象成了空军招待所，然而事实上也正是这样。 下车乍一看对面是“高雄市立女子高级中学”，据说是高雄女校第一等学府，似乎很牛掰的样子，由于是女子学校，所有没能获得一次参观的机会，虽然最后从我们房间的窗户望过去就是“雄女”了。
说道住宿环境，如果当看房间的话还好，问题在于！我们竟然要4个人挤一间！好吧两张床铺还是比较大的，据说是双人床。宾馆貌似有些年代了，所以设施比较陈旧，比如那台老式电视，虽然还是彩色的。我们即将在这里住下四个晚上。安顿之后yyu带领我们去解决了饥饿这个问题，在旁边的一下“满家”饭店里一顿9个人吃了NTD3000+，对于大陆旅游者来说台湾物价还是比较高的啊。
好吧，暂时就写到这里吧，这篇比较流水，主要的地方还都没涉及到，请期待下文。
万能的Splay-处理区间问题
为什么会用到Splay呢，Splay虽然很强大但是不）同问题上替代品也有不少。其实主要是最近看到动态树、Link-cut Tree，里面需要维护一条路径的信息，而且路劲还是可分割，可合并的，这里Splay就是最佳的组件了。
Splay如果仅仅作为一棵二叉平衡查找树（BST）来使用的话的确效率是不尽人意，不过正如Splay的中文名—伸展树，它的发明不仅仅是作为一棵平庸的BST来使用的，较高的常数和看起来不怎么爽的平摊O(logN)的效率带来的是其非常丰富的功能。比如现在所讲的—如何用Splay处理区间问题。
给个例题，POJ3468，题目意思是：给一个连续的区间[1..N]，区间里每个元素上面都有一个数值。每次有两种询问，第一种是给定区间[A,B]，把里面所有元素的数值加上某个数字C，第二种询问是给定区间[A,B]，求区间里所有元素数值的和。
其实这题用线段树还是能非常轻松的过掉的。不过今天就要自虐一下写个Splay。
首先呢，我们以元素的序号为关键字建一个二叉查找树（平衡不平衡这里其实无所谓，反正Splay几下就均摊平衡了。），树上的每个节点代表一个元素，为了方便起见我们可以再插入两个元素0和N+1（等下你就知道为什么需要这俩东西了。）。
接下来的问题呢，是如何把一段连续的区间在树上展现出来，一般人都会比较混沌，因为树上的结构看起来或许很乱。但是Splay在这里就发挥了他十分大的优势，比如，询问区间为[A,B]，我们可以先把元素A-1旋到树根，这样询问区间里的所有元素都在树根的右子树里，接下来的手法类似，就是单独取下那棵右子树（[0..A-1]区间里的元素就这样被我们忽略了），然后把B+1选到树根上，这样树根的左子树就是代表着我们需要处理的区间[A,B]了。
接下来的事情就比较简单了，对于第一种询问，我们可以对于每个节点多记录下一个新信息size，表示以该节点为根的子树下有多少个节点，然后再用类似线段树的标记传递的方法覆盖下去。对于第二种询问，我们可以对每个节点维护sum，表示以该节点为根的子树下所有元素的和是多少。然后问题就此解决了哈哈～
（Splay的基础知识参考NOI WinterCamp2004杨思雨的论文）
在Ural上被阴了一题 -> Ural 1028
题目就不多说了..原本是找些线段树的题目来练练手.
结果这题..看起来好水..可以用树状数组切掉..
看到这么水的题目不忍心放弃..就开始随便写..
结果交上去TLE..觉得非常新奇..找了段线段树的程序扔上去AC了.(没天理啊..)
仔细观察题目.才发现..当坐标为0的时候..我可怜的树状数组啊..就开始无限的循环下去了.
还好..赶紧解决..可以把所有坐标加个1..也可以对于0的情况特判.
以下为我AC的程序:
#include <stdio.h> #include <memory.h> int n,a[15001],b[15001],ans[15001],tree[60000],t; int Query(int a) { if (!a) return tree[0]; int ans = 0; while (a) { ans += tree[a]; a -= (a & (-a)); } return ans + tree[0]; } void update(int a) { if (!a) { ++ tree[0]; return; } while (a <= 32768) { ++ tree[a]; a += (a & (-a)); } } int main() { freopen("input.txt","r",stdin); scanf("%d",&n); for (int i=1; i<=n; ++i) scanf("%d %d",&a[i],&b[i]); for (int i=1; i<=n; ++i) { update(a[i]); t = Query(a[i]); ++ ans[t]; } for (int i=1; i<=n; ++i) printf("%d\n",ans[i]); }
