万能的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杨思雨的论文）
C++之我头晕:关于stdio
一样的先来看一段代码:
#include <stdio.h> int main(void) { int age; char name[80]; puts("Enter your age."); scanf("%d", &age); puts("Enter your name."); scanf("%s", name); printf("Age is %d.\n", age); printf("Name is %s.", name); return 0; }
当然在程序里是看不出什么有趣的地方..
如果你把它运行起来...第一个输入"23.00"..会发生什么奇妙的事吗?
显然发生了...这都是伟大的scanf函数的功劳..
首先是读入一个整形变量...输入是"23.00"..他把"23"读走了..还剩".00"留在stdin里..
于是到了第二个scanf函数里..读入一个字符串..就把".00"取走了..于是就奇妙了..
密码风暴隐藏关卡之数独解决
用pascal写了段..贴出来献丑啦...
穷举搜索..很简单吧? 懒的做优化了..反正密码风暴里的搜索量又不大..
这个是给出所有可行解的.只要一个的话自己改一改..
C++之严谨篇第一话:强制类型转换及编译器优化
#include <iostream> using namespace std; int main() { const int i=10; int *pi,*pt; pi=(int *)&i; pt=(int *)&i; cout<<*pi<<endl; *pi=11; cout<<*pi<<" "<<i<<" "<<*pt<<endl; cout<<pi<<" "<<&i<<" "<<pt<<endl; return 0; }
以上的代码输出会是什么呢?
在Linux下或是在Windows下结果都一样...用了微软的C++以及开源的G++编译器
最后结果相同.
首先是那几个变量的地址是一样的.
在输出*pi,*pt时结果是11,输出i的结果却是10
