数据结构题目
一,并查集
并查集主要是对不相交的两种集合进行两种操作.
(1)检索某元素属于哪个集合
(2)合并两个集合
题目大意是有三种动物，A吃B，B吃C，C吃A，现在给定N句话，1 X Y 表示X和Y是同类，2 X Y 表示X吃Y，每句话满足下面三个条件之一就是假话：
i) 和前面的真话冲突
ii) X 或者 Y 比 N 大
iii)X吃X
否则就是真话。问这N句话里有多少句假话？
分析: 种类并查集，有三个种类，我们用rank[i]来表示 i 和 i 的父节点的关系。rank[i] = 0 表示 i 和父节点是同类，rank[i] = 1 表示 i 被父节点吃， rank[i] = 2 表示 i 吃父节点。然后在Find函数路径压缩时，有这样的代码:
int Find(int x){
if(x == father[x]) return x;
int tx = Find(father[x]);
rank[x] = (rank[x] + rank[father[x]]) % 3;
father[x] = tx;
return tx;
}
说一下代码的意思。当程序执行了前两句时，father[x]的父节点是 tx ，那么 rank[father[x]] 表示的就是 father[x] 与 tx 的关系，而我们路径压缩要将 x 的父节点换为 txm，所以 rank[x] 要相应改变，他们之间的关系如下:
rank[x] 0 0 0 1 1 1 2 2 2
rank[father[x]] 0 1 2 0 1 2 0 1 2
new rank[x] 0 1 2 1 2 0 2 0 1
所以有了 rank[x] = (rank[x] + rank[father[x]]) % 3 这一句代码。
而当合并时，同样也需要更新相应关系，代码如下:
void Union(int x,int y,int tx,int ty,int type){
//tx为x的父节点,ty为y的父节点type = 0表示同类,1表示x吃y,2表示y吃x
father[ty] = tx;
rank[ty] = (rank[x]-rank[y]+type+3)%3;
}
其中 tx 是 x 的父节点，ty 是 y 的父节点，所以 rank[x] 表示 x 和 tx 的关系，rank[y] 表示 y 和 ty 的关系，当将 ty 的父节点置为 tx 时，需更新相应关系。
我们同样分析一下他们之间的关系和合并后的关系
type 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
rank[x] 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
rank[y] 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
new rank[ty] 0 2 1 1 2 2 2 1 0 0 2 1 1 0 2 2 1 0
当 type = 3 时大家自己分析，一个道理。根据上面的关系，我们得到了rank[ty] = (rank[x] – rank[y] + type + 3) % 3这个关系。
这两个过程处理了，这个题就搞定了。关键是弄清楚在路径压缩时和在合并时关系的处理，如果比较复杂的话我们可以把所有可能的情况列出来然后找通用关系。3个中已经属于比较复杂的了，一般的种类并查集都是两个关系。只要分析清楚就OK了。
题目大意：N个人玩石头剪子布的游戏，有1个人当judge，其他人分为3组(可以为空),出三种不同手势，同一组人总是出同样的手势。judge随机出手势。现在给出M个关系，用来表示两个人玩的结果：平，赢，输。问能否确定谁是judge？如果能，最少在第几话之后就可以确定？
分析：和食物链一模一样的关系，三个手势相互制约。其中Find函数和Union函数和食物链一样，我们只需要枚举judge，然后判断这M句话到第几句有错误。如果当某个人是judge时所有的话都是对的，说明这个人是judge。最后如果
i) 没有能使所有话都对的人，则是Impossible
ii) 有多个这样的人，则是 Can not determined
iii) 如果只有一个，则选其他人做judge时出现错误最晚的句子为可以确定的句子
HDU3038 How many answers are wrong?
题目大意：给定一个N和M，表示有一个长为N的序列，M个关系: x y z表示第 x 项到第 y 项的和为 z ，问这些句子有多少是错误的。
分析：对于每一个关系x y z，转化为 sum[y] – sum[x-1] = z, 表示前 y 项和与前 x-1 项和的差为 z 。我们用 rank[i] 表示 i 与 i 的父节点的差，然后在路径压缩和合并时更新相应信息即可。
题目大意：一个岛上有两个部落，分别是好人和坏人。好人总是说真话，坏人总是说假话。现在有p1个好人，p2个坏人，给出N句话: x y yes/no表示 x 说 y 是/不是 好人，问能否唯一确定这p1个好人？如果能，输出这p1个好人的ID。
分析：我们先分析者N句话，如果是no：(1) x是好人，那么y就是坏人 (2)x是坏人，那么y是好人 ；所以如果是no那么x和y属于不同集合。同理，如果是yes则x和y属于同一个集合。通过这N句话，我们进行一系列合并操作得到K个集合，这K个集合里每个集合都有两种人a和b，现在问题转化为了从K个集合里各自找a或者b使得总数恰好为p1，这个可以用DP实现。假设有K个集合，第i个集合的两种人的个数为a[i][0] 和 a[i][1],用dp[i][j] 表示到第 i 个集合人数为 j 的情况数，那么有转移方程dp[i][j] = dp[i-1][j-a[i][0]] + dp[i-1][j-a[i][1]] (j > a[i][0], j > a[i][1])，最后如果dp[k][p1] = 1表示有唯一解，中间再加上记录的辅助数组就可以将选的这p1个人找出来了。
题目大意：商店有N种商品，每种商品有一个销售截止日期和该商品的利润，销售一个商品需要一个单位的时间，让找一个合理方案使获利最大。
分析：这里用并查集解决感觉很巧妙。我们先对每个商品按照利润从大到小排序，然后把每个商品的截止时间t看做一个时间段[1,t],初始时将所有时间的父节点设为自己，然后每次查询一个商品的根结点root如果大于0，则可以出售，并将它的根结点记为root-1，这样处理完N个商品就得到了最大利润。常规思路是 贪心+堆优化
POJ1611 The Suspects 水题，忽略之
基础的种类并查集，两个种类，路径压缩和合并更新相应信息即可
大意：有长度为N(N < 10^9)的01序列，给出M个关系x y odd/even 表示x到y的和是奇数还是偶数，问最多能满足前几个关系？
分析：转化为 sum[y] 与 sum[x-1] 是否同奇偶的问题。由于区间太大，我们将这M个问题的 x-1 和 y 离散化，然后就是一个比较基础的种类并查集了。
大意：有N个方块，编号1到N，现在有P个操作，M x y表示将含有编号为x的整体放在含有y的整体的上面，C x 表示询问在x下方有多少歌方块？
分析：我们用rank[x] 来表示含有x的集合的个数，用dist[x]来表示x 距离 x 的根结点有多少个方块，在路径压缩的时候更新dist数组，查询的时候答案就是rank[x] – dist[x] - 1。
大意：有N个电脑，每个电脑有一个坐标，距离不超过D的电脑之间可以直接连接，电脑之间也可以间接连接。初始时电脑都是坏的，现在给出一系列操作和查询，O x 表示修复电脑 x ，S x y 表示询问 x 和 y 是否能够连接。
分析：每次有修复的话就将刚修复的电脑和以前修复过且距离不超过D的电脑合并，合并时可以统一合并到根结点小的上边。然后查询即可。
大意：给出M个虫子之间的恋爱关系，问是否有同性恋。哈哈，好猥琐的题目！~
分析：简单的种类并查集，用rank数组表示和父节点的性别关系，路径压缩和合并时相应更新。
POJ2524 Ubiquitous Religions水题，忽略之
大意：给定一些边，问是否是一棵树？
分析：只要看边的两个顶点是否在这之前已经在一个集合即可。注意空树的情况，很恶心。
ZOJ3261 Connections in Galaxy War
大意：又N个点，每个点有一个权值，给出M条边，然后有Q个操作，操作有两种：(1) destroy x y摧毁x y 这条边 (2) query x 查询和x连接的权值最大的点，如果这个点权值没有 x 大，输出-1；如果有多个权值一样大的，输出ID小的。
分析：因为有销毁操作，所以我们想到了先把所有操作读进去，然后逆向处理：将边排序，二分所有要摧毁的边，将他们标记。然后倒着处理，如果是查询操作，直接查询即可，如果是摧毁操作，则进行合并。
二,平衡树
平衡树是二叉搜索树的一种,在二叉查找树中,搜索,插入,删除的复杂度都与高度h有关,因此高度是制约二叉搜索树时间效率的瓶颈.而平衡树利用了诸多变形,将这棵树的高度维护在了LogN.
Treap算法:
Treap=Tree+Heap,也可以这么理解Tree就是二叉搜索树,Tree+Heap就是用堆变形了的二叉搜索树,即在原来的基础上增加了一个随 机的优先值.所以,这个二叉搜索树节点插入的顺序是随机的,那我们得到的二叉搜索树大多数情况下是平衡的,相对于AVL,性价比绝对高.
详细介绍:http://www.nocow.cn/index.php/Treap
[PKU3481]Double Queue
SBT算法:
SBT是由CQF大牛自己原创的平衡树结构,相对于Treap,AVL等平衡树结构,SBT应该是这其中性价比中最高的一个.具体的思想参见Sqybi整理发布的PDF论文,很有用.
详细介绍:http://www.cnblogs.com/woodfish1988/archive/2007/12/21/1009673.html
[NOI2004]郁闷的出纳员
splay-tree算法：
研究了一下sbt(size balance tree)后,三鲜师傅评论说splay-tree功能更强大,并且有很多其他数据结构无法实现的功能
于是赶紧去学习,看了这题后发现sbt几乎完成不了其中的任何一个操作,而线段树也无法完成插入.删除.翻转的操作,但是splay却能很完美的解决
其他平衡二叉树是根据权值来限制树的结构的,没有splay这么灵活.splay的任意旋转可以对一整个区间进行操作,并且可以任意增加区间,任意删除区间,都是logn的复杂度.并且可以沿用线段树的延迟标记,每次不用急着传递给子树,遍历到时候传下去即可,然后更新上来(我写了push_down和push_up两个函数,其实线段树也是这个套路,不过我以前写线段树的时候直接把这两个函数写进update和query里的,现在回去看以前线段树的代码感觉很乱,没有单独写出来优美~)
献上Crash撞神大牛的论文,里边就是将splay对一个区间的具体操作
一些其他二叉平衡树叶能完成的操作在这篇和楼教主同个时代的美女神牛杨思雨的论文里有介绍
介绍一些练习splay的题目:
【splay入门】用其他平衡二叉树能解决:(理论复杂度没有sbt好,但我用splay却比写sbt还快=.=)
[HNOI2002]营业额统计
[NOI2004]郁闷的出纳员
[HNOI2004]宠物收养所
【splay热身】其他平衡二叉树不能解决,但是线段树和splay能解决(效率是线段树的1~5倍.)
I Hate It(更新节点,区间最值)
A Simple Problem with Integers(成段更新,区间求和)
Memory Control(较为复杂的区间操作)
更多热身题可以去这里找
【splay进阶】其他平衡二叉树和线段树都无法解决:
Robotic Sort
比较有意思的题目,结点处没有任何权值,只要记录每个数字对应的结点位子,然后从小到打把相对应的位子旋转到根节点,输出i+左子树的个数,接着给左子树一个翻转的延迟标记,最后删除该节点.注意把结点旋到根部的时候要先从根部把延迟标记push_down下去.
Queue-jumpers
可以用各种数据结构解决的题,用splay的话和上题差不多,记录结点的位子..Top的操作有点麻烦,记得每次操作后都要把结点splay到根部,不然会超时=.=
Play with Chain
此题有splay的最独特的操作 区间旋转和切割
[AHOI2006]文本编辑器editor(较为简单的插入删除旋转,小数据版)
[AHOI2006]文本编辑器editor(较为简单的插入删除旋转,大数据版)
这题很恶心,最后一个是结束符号也会让你输出来,我纠结了很久很久
[NOI2005]维修数列(在插入删除基础上增加区间统计,较难)
区间统计如果做了上边三个热身题的话应该没问题了
旋转和区间统计的时候要特别注意,两者结合产生的trick留给大家自己去发现,这个trick整了我一个下午
50M的数据量,用静态的数组开不下,动态的太浪费时间,怎么办呢?自己手动压个内存池吧
总结.splay的区间操作看上去很复杂,其实就是函数多,略数一下有以下几个
void Rotate(int x,int f)
void Splay(int x,int goal)
void RotateTo(int k,int goal)
void NewNode(int &x,int c)
void push_down(int x)
void push_up(int x)
void makeTree(int &x,int l,int r,int f)
void init(int n)
这几个函数是必不可少的,并且还要再根据题目意思加一些函数
但是真正理解了之后会发现…写了最上边的三个函数后 其实剩下的就和线段树差不多,这样看来编程复杂度也不是很大,手抽筋一下花个5分钟敲下这几个函数也就OK了
所以splay的题完全可以套上线段树的马甲再加上线段树无法完成的操作变成更难的题目
三,线段树
线段树是一棵二叉树,其结点是一条"线段",它的左儿子和右儿子分别是这条线段的左半段和右半段.
详细介绍:http://en.wikipedia.org/wiki/Segment_tree
线段树可以拓展为二维线段树,即树套树.一个线段树控制行,另一个线段树控制列,就可以达到二维线段树的目的.还有一种树叫做四分树,即将矩形进行四分,也不错.
1.hdu1166 敌兵布阵
更新节点,区间求和
2.hdu1754 I Hate It
更新节点,区间最值
3.hdu1698 Just a Hook
成段更新,总区间求和
4.hdu1394 Minimum Inversion Number
更新节点,区间求和(实现nlog(n)的逆序数方法,和树状数组比起来实在是有点鸡肋)
5.hdu1779 9-Problem C暂不公开
成段更新,区间最值
6.pku2777 Count Color
成段更新,区间统计,位运算加速(我总把query里的传递给子节点的步骤忘了)
7.pku3468 A Simple Problem with Integers
成段更新,区间求和(中间乘法会超int..纠结了)
8.pku2528 Mayor’s posters
成段更新,区间统计(离散化)
9.hdu2795 Billboard
更新节点,询问特殊(暑假的时候不会线段树被这水题狂虐)
10.pku3667 Hotel
成段更新,寻找空间(经典类型,求一块满足条件的最左边的空间)
11.hdu1540 Tunnel Warfare
更新节点,询问节点所在区间(同上一道Hotel一样类型的题目)
12.hdu2871 Memory Control
hotel变形题目,三个都函数一样(vector忘记清空检查了好久)
13.hdu3016 Man Down
成段更新,单点查询(简单线段树+简单DP)
14.hdu1542 Atlantis
矩形面积并,扫描线法(发现我们HDU的队员的矩形面积交模板基本都是在最坏情况下更新到底,宁波惨痛的教训啊..)
15.hdu1255 覆盖的面积
同上,扫描线法,我多加了一个系数csum,来统计覆盖两次的长度(156MS,第一次做线段树排到第一,纪念下)
16.hdu1828 Picture
扫描线,同面积统计,加了一个num_Seg统计一个扫描区域里的边
17.pku1436 Horizontally Visible Segments
成段更新,成段询问(染色问题,坐标*2后很简单,最后统计用暴力- -)
18.pku3225 Help with Intervals
成段更新,总询问区间(有个异或操作比较新颖)
19.pku2482 Stars in Your Window
成段更新,区间最值 + 扫描线(转化成区间最值有点巧妙,数据太TMD的恶心了,中间二分的地方会int溢出,检查了半个小时)
20.pku2828 Buy Tickets
思维很巧妙,倒过来做的话就能确定此人所在的位置
21.pku2464 Brownie Points II
更新节点,区间求和 + 扫描线(很好玩的一道题目,用两个线段树沿着扫描线更新,然后按”自己最多,对方最少”的方案一路统计)
(因为两棵树,我就直接写成类了)
22.pku3145 Harmony Forever
查找一个区间内最左边的数,询问的val大的话用线段树,小的话线性扫描,很囧的题目
23.pku2886 Who Gets the Most Candies?
寻找区间中的左数第N个数,约瑟夫环(学到了反素数表,可以不用把所有数字预处理出来了)
24.pku2991 Crane
记录了线段的两端点以及转过的角度,成段的转,超有意思的题目,做了之后会对线段树理解更深刻
(wy教主推荐的,不过我的代码写的太搓了..没啥学习的价值)
25.hdu1823 Luck and Love
二维线段树,没啥意思,代码量大了一倍而已,题目和运用范围都没一维的广,随便找了道题目练习下就好
四,树状数组
树状数组可以看成线段树的一个精简版,精在它的时空效率都比线段树要优,简在它的代码都比线段树要短.不过美中不足的是,使用线段树必须满足减法原则,否则就只能使用线段树.
详细介绍:http://www.nocow.cn/index.php/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84
先提个注意点，由于Lowbit(0) = 0，这会导致x递增的那条路径发生死循环，所有当树状数组中可能出现0时，我们都全部加一，这样可以避免0带来的麻烦～～
简单：
POJ 2299 Ultra-QuickSort
http://acm.pku.edu.cn/JudgeOnline/problem?id=2299
求逆序数，可以用经典的归并排序做，也是基本的树状数组题目。
因为a[i]比较大，但只有最多500000个，所以要离散化。
逆序数就是求前面的数比后面的数大的次数。从后往前看就是求后面比前小的数的个数。用树状数组！c[i]表示比i的值小的个数。
POJ 2352 Stars
http://acm.pku.edu.cn/JudgeOnline/problem?id=2352
题目意思就是求每个星星左下方的星星的个数，由于y轴已经排序好了，我们可以直接用按x轴建立一维树状数组，然后求相当于它前面比它小的个数，模板直接一套就搞定了～～
POJ 1195 Mobile phones
http://acm.pku.edu.cn/JudgeOnline/problem?id=1195
二维的树状数组，直接把Update()和Getsum()改为二维即可。
如Update()函数改为：
void Update(int x, int y, int d)
{ // 注意：当i = 0，0 + Lowbit(0) = 0，会造成死循环!
int i, j;
for (i = x; i < maxn; i += Lowbit(i)) // 注意这里是maxn，是tree[]的大小.
{
for (j = y; j < maxn; j += Lowbit(j))
{
tree[i][j] += d;
}
}
}
写这题的好时候就是求区间和时应该是（x2,y2）-(x2,y1-1)-(x1-1,y2)+(x1,y1)。
而不是（x2,y2）-(x2,y1)-(x1,y2)+(x1,y1).
POJ 2481 Cows
http://acm.pku.edu.cn/JudgeOnline/problem?id=2481
将E从打到小排序，如果E相等按S排序，然后就跟POJ 2352 Stars做法一样了～～
POJ 3067 Japan
http://acm.pku.edu.cn/JudgeOnline/problem?id=3067
先按第一个坐标排序从大到小排序，如果相等按第二个坐标从大到小排序，然后就又是跟Cows和Stars做法相同了...
做的时候有两点注意：1，算逆序的时候相同的不应该算，即求和时应该减一。2，要用__int64
POJ 2029 Get Many Persimmon Trees
http://acm.pku.edu.cn/JudgeOnline/problem?id=2029
O(n ^ 2)枚举起点，再用二维树状数组求其中的点数即可。
HOJ 2275 Number sequence
http://202.118.224.210/judge/show.php?Contestid=0&Proid=2275
两个一维树状数组，分别记录在它左边比它小的和在它右边比它大的即可～～
HOJ 1867 经理的烦恼
http://202.118.224.210/judge/show.php?Contestid=0&Proid=1867
先筛法求素数，然后如果从非素数改变成素数就Update(x, 1)，如果从素数改变成非素数就Update(x, -1)即可。
Sgu 180 Inversions
http://acm.sgu.ru/problem.php?contest=0&problem=180
经典树状数组 + 离散化。注意结果要用long long～～
SPOJ 1029 Matrix Summation
https://www.spoj.pl/problems/MATSUM/
基本的二维树状数组...
中等：
POJ 2155 Matrix
http://acm.pku.edu.cn/JudgeOnline/problem?id=2155
经典树状数组题目，分析见前一篇文章（树状数组学习系列1 之 初步分析——czyuan原创）～～
POJ 3321 Apple Tree
http://acm.pku.edu.cn/JudgeOnline/problem?id=3321
这题的难点不在于树状数组，而是如果将整棵树映射到数组中。我们可以用DFS()改时间戳的方法，用begin[i]表示以i为根的子树遍历的第一个点，end[i]表示以i为根的子树遍历的最后一个点。
比如数据为：
5
1 2
2 5
2 4
1 3
那么begin[] = {1, 2, 5, 4, 3}, end[] = {5, 4, 5, 4, 3}，下标从1开始。
对于每个点都对应一个区间(begin[i], end[i])，如果要改变点a的状态，只要Update(begin[a])，要求该子树的苹果树，即Getsum(begin[a] ) - Getsum(end[a] + 1)，(注：这里求和是求x递增的路径的和。)
POJ 1990 MooFest
http://acm.pku.edu.cn/JudgeOnline/problem?id=1990
这题的难点是要用两个一维的树状数组，分别记录在它前面横坐标比它小的牛的个数，和在它前面横坐标比它小的牛的横坐标之和。
按音量排个序，那么式子为：
ans += 1LL * cow[i].volumn * (count * x - pre + total - pre - (i - count) * x);
cow[i].volumn为该牛的能够听到的音量。
count为在第i只牛前面横坐标比它小的牛的个数。
pre为在第i只牛前面横坐标比它小的牛的横坐标之和。
total 表示前i - 1个点的x坐标之和。
分为横坐标比它小和横坐标比它大的两部分计算即可。
Hdu 3015 Disharmony Trees
http://acm.hdu.edu.cn/showproblem.php?pid=3015
跟上题方法相同，只要按它的要求离散化后，按高度降序排序，套用上题二个树状数组的方法即可。
HOJ 2430 Counting the algorithms
http://202.118.224.210/judge/show.php?Contestid=0&Proid=2430
这题其实是个贪心，从左往右或者从右往左，找与它相同的删去即可。先扫描一遍记录第一次出现和第二次出现的位置，然后我们从右到佐，每删去一对，只需要更改左边的位置的树状数组即可，因为右边的不会再用到了。
tju 3243 Blocked Road
http://acm.tju.edu.cn/toj/showp3243.html
这题主要在于如果判断是否连通，我们可以先用j = Getsum(b) – Getsum(a – 1)，如果j等于(b – a)或者Getsum(n) – j等于(n – (b – a))，那么点a, b联通。
SPOJ 227 Ordering the Soldiers
http://www.spoj.pl/problems/ORDERS/
这题与正常的树状数组题目正好想反，给定数组b[i]表示i前面比a[i]小的点的个数，求a[]数组。
我们可以先想想朴素的做法，比如b[] = {0, 1, 2, 0, 1}，我们用数组c[i]表示还存在的小于等于i的个数，一开始c[] = {1, 2, 3, 4, 5}，下标从1开始。
我们从右向左扫描b[]数组，b[5] = 1，说明该点的数是剩下的数中第4大的，也就是小于等于它的有4个，即我们要找最小的j符合c[j] = 4(这里可以想想为什么是最小的，不是最大的，挺好理解的)，而c[]是有序的，所以可以用二分来找j，复杂度为O(logn)，但现在问题是每次更新c[]要O(n)的复杂度，这里我们就想到树状数组，c[i]表示还存在的小于等于i的个数，这不正好是树状数组的看家本领吗～～所以处理每个位置的复杂度为O(logn * logn)，总的复杂度为O(n * logn * logn)。
hdu 2852 KiKi's K-Number
http://acm.hdu.edu.cn/showproblem.php?pid=2852
这题与上面那题类似，只是要求比a大的第k大的数，那我们用Getsum(a)求出小于等于a的个数，那么就是要我们求第k + Getsum(a)大的数，而删除操作只要判断Getsum(a) – Getsum(a - 1)是否为0，为0则说明a不存在。
难题：
POJ 2464 Brownie Points II
http://acm.pku.edu.cn/JudgeOnline/problem?id=2464
这道题用二分也可以做的，这里介绍下树状数组的做法。首先有n个点，过每个点可以做x,y轴，把平面切成BL, TL, TR, BR四个部分，我们现在的问题是如果快速的计算这四个部分的点的个数。
这样我们可以先预处理，先按y坐标排序，求出每个点正左方和正右方的点的个数LeftPoint[], RightPoint[]，复杂度为O(n)，同样我们再以x坐标排序，求出每个点正上方和正下方点的个数UpPoint[], DownPoint[]。还要求出比点i y坐标大的点的个数 LageY[]。注意：这里要进行下标映射，因为两次排序点的下标是不相同的。
然后按x坐标从小到大排序，x坐标相等则y坐标从小到大排序。我们可以把y坐标放在一个树状数组中。
对于第i个点，求出Getsum(y[i])即为BL的个数，然后Update(y[i])。由于现在是第i点，说明前面有i – 1个点， 那么
TL = i - 1 - LeftPoint[i]- BL;
TR = LargeY[i] - TL – UpPoint[i] ;
BR = n - BL - TL - TR - LeftPoint[i] - RightPont[i] - UpPoint[i] – DownPont[i] - 1;
这样我们就求出四个部分的点的个数，然后判断有没有当前解优，有的话就更新即可～～
UVA 11610 Reverse Prime
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=78&problem=2657&mosmsg=Submission+received+with+ID+7313177
一道很综合的树状数组题，用到了树状数组中的很多知识点，包括离散化，二分查找等。
1. 先按题目要求筛法素数，找到所有的Reverse Prime。
2. 将这些Reverse Prime离散化，只有78500个左右。树状数组中tree[i]记录比i小的点的个数。
当执行q a操作时，二分查找最小的j, 使得Getsum(j) 等于 ++a(因为a可能为0，所以统一加一)。这步与上面SPOJ 227 Ordering the Soldiers 类似。
3. 当执行d a操作时，先找到a离散化后的值b，然后Update(b, -1)即可。
按这样做后，运行时间为: 0.3s多，感觉很诧异，因为都是0.1s以下的。这里特别感谢liuzhe大牛的指点，其实题目中的Reverse Prime是由10^6以下的素数倒置得到的，那么得到的要求是7位，最后一位一定是0，我们可以对每个除以10处理，那么数的范围就减小了10倍，速度就提高了不少。
五,左偏树
左偏树可以理解成一种特殊的可合并堆,普通的二叉堆合并需要O(N)的复杂度,而左偏树的合并仅仅需要O(LogN)的复杂度,而且其他二叉堆支持的操作左偏树都支持.
详细介绍:http://blog.csdn.net/king821221/archive/2008/01/27/2068668.aspx
例题:
[ZJU 2334]Monkey King 左偏树 并查集
六,字典树
Trie,是一种利用串的公共前缀来节约空间,加快速度的一种检索字符串的树.
详细介绍:http://www.cnblogs.com/tanky_woo/archive/2010/09/24/1833717.html
例题:
[IOI2008]printer 字母树Trie
七,后缀数组
"后缀数组 — 处理字符串的有力工具."非常有用的,非常强大的数据结构.
今天拜读了罗穗骞的神作《后缀数组——处理字符串的有力工具》
这篇主要是模板以及应用,还有一篇许智磊的《后缀数组》主要讲概念和证明
两者结合疗效好- -
刚刚开始做的时候觉得不过尔尔,模板题而已
但越做到后边PKU3693越发觉有趣,非常巧妙的统计,随便把RMQ也学了
跟着论文做了几道题目,但还不知道以后出现后缀数组的题能不能解出来,呵呵
刷题途中发现3xian总是排第一—-无限崇拜并馋涎其模板,发现他的最大流,(kth number)图灵树,后缀树模板极其的高效。
下边收入几道论文上没提的后缀数组题目
zoj3199 Longest Repeated Substring
连续重复至少1次的最长串
spoj1811 Longest Common Substring
普通的LCS,同PKU2774,不过数据量超大,上边的模板超时,DC3刚好卡过,据说正解是后缀自动机,Orz
hdu2890 Longest Repeated subsequence
不可重叠k次最长重复子串.分层后排序贪心nlog(n)
[PKU 2774]Long Long Message 最长公共前缀
[PKU 1743]Musical Theme 不可重叠重复字串
[PKU 3261]Milk Patterns 可重叠K次的最长重复子串
[Usaco 1.3.1]calfflac 后缀数组+RMQ
八,哈希
挺喜欢hash的，可能是因为hash的运用比较灵活吧。现在对就对ac的几个题做个分类。
大整数的hash，含多个整数(这类题的hash函数比较灵活)
poj2875
poj1840
poj3640
poj3349
poj2002 key=(abs(p[i].x)*99983+abs(p[i].y)*13)%77777;
poj1200 （将字符串看成26进制数)
字符串的hash（有许多现成函数，选择合适的就行）
poj 2503
int ELFhash(char *key)
{
unsigned long h=0;
while(*key)
{
h=(h<<4)+*key++;
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%MOD;
}
数组的hash（有现成函数）
poj3274
int getkey(int *v,int k)
{
int i,p=0;
for(i=1; i<k; i++)
p=((p<<2)+(v[i]>>4))^(v[i]<<10);
p = p%prime;
if(p<0) p=p+prime;
return p;
}
全排列的hash （没有冲突的hash,利用全排列与逆序数列一一对应的原理）
poj1077
int getkey(int *seq)
{
int i,j,cnt,key=0;
for(i=0;i<9;i++)
{
cnt=0;
for(j=0;j<i;j++)
if(seq[j]>seq[i])
cnt++;
key+=cnt*fac[i]; // cnt<=i
}
return key;
}
HDU
hash一般用在搜索中用于判重
单纯考察hash的题目不多，
有些需要处理冲突
1904 最普通的
1800 需要处理冲突
1755 典型hash
1482 中途用到hash思想
1496 经典hash
2141 经典hash加强版
2024年1月14日 19:30
I definitely enjoying every little bit of it and I have you bookmarked to check out new stuff you post.