hdu 4777 Rabbit Kingdom (树状数组+预处理)

https://vjudge.net/problem/47450/origin

题意:

有一个含有n个数的序列,m个询问。问 [l, r] 区间内与所有数都互质的数有几个?

思路:

想到了预处理每个数最左最右的,最远的互质的数的范围。。

之后对于询问区间[l,r],我们要知道 对于 i>=L && i <= R 并且 a[i].l<=L,a[i].r>=R的i的个数…

没有想到怎么维护,gg

 

转载一段题解:

先算出每个数的有效范围,l[i],r[i]代表与第i个数一直互质到的最左端和最右端。这个处理方法是,预处理出一张因子表。然后对每个输入的数,判断其因子出现的最接近它的位置。从左到右扫一遍求出l[i],从右到左扫一遍求出r[i];我们还需要用一个vector记录下左边界为i时的所有数。

我们思考一个范围内,当一个数的l[i]和r[i]都在范围之外时,这个数会被统计在内。反过来讲就是一个范围在一个数的边界之内,当前的数会被统计到范围之内。

我们先对问题进行离线处理,先根据问题的左边界排序。我们需要维护一个树状数组来统计和增减值。

然后我们按照i从1到n扫一遍,i代表的意义是左边界。

1. 当扫到第i个数时,我们统计左边界为i+1的问题(这样范围一定满足左边界,因为右边界接下来也进行了处理,所以可以直接统计)。

2.  我们还需要更新第i个数。i的意义是左边界,因为之后统计的问题左边界都大于i,都满足。所以我们找到所有左边界为i的数,将其+1处理。然后右边界-1处理。这样如果问题的边界大于右边界的话,这个数就不会统计在内。

3.  最后处理完i后,因为以后问题的左边界都大于i,所以第i个数不会再被统计了,所以我们要除去第i个数的影响,就是把其右边界+1(自身为什么不处理,因为处不处理都一样,不会在涉及到它本身了)

 

转载又一段题解:

先预处理出来每个数的贡献区间,每个数的贡献区间是 [左边最近不互质数的位置,右边最近不互质数的位置] ,现在问题就转化为了求区间 [L, R] 中有几个数的贡献区间能完整覆盖 [L, R] 区间。但是数据范围挺大的,可以考虑用树状数组离线处理来达到优化的目的。先对所有的查询进行排序 (按照L升序排列) ,然后从左到右依次处理。我们用树状数组区间和sum [L, R] 表示区间[L, R]中符合题意的有多少个数。假设现在需要查询 [L, R] 区间,我们可以考虑贡献区间L[i]<L的数,可以在i位置加 1,然后在R[i]位置减1。这样处理的话必须要保证L[i]小于查询区间L的值,以及i要在查询区间内。所以我们每次向后移动的时候,要在树状数组中减去当前位置的数对树状数组的影响,也就是进行操作 i 位置减1,R[i]位置加1. 分析到这里这个题目就变成了一个比较水的利用树状数组进行点更新,区间查询的题目了,也可以用线段树搞的。

 

hdu 5618 Jam’s problem again (cdq分治+BIT,三维偏序)

题目链接

题意:

If two point such as (xi,yi,zi) and (xj,yj,zj) xixj yiyj zizj, the bigger one level add 1

问每个point的level是多少。

思路:

cdq分治,先去重并统计相同的点的数量,需要注意要记录原id对应到了哪个新id

 

BZOJ 3262: 陌上花开 (cdq分治模板题,三维偏序)

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性

Output

包含N行,分别表示评级为0…N-1的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

 

思路:

第一发cdq分治,果然很好写。

cdq分治学习笔记

题目很裸,好像没什么好分析的。

代码风格的话,我是看lwt菊苣代码长大的

 

 

codeforces #413 C. Fountains (BIT维护前缀max)

题目链接

题意:有2种货币,分别为C和D.给出n种资源的代价和美丽度,每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买2个资源,问最大美丽度,不能的话输出0.

思路:首先显然三种情况。。。CC,CD,DD.

CD直接扫一遍。。重点是CC和DD

一开始思路错掉了。。全程写two pointer wa4…一直调。。

最后恍然大悟。。发现two pointer非常错啊。。。

其实正解也很简单?

先去跑步了orz

只要想办法维护每个代价的最大美丽度就好了(更准确得说,是维护小于等于某代价的最大美丽度)

直接BIT搞。维护一个前缀max…好像很稳啊?

不过我竟然对于BIT能维护前缀max吃了一惊?

以往都是用线段树来做这个操作的…想想大概是。。我把BIT的函数起名叫”Sum”的锅。。。

看起来就只能求Sum。。。。233333

 

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接

题意:给出n个数,q个查询,每组一个区间,询问区间中所有数的乘积的欧拉函数%1E9+7的答案是多少。

思路:这道题需要一点欧拉函数的知识。

phi(n)是欧拉函数,意义为小于等于n并且与n互质的数的个数。

To calculate the answer on every query let’s use the formula , where p1, p2, …, pk — all prime numbers which dividedn.

如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。

考虑两个数a,b的欧拉函数。

一开始考虑也许有什么性质。。。查了下欧拉函数的wiki
欧拉函数_维基百科
欧拉函数是积性函数(但不是完全积性函数。。因此必须phi(ab) =phi(a)*phi(b)成立当且仅当gcd(a,b)==1)

然而这里并不一定满足互质的条件。。。

 

再想一下。。。发现完全没必要由phi(a)和phi(b)得到phi(a*b)

直接把a*b看成一个数就好了。。。。

后面质因子乘积部分只需要把两部分的并在一起就好了。。。

所以根据上面欧拉函数的公式。。。答案分为两部分。。。

一部分是区间中所有数的乘积。。。

一部分是区间中所有数的不相同的素因子的p-1/p形式的乘积。。。

第一部分预处理前缀积即可。。。由于有%运算。。。所以除的时候需要计算逆元。。。

第二部分的做法同spoj_dquery解题报告

也是离线处理,把询问按照区间右端点排序升序排列,然后lst数组记录上次该数出现的位置。。。用bit维护一个从1到某个数的乘积。。。在撤销的时候同样需要逆元。。。

 

还要注意。。。太长的式子一定要分开写。。。。

因为写错括号顺序调了半天orz…

 

 

 

 

codeforces #351 D. Jeff and Removing Periods (线段树/树状数组判断位置成等差数列)

题目链接
题意:有n个数,每次可以删除掉数值相同并且所在位置成等差数列(只删2个数或者只删1个数应该也是可以的),删掉这些数以后可以将剩下的数重新以任意顺序排列,称为一次操作。现在给出m个询问,每个询问一个区间[l,r],问删光区间[l,r]中的数最少需要的操作次数。

思路/题解:由于第一次操作之后可以重排,那么把相同的数放在一起得到一个位置的公差为1的等差数列,之后的答案显然是元素个数。所以需要判断初始的时候,是否能一次删光某个数值的数,也就是需要判断初始时刻是否有某个数出现的所有位置组成一个等差数列。

(去icpc-camp的论坛问了一波。。。链接在这里)

之前刚刚学了判断一个区间中不同的数有多少个的姿势。。。

所以问题就在于如何判断这个等差数列。。。

参考叉姐的思路,我的思路如下:

就是从左往右扫的时候,对于当前的数,看该种数在当前位置左边且离当前位置最近的不能和当前位置构成等差数列的数的位置,然后用树状数组判断这个位置和当前查询区间的左端点的关系,如果左端点在这个位置左边,就不是等差,否则就是等差。

上面是判断一种数的情况。。。我要找到一种数满足题意即可。。

具体做法:

从左到右扫描每个元素,对于每种数字,肯定是有最长的一段后缀是等差数列,假设是 xx 个,那么左端点落在第 x + 1x+1 个后,这种数字就是全是等差数列。
我们可以拿一个树状数组把从第 (x + 1)(x+1) 个数往后全部 +1,询问时只要询问某个元素是不是 >0 就可以了。

 

顺便说一句:叉姐人真的好nice啊。。本来昨天大概找了大半天题解。。看了代码也没看懂。。。

然后晚上去icpc-camp的论坛上问了一波。。。

然后茶姐的回复窝仍然看不懂。。。。。

感觉窝问的应该不是什么困难的问题(虽然我想了好久都想不出)。。。

所以纠结了好久要不要再问一下叉姐。。。。

最后还是问了。。。结果叉姐非常热心而又详细地回答了我。。。。

真是让我这种蒟蒻感动不已啊。。。。orz

怪不得人人爱叉姐。

 

 

codeforces 220 E. Little Elephant and Inversions (树状数组+尺取)

题目链接

题意:

how many pairs of integers l and r are there, such that 1 ≤ l < rn and sequence b = a1a2alarar + 1an has no more than k inversions.

我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。

其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,r的对数。

思路:尺取+树状数组。

枚举l,每次找到最小的满足题意的r,对答案的贡献是n-r+1,然后用两个树状数组,分别维护增加或者减少一个树的时候,前半段和后半段对逆序数的影响。

 

 

BZOJ 3289 Mato的文件管理 (莫队算法套树状数组)

http://www.lydsy.com/JudgeOnline/problem.php?id=3289

题意:中文题目,简单来说就是求某一区间内的逆序对数。

思路:逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。

还有这题没给数据范围但是需要离散化。。。不然会re…
 

 

codeforces 522 A. Vanya and Table

http://codeforces.com/problemset/problem/552/A
题意:一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。
思路:树状数组搞得…然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。

hdu 1394 Minimum Inversion Number (树状数组 逆序对)

题目链接

题意:
这题是问一个长度为n的循环数组中,逆序对最少的个数。。。
我们可以先用树状数组求出初始的数列的逆序对。。。
然后其他的可以通过递推得到。。。。
当a[i]从处于位置1而被放到最后的时候。。。
cnt = cnt -a[i]+n-a[i]+1;
然后取所有cnt的最大值就行。

hdu 5480|| bestcoder   #57 div 2 Conturbatio(前缀和||树状数组)

比较水.
唯一一点需要注意的是…
可能有重复元素…
因为我的思路是用两棵一维树状数组搞..
每个点标记为1
然后看矩形的两个方向中是否至少有一个方向上和等于长度…
所以这样如果有重复元素的话,不处理会出错.. 
 
但实际上又没修改..直接前缀和就好了...
树状数组个毛线...
不过看到还有人线段树搞得233333
 
 

bestcoder #56 div 2 C Clarke and puzzle (nim游戏 树状数组)

比赛的时候没过.还以为是树状数组写残了.
但实际上是有自己不知道的东西.
这种博弈叫 nim游戏
所以这是一个二维的nim游戏.
nim游戏的性质是xor 和为0必败,否则必胜.
xor和也有前缀和性质,所以可以用树状数组维护.

hdu 3333 Turing Tree (求区间中不相同数的和,离线+线段树/树状数组)

题目链接

喵呜,离散树状数组。

这道题由于相同的值加和的时候只算一次,所以比较伤脑筋==

怎么办呢?

我们发现对于一个值,由于相同的只算一次,所以在任意时间内,这个值只需要出现一次。

如果我们从作往右将原数组更新到树状数组,如果某个值之前出现过,那么我在更新当前的时候,还需要删掉之前那个。

这样就可以保证当前的序列中一个值只出现了一次,而且位置更新成最后出现的位置。

如果只出现一次的话那就又是我们喜闻乐见的那个熟悉的树状数组了呢 喵呜!

但是这样删掉前面出现的元素真心大丈夫? 万一之后又查询了之前你删掉的点岂不是整个人都萌萌哒了?

 

所以我们可以按照查询区间的又断点排序,保证前面删掉的点以后不会再被查询。

也就是按照顺序,从左往右,边查询,边更新原数组到树状数组。

由于查询区间是无序的,按照右端点排序之后打乱了原来的查询顺序,所以要离线操作。

由于查询区间是无序的,按照右端点排序之后打乱了原来的查询顺序,所以要离线操作。

由于查询区间是无序的,按照右端点排序之后打乱了原来的查询顺序,所以要离线操作。


重要的事情说三遍。

所谓离线操作,就是查询的时候不直接输出答案,而是将答案存起来,然后最后一起输出。

 

我们需要开一个数组pre [x] 记录x这个数的上一个位置,初始为-1

由 x的范围太大,数组存不下,所以要离散化。

离散化是为了记录一个数上次出现的位置!

注意要开LL 。

 

update:20160916,写了个线段树的版本。

hdu 3584 Cube (三维树状数组,更新区间,查询单点)

三维树状数组
容斥那里注意一下。
多组数据因为忘记清空c数组而wa了1次,细心!

poj 2155- Matrix (树状数组,二维,更新区间,查询单点)

1

和上一道类似,也是更新区间,查询单点。
用到了容斥原理。