标签归档:treap

HPU 1193: Interval(查询区间长度大于特定值且区间和大于特定值的区间个数)

题意就是题目上说的那样。。。给出一个n个数的序列,对于这个序列询问区间长度\(>=L\)且满足区间和\(>=M\)的区间的个数。数组下标从\(1\)开始,\(N\leq 10000,-100000\leq M,a[i] \leq 100000\)。

很久之前和ClearY吃饭的时候讨论的,后来她居然弄到校赛里面去了。。。

维护出来一个前缀和,那么对于位置\(pos\)来说,对答案的贡献就是位置\(i\)满足\(i <= pos-L\),而且\(sum[pos]-sum[i] >= M\)。那么我们从前往后扫,维护一棵平衡树,对于每个位置\(i\)找到他往后的\(L\)个位置\(pos\),查询比\(a[pos]-M\)小于等于的数有多少个就好了。这个treap写个rank函数就好了。

 

 

BZOJ 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居(treap+并查集)

Description

了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l≤Xi,Yi≤[1..10^9];Xi,Yi∈整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:
  1.两只奶牛的曼哈顿距离不超过C(1≤C≤10^9),即lXi – xil+IYi – Yil≤C.
  2.两只奶牛有共同的邻居.即,存在一只奶牛k,使i与k,j与k均同属一个群.
    给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

Input

   1行输入NC,之后N行每行输入一只奶牛的坐标.

Output

仅一行,先输出牛群数,再输出最大牛群里的牛数,用空格隔开.

Sample Input

4 2
1 1
3 3
2 2
10 10

* Line 1: A single line with a two space-separated integers: the
number of cow neighborhoods and the size of the largest cow
neighborhood.

Sample Output

2 3

OUTPUT DETAILS:
There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.

维护连通块有个直观的想法就是用并查集,但是O(n^2)连边的话肯定爆炸。想到BZOJ 4152这个题目通过点只连和自己距离最近的点把连边复杂度降为O(n),类似我们只需要找到某个点和它曼哈顿距离最近的两个点相连即可。但是。。。并不知道该怎么找。。。
查了一下,发现了一个曼哈顿距离转换为切比雪夫距离的方法:设一个点为A(x,y),把他的坐标变换为A'(x+y,x-y)。这时候原来两点间的曼哈顿距离就恰恰转换为了新坐标系下两点的切比雪夫距离即:max(|x1-x2|,|y1-y2|)。
这样的好处在于我们可以把x,y这两维拆开考虑了。由于我们已经按照切比雪夫距离来计算了,那么先把所有点按照x升序排序。然后维护一个队列,这个队列里的元素x坐标之差不超过C,类似于滑动窗口的处理。至于y坐标,我们考虑把队列里的所有点的y坐标加入到一棵平衡树内,这样的话我们可以在logN的时间内查出前驱和后继,再进行判断前驱和后继的y坐标和该点的距离是否在C的范围内。只需要连前驱和后继即可。这个就可以用并查集来做了。
所以,我写了棵双关键词的treap和并查集,太久没写过treap了,调了好久的bug。。。。

 

BZOJ上的USACO 第一弹

听说刷BZOJ上的USACO题目比较涨rank,于是我也开始了开心的划水生活~在这里贴一些题目的代码和思路,如果感觉比较好的题目用★标注出来,也会单独写写。

现在做了几题:

50/50

终于填完了,写题写的好慢啊QAQ。再弄个第二弹。

继续阅读