spoj DQUERY – D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接
题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。

思路:离线处理+线段树的做法不多说了:

之后补一个主席树的做法

先来补一个莫队的做法。

因为a[i]<=1E6,可以很方便得统计每个数出现的次数,update的时候,如果是1变成0,那么区间中不同的数的个数减1,如果是0变成1,那么区间中不同数个数+1

 

补一个在线的做法,可持久化线段树,其实思路和离线线段树几乎一样。

 

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

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

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

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

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

 

hdu 4638 Group

http://acm.hdu.edu.cn/showproblem.php?pid=4638
题意:给定一个序列,序列由1-N个元素全排列而成,求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。
思路:增加一个元素,如果它两边的元素都出现了,那么段数-1(相当于把两段连接起来合并成了一段),如果两边元素都没有出现,那么段数+1.反过来,减少一个元素时,如果两边元素都出现了,俺么段数+1(相当于把完整的一段断开成两段),如果两边元素都没有出现,那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000,所以判断某个元素是否出现开一个100000大小的布尔数组即可(我竟然傻逼得去用set….然后华丽丽得TLE了2333)

选区_019

 

莫队算法总结

写了几道莫队,总结下。
目前只会区间莫队。。树上莫队以后再补。

莫队算法学习

说说我自己的理解:
莫队算法是一类用来处理离线静态区间问题的算法。
必须是离线,而且对区间没有修改。
还要满足,如果我们知道区间[l,r]的答案,那么知道区间[l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案都是平凡的。。也就是O(1)可以实现才可以。

本质的话。。感觉就是分块+暴力? 通过离线操作,把查询按照某种顺序均分使得复杂度降低。

除了bzoj的权限题。。。区间莫队基本都A掉了。

hdu 5145 NPY and girls

http://acm.hdu.edu.cn/showproblem.php?pid=5145
题意:有n个女孩,编号1..n,第i个女孩在第a[i]个教室,m次访问,每次访问编号[L,R]的女孩,处于同一个教室的女孩一次只能访问一个,问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。

思路:正好刚刚听完学堂在线上的组合数学的那一节,讲到有重复元素的不重复排列的个数的计算方法:可以先将所有元素看成不重复,再除以每个元素的重复度的阶乘(重复度定义为每个元素个数)。

增加一个元素的影响是,乘一个增加的长度,并且除以该元素的重复度(因为每增加一个元素就要除以以此重复度,那么当同一元素c增加到第i次时,除以的就是i的阶乘),减少一个元素的影响正相反。 两种改变都可以O(1)实现,因此可以上莫队。

之前要预处理下逆元。

 

 

 

codeforces #340 div 2 E XOR and Favorite Number

http://codeforces.com/contest/617/problem/E

题意:给出n个数,m个查询,每个查询给定l,r,问在区间【l,r】内,有多少对i,j,满足i^(i+1)^(i+2)^…^j的值为给定的常数k.

思路:学了莫队算法以后。。。这题果然是莫队的一眼题。

入手点是,知道异或也像加一样有前缀和性质。如果我们处理一个按照异或规则的前缀和数组sum[i]=sum[i-1]^a[i],那么i到j的异或和就是sum[i-1]^sum[j]  (x^x==0,因此a[1]到a[i-1]的异或和被去掉了)

因此我们要找的就是区间内有多对i,j满足sum[i-1]^sum[j]==k,也就是sum[i-1]==k^sum[j]这和hdu 5213 a=k-b有如此类似的形式,做法也是类似的。

由于对于每个j,找的是i-1,在处理的时候记得将区间左端点-1,

最重要的一点是,莫队的添加和删除操作最好分开写,至少根据d的正负写个if else,因为顺序不一定相同。

最后一个注意的是,可能会爆int ,所以要用long long

 

 

 

hdu 5213 lucky (莫队算法)

http://acm.hdu.edu.cn/showproblem.php?pid=5213
题意:n个数,m个查询,每个查询由4个数l1,r1,l2,r2构成,询问分别从[l1,r1]和[l2,r2]中各取一个数,和为给定的常数k的方案数。

思路:首先分别由两个区间取数不好搞,我们可以用容斥原理对区间变换。这是这道题最关键的一步。

官方题解:这道题需要一些莫队算法的知识 定义记号f(A,B)f(A,B)表示询问区间A,B时的答案 用记号+表示集合的并 利用莫队算法我们可以计算出任意f(A,A)f(A,A)的值 不妨假设A=[l1,r1],B=[l2,r2],C=[r1+1,l2-1]A=[l1,r1],B=[l2,r2],C=[r1+1,l21]容易知道(并没有很容易f(A,B)=f(A+B+C,A+B+C)+f(C,C)-f(A+C,A+C)-f(C+B,C+B)f(A,B)=f(A+B+C,A+B+C)+f(C,C)f(A+C,A+C)f(C+B,C+B) 因此一个询问被拆成四个可以用莫队算法做的询问 总的时间复杂度为O(msqrt(n))O(msqrt(n))

然后就是莫队算法的内容。值得一提的是,被拆成的四个子询问不必做四次莫队,可以合在一起,因为每一次询问对答案的贡献都不会受顺序影响,而且这样用时更短。

然后初始构造的时候用构造函数比赋值要方便许多。

还要记得多组数据记得清空各种数组。。。(因为忘记清空ans数组wa到死。。。)

最最关键的是,对于求两个数a+b==k这类问题(不一定是加,就是和两个数满足一个关系的时候),我们可以转换思维。a==k-b.也就是统计的时候是cnt[b]++,更新答案的时候,由于现在是b,我需要找有多少个a,也就是多少个k-b,所以是ans+=cnt[k-b];(要注意保证k-b>0)

 

 

codeforces 220 B. Little Elephant and Array

http://codeforces.com/contest/220/problem/B

题意:n个数,m个查询区间,对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。

思路:首先,a[i]很大。。。但是n最大才1e5…每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次,上莫队算法。

 

codeforces 86 D. Powerful array (莫队算法)

http://codeforces.com/problemset/problem/86/D

题意:Ks为区间内s的数目,求区间[L,R]之间所有Ks*Ks*s的和

思路:莫队算法,和小z的袜子差不多。不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。

再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多==

选区_016

 

 

(莫队算法的学习)bzoj 2038 [2009国家集训队]小Z的袜子(hose)

2038: [2009国家集训队]小Z的袜子(hose)

Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 5327 Solved: 2461
[Submit][Status][Discuss]
Description

作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数N和M。N为袜子的数量,M为小Z所提的询问的数量。接下来一行包含N个正整数Ci,其中Ci表示第i只袜子的颜色,相同的颜色用相同的数字表示。再接下来M行,每行两个正整数L,R表示一个询问。

Output

包含M行,对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1,否则输出的A/B必须为最简分数。(详见样例)

Sample Input

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

Sample Output

2/5

0/1

1/1

4/15

【样例解释】

询问1:共C(5,2)=10种可能,其中抽出两个2有1种可能,抽出两个3有3种可能,概率为(1+3)/10=4/10=2/5。

询问2:共C(3,2)=3种可能,无法抽到颜色相同的袜子,概率为0/3=0/1。

询问3:共C(3,2)=3种可能,均为抽出两个3,概率为3/3=1/1。

注:上述C(a, b)表示组合数,组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。

【数据规模和约定】

30%的数据中 N,M ≤ 5000;

60%的数据中 N,M ≤ 25000;

100%的数据中 N,M ≤ 50000,1 ≤ L < R ≤ N,Ci ≤ N。

中文题目,不解释了。
思路:分块+莫队算法。http://blog.csdn.net/bossup/article/details/39236275
这篇博客讲得很清楚。看完之后自己写的。。调了大概两个小时。。。?感觉有些理解了。
注意的是,如果最后分子为0,那么分母要赋值成1,而且分子为0的时候不要去求gcd…