主题

主题

 
   

3809:Gty的二逼妹子序列

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3809

Description

Autumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。

对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。

为了方便,我们规定妹子们的美丽度全都在[1,n]中。

给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n),对于m(1<=m<=1000000)次询问“l,r,a,b”,每次输出sl…sr中,权值∈[a,b]的权值的种类数。

Input

第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。

第二行包括n个整数s1…sn(1<=si<=n)。

接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。

保证涉及的所有数在C++的int内。

保证输入合法。

Output

对每个询问,单独输出一行,表示sl…sr中权值∈[a,b]的权值的种类数。

Sample Input

10 10

4 4 5 1 4 1 5 1 2 1

5 9 1 2

3 4 7 9

4 4 2 5

2 3 4 7

5 10 4 4

3 9 1 1

1 4 5 9

8 9 3 3

2 2 1 6

8 9 1 4

Sample Output

2

0

0

2

1

1

1

0

1

2

HINT

样例的部分解释:

5 9 1 2

子序列为4 1 5 1 2

在[1,2]里的权值有1,1,2,有2种,因此答案为2。

3 4 7 9

子序列为5 1

在[7,9]里的权值有5,有1种,因此答案为1。

4 4 2 5

子序列为1

没有权值在[2,5]中的,因此答案为0。

2 3 4 7

子序列为4 5

权值在[4,7]中的有4,5,因此答案为2。

建议使用输入/输出优化。


个人解法:

28MB……表示MLE一次。于是上不了树据结构了。

然后我们可以考虑莫队。

显然我们维护一个桶。需要支持单点修改与区间查询。用一个树状数组维护这个桶就可以了。

一次转移O(logn)。于是莫队复杂度为O(msqrt(m)logn)。时间会炸(没有亲测)。

于是我们考虑用一种修改很快,查询较慢的玩意?

(当然什么都不用,修改O(1),查询O(n)。这个显然不可靠的。)

于是我们使用分块来优化莫队。

分块单点修改可以实现O(1),区间查询支持O(sqrt(n))。于是转移变为了O(1)。那么总的时间复杂度变为O(msqrt(m)+msqrt(n))。

不过考场上想到一个带sqrt的想法以后,本蒟是不会管优化了……


代码如下:

https://code.csdn.net/snippets/2147617

 
 
评论