文理学院程序设计在线练习


mo's algorithm

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 13   Accepted Submission(s): 13
Problem Description

We all know that a problem is hard when it requires more than one algorithm in the same moment.
But we still tend to believe bravery can help us overcome difficulties.
The result of this problem will depend on how brave you are.
You have an array a and its’s size equals n.
There are exactly n positive constant number in your array.
Now you are faced with q query which consists of four integer: L1, R1, L2, R2.
Please answer how many different pair(i, j) where L1 <= i <= R1 and L2 <= j <= R2 and a[i] = a[j].
We consider two pair is same if and only if they look the same completely.
For example, (3, 3) is different from (3, 5).
(3, 5) and (3, 5) look the same.
Attention![L1, R1] may intersect with [L2, R2]

Input

An integer T on the first line representing there will be T test cases(1 <= T <= 100)
An integer n on the second line representing your array’s size.(1 <= n <= 100)
There are exactly n positive integers ai on the third line separated by space, each represents the ith element.(1 <= ai <= 100)
An integer q on the fourth line representing that there will be q query waiting for you.
Q lines follows, each contains four integer: L1, R1, L2, R2.
1 <= L1 <= R1 <= n
1 <= L2 <= R2 <= n

Output

For each query, print an integer respecting your answer in one line.

Sample Input
1
5
1 2 3 2 1
4
1 1 5 5
1 5 1 5
1 2 4 5
1 3 3 5
Sample Output
1
9
2
3
Hint

All legal pair(i, j) of the first query:(1,5)
All legal pair(i, j) of the second query:(1,1),(1,5),(2,2),(2,4),(3,3),(4,2),(4,4),(5,1),(5,5)
All legal pair(i, j) of the third query:(1,5),(2,4)
All legal pair(i, j) of the fifth query:(1,5),(2,4),(3,3)
Someone said : “Inclusion-exclusion principle + Off-line algorithms +Mo’s algorithm,now you are accepted.”

Source

2019绍兴联赛