HDU 3664: Permutation Counting

Codeforces 280B: Maximum Xor Secondary

链接：http://codeforces.com/problemset/problem/280/B

题意：给定一个序列，求对于任意L,R，在LR之间最大值与严格次大值异或值最大是多少。

做法：维护一个优先序列，可以证明每个元素最多只会进队一次出队一次，所以复杂度是O(n)的。

代码君：http://codeforces.com/contest/280/submission/3852565

Codeforces 280C: Game on Tree

链接：http://codeforces.com/contest/280/problem/C

题意：给一棵树，每次随机的删除一个结点和这个结点的子树，问删除整个树期望要删多少次

做法：每个结点的depth的倒数和即为最终结果，（不会证明）

代码君：http://codeforces.com/contest/280/submission/3852624

下面列出来的知识点是我接下来一段时间要搞的。。。

可持久化线段树

平衡树：splay

可持久化treap

树链剖分

dfs序

跳表

动态树

AC自动机

坑～

树上的相关问题：

http://wenku.baidu.com/view/4921ee23ccbff121dd36838b.html

要做的一些题目：

spoj GSS系列

spoj QTREE系列

AC自动机http://codeforces.com/contest/163/problem/E

坑～

http://fanhq666.blog.163.com/blog/static/819434262011179150889/

http://crfish.blogbus.com/logs/61521366.html

http://www.cppblog.com/MatoNo1/archive/2012/02/26/166547.html

http://www.shuizilong.com/house/archives/hld-lct/

http://www.shuizilong.com/house/archives/hdu-4010-query-on-the-trees/

http://www.artofproblemsolving.com/blog/54268

http://wenku.baidu.com/view/5c6ca2dcce2f0066f5332277.html

http://xietutu.com/archives/711

http://acforfun.com/?tag=%E5%8A%A8%E6%80%81%E6%A0%91

http://yc5-yc.blog.163.com/blog/static/137797109201341995941220/

http://cxjyxx.me/?p=148

https://quartergeek.com/summary-of-link-cut-tree/

http://zh.scribd.com/doc/3072114/7-

SPOJ GSS1 && SPOJ GSS3

链接：http://www.spoj.com/problems/GSS1/ http://www.spoj.com/problems/GSS3/

题意：GSS1和GSS3一样query都是区间最大连续和，只不过GSS3有个单点update罢了

做法：维护sum(区间和)，maxSum(区间最大连续和)，maxLeft(左儿子区间最大连续和)，maxRight(右儿子区间最大连续和)

代码君：GSS1：http://ideone.com/5tepgk    GSS3：http://ideone.com/MsopAu

SPOJ FREQUENT

链接：http://www.spoj.com/problems/FREQUENT/

题意：给个不下降序列，无update，query是求区间重复出现最多的数

做法：注意到是不下降序列，那么这个问题就转化成求区间连续相同序列的长度，因为是不下降的，所以不用维护区间最左和最右的值，可以只维护maxLen，leftLen，rightLen。

代码君：http://ideone.com/nGIts7

SPOJ

keng