【czy系列赛】czy的后宫3

2014年7月19日3,7974

czy的后宫3

【题目描述】

上次czy在机房妥善安排了他的后宫之后,他发现可以将他的妹子分为c种,他经常会考虑这样一个问题:在[l,r]的妹子中间,能挑选出多少不同类型的妹子呢?

注意:由于czy非常丧尸,所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数,你懂得。

问题简述:n个数,m次询问,每次问[l,r]区间有多少个数恰好出现正偶数次

【输入格式】

第一行3个整数,表示n,c,m

第二行n个数,每个数Ai在[1,c]之间,表示一个Ai类型的妹子

接下来m行,每行两个整数l,r,表示询问[l,r]这个区间的答案

【输出格式】

有m行,表示第i次询问的答案

【样例输入】

5 5 3

1 1 2 2 3

1 5

3 4

2 3

【样例输出】

2

1

0

【数据范围】

共有10组测试数据

1-4组n,m=500,2000,5000,10000,c=1000

5-7组n,m=20000,30000,40000,c=10000

8-10组n,m=50000,80000,100000,c=100000

数据保证随机生成

【题解】

本题改编自bzoj作诗,但是不强制在线

算法1:n^2暴力

算法2:分块,同作诗

算法3:离线+树状数组

按照所有询问的左端点排序

一开始建树状数组,记录1-x的答案

now=1,从左往右扫

如果now<q[i].l,考虑删除a[now]对于答案的影响,若a[now]值为v

显然v1-v2即now到下一个v出现的位置,答案+1,

v2-v3答案-1,以此类推,用树状数组依次维护

now=q[i].l时记录下q[i].ana,即在树状数组中查询q[i].l-q[i].r的答案

询问每次是logn的,但是now指针向右移动时,花费的时间为a[now]在now之后中出现次数x*logn

但是由于数据是完全随机的,我们可以认为某一个数字出现次数是比较少的

算法4:同上

对于算法3,可以构造数据,某个数字出现次数很多使得其复杂度为n^2logn

所以我们可以采取一些办法使得算法变得“靠谱”

以√n为界,出现次数大于√n的数字不超过√n个

出现次数小于√n的可能有n个

每次查询q[i].l-q[i].r的时候,答案由两部分构成

1.出现次数小于√n的我们依然维护这些数对答案贡献的树状数组,直接在树状数组中查询 logn

2.出现次数大于√n的数,每一个数维护树状数组,我们可以得出q[i].l-q[i].r每一个数出现的次数,是偶数就将答案+1 √nlogn

总询问复杂度nlogn+n√nlogn

考虑删去一个数,它出现次数小于√n,则直接在答案树状数组上操作√nlogn

否则就在以这个数为次数建立的树状数组上操作logn

俩种操作最多都是n次,总复杂度nlogn+n√nlogn

复杂度和分块差不多

算法5:莫队算法

这个没学过的话自行百度,会的话应该分分钟水过的吧,复杂度n√n,常数小

 

 

  • Believe2015年7月18日 上午10:01 回复

    czy系列赛是什么??

    #1  
  • cyy4892015年7月21日 下午7:59 回复

    请问大神莫队算法和分块有什么区别?我一直以为是一样的。。。

    #2  
  • […] 而且不强制在线的话有很多做法,可以看我blog一道类似题目 czy的后宫3 […]

    #3  
  • 沙狼阿折2016年11月6日 上午11:58 回复

    分块的思想是什么啊

    #4