万能的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]); }
POJ 3719 Art of Balance
PKU某月的月赛中的一道题.写一写来练手.
题目大意是: 给出m个砝码(m<=16),有一个有n个节点的二叉树(n<=100),这棵树上有m个叶子节点,每个叶子节点可以挂上一颗砝码,一颗子树的重量是地下挂的所有砝码的重量之和,定义不平衡量为abs((lch.weight / root.weight)-1/2)*1000 , 要求给出一种方案,是的不平衡量的总和最小.
稍微想了下..m只有16..好吧...状态压缩的treedp.
记下f[root,state]为处理根为root的子树,底下用的砝码的状态为state..然后直接转移吧..
#include <stdio.h> #include <memory.h> typedef struct treenode{ int lch,rch,count; }; int cases,n,m,a[17],st[17][65538]; double f[102][65538],w[65538]; struct treenode tree[102]; int dfs(int root) //统计每棵子树所包含的叶子节点的数目. { if (tree[root].lch < 0 && tree[root].rch < 0) tree[root].count = 1; else tree[root].count += dfs(tree[root].lch) + dfs(tree[root].rch); return tree[root].count; } void calc_w() //计算各种状态的重量 { memset(w,0,sizeof(w)); for (int i=1; i<(1 << m); ++i) for (int j=0; j<m; ++j) if (i & (1 << j)) w[i] += a[j+1]; } void build_state(int state,int posi,int len) //生成有用状态 { if (posi > 16) return; build_state(state,posi+1,len); state = state | (1 << (posi-1)); st[++len][++st[len][0]] = state; build_state(state,posi+1,len); } double abs(double a) { if (a < 0) a = -a; return a; } double search(int root,int state) //DP主过程.(记忆化搜索) { if (f[root][state] < 0) { f[root][state] = 2000000000; if (tree[root].count == 1) { f[root][state] = 0; return 0; } for (int i=1; i<=st[tree[tree[root].lch].count][0]; ++i) { int tstate = st[tree[tree[root].lch].count][i]; if ((state & tstate) == tstate) { double temp = search(tree[root].lch,tstate)+search(tree[root].rch,state ^ tstate)+abs((w[tstate]/w[state])-0.5)*1000; if (f[root][state] > temp) f[root][state] = temp; } } } return f[root][state]; } int main() { scanf("%d",&cases); build_state(0,1,0); for (; cases; --cases) { scanf("%d",&n); memset(tree,0,sizeof(tree)); for (int i=1; i<=n; ++i) scanf("%d %d",&tree[i].lch,&tree[i].rch); dfs(1); scanf("%d",&m); memset(a,0,sizeof(a)); for (int i=1; i<=m; ++i) scanf("%d",&a[i]); calc_w(); for (int i=1; i<=n; ++i) for (int j=1; j<(1 << m); ++j) f[i][j] = -1.0; printf("%.3lf\n",search(1,(1 << m)-1)); } }
[转]Think like an OIer
Matrix67.com原创，转贴请注明出处。
Think like an OIer...
1. 与32、95、XP属于同一类事物的是：
A. 61 B. SEX
C. 我 D. Love is Everything
2. 如果48=0，那么84等于什么？
A. : ) B. T
C. 000 D. 12:56
3. 下面这些选项中哪一项是一种计算机高级语言？
A. B.
C. D.
4. 下面这些算式中哪一个算出来很可能是负数？
A. 1111+1111 B. 2222+2222
C. 11111+11111 D. 22222+22222
5. (10000000000)2
A. (1024)1 B. (1024)10
C. (1024)100 D. (1024)1000
6. 请选择下列描述中错误的一项：
A. 270400是一个完全平方数
B. 500500是一个三角形数
C. 33550336是一个完全数
D. 以上三项全错
7. 这道题的题目是什么？
A. 关于递归运算的题目
B. 关于线性规划的题目
C. 关于汇编语言的题目
D. 关于周莉莉的一切
8. 1099511627776B
A. tumor B. tuberculosis
C. aeroacrophobia D. pneumonoultramicroscopicsilicovolcanoconiosis
9. 下面四个选项中有几个是错误的？
A. 1个 B. 2个
C. 3个 D. 4个
10. 以下哪个命令可以列出当前目录下的文件？
A. 楼主 B. 楼上
C. 火星 D. 沙发
11. 请选出下面四个选项中与众不同的一项：
A. 1 B. 2
C. 3 D. 4
12. 你认为OIer最喜欢下列哪个选项？
A. C B. C
C. C D. C
13. 恐怖份子与战斗机
A. √ B. ×
C. ∴ D. ∵
14. 27乘以6.5等于多少？
A. 92.755 B. 175.6
C. 23.1516 D. -7632.33
15. 
16. We use Θ if O( f(n) )=__( f(n) )
A. 劳力士 B. 欧米茄
C. 天梭 D. 斯沃琪
17. 以下哪个选项在英文中出现频率最高？
A. 麦当劳 B. 氧
C. 2.718 D. 函数
18. 打网游为什么经常死机？
A. 经常出现各种人物
B. 经常出现各种宠物
C. 经常出现各种怪物
D. 经常出现各种NPC
19.
A. 123456 B. 234567
C. 345678 D. 456789
20 以下哪个选项正是本题所缺少的？
A. , B. .
C. ? D. !
