主题

主题

 
   

Lucky

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5213

Problem Description

WLD is always very lucky.His secret is a lucky number K.k is a fixed odd number. Now he meets a stranger with N numbers:a1,a2,...,aN.The stranger asks him M questions.Each question is like this:Given two ranges [Li,Ri] and [Ui,Vi],you can choose two numbers X and Y to make aX+aY=K.The X you can choose is between Li and Ri and the Y you can choose is between Ui and Vi.How many pairs of numbers(X,Y) you can choose?

If WLD can answer all the questions correctly,he'll be the luckiest man in the world.Can you help him?

Input

There are multiple cases.(At MOST 5)

For each case:

The first line contains an integer N(1≤N≤30000).

The following line contains an integer K(2≤K≤2∗N),WLD's lucky number.K is odd.

The following line contains N integers a1,a2,...,aN(1≤ai≤N).

The following line contains an integer M(1≤M≤30000),the sum of the questions WLD has to answer.

The following M lines,the i-th line contains 4 numbers Li,Ri,Ui,Vi(1≤Li≤Ri<Ui≤Vi≤N),describing the i-th question the stranger asks.

Output

For each case:

Print the total of pairs WLD can choose for each question.

Sample Input

5

3

1 2 1 2 3

1

1 2 3 5

Sample Output

2

Hint

a1+a4=a2+a3=3=K.

So we have two pairs of numbers (1,4) and (2,3).

Good luck! 


题目大意:

给出一个长度为n的区间,给出一个常数k,给出m个询问(l,r,x,y),查询在(l,r)中取一个点p,(x,y)中取一个点q,使得A[p]+A[q]=k的有序点对的个数。


个人解法:

最开始没有注意有序点对……然后瞎改了好久。

刚开始想的时候,由于一次询问是4个参数,直接把莫队否定了。后来想分块似乎不是那么好做,预处理也不太妙。想到可以分别莫队,分别维护桶。然后又不会查询,均以失败告终。

瓶颈在于4个参数。

猛然发现这是计数问题。于是想到可减!

然后我们发下可以处理前缀。比方说查询(l,r,x,y)可以变为查询(r,x,y)-(l-1,x,y)。

问题变得简单起来。

莫队的话,可以继续拆分,变为查询(r,y)-(r,x-1)这样的。然后就变为了2个参数,很好维护。

自己尝试了分块预处理的做法:

  1. SumF[x][y]表示第一个数字在x这个块,第二个数字在[1..y]的块的答案。

  2. G[x][y]表示[1..x]的块中y的个数。

然后考虑查询(q,x,y),表示第一个数字在[1..q],第二个数字在[x..y]的方案数(q,x,y均为端点):

  1. 整块-整块:枚举到q为止的块bq,然后用SumF来计算对应在[x..y]区域里面的整块[bx+1..by-1]这一部分对答案的贡献,即SumF[bq][bx+1..by-1]。

  2. 零散-零散:然后[1..q]的末尾还剩下一些小部分。[x..y]末尾还剩下一些小部分。拿出一个当桶,另一个扫描即可。

  3. 零散-整块:拿G数组统计即可。

以为常数可能有一点惊人。然而莫队的常数更加惊人。A了以后也不是自己想象的那么慢……


代码如下:

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

 
 
评论