| Problem description | | Progress |
|
Темы:
Mo algorithm
You are given an array of integers A of length n.
It is necessary to answer m queries of the form "report the number of different numbers of a subsegment of array A from the element with index l to the element with index r" (both boundaries of the subsegment are included, the array is numbered from one).
Input:
The first line contains two numbers: n - the number of array elements and m - the number of requests (1 <= n, m <= 105).
The second line contains n integers Ai - array elements (0 <= Ai <= 106).
Then there are m lines, each containing two numbers l and r - the boundaries of the subsegment for each query (1 <= l <= r <= n).
Output:
In a single line print m space-separated numbers - for each query, the number of different numbers on the corresponding subsegment.
Example:
| Input |
Output |
7 5
1 3 1 2 2 4 1
1 3
4 5
37
24
77 |
2 1 3 3 1 |
| |
![]()
|
|
Темы:
Mo algorithm
Formula derivation
There is an array of natural numbers a1, a2, ..., an. Consider some of its subarrays al, al + 1, ..., ar, where 1 ≤ l ≤ r ≤ n, and for each natural number s denote by Ks the number of occurrences of the number s in this subarray. Let's call the cardinality of a subarray the sum of the products Ks·Ks·s over all distinct integers s. Since the number of different numbers in the array is finite, the sum contains only a finite number of non-zero terms.
It is necessary to calculate the cardinalities of each of the t given subarrays.
Input
The first line contains two integers n and t (1 ≤ n, t ≤ 200000) — the length of the array and the number of requests, respectively.
The second line contains n natural numbers ai (1 ≤ ai ≤ 106) — array elements.
The next t lines contain two positive integers l and r (1 ≤ l ≤ r ≤ n) — indexes of the left and right ends of the corresponding subarray.
Imprint
Print t lines, where the i-th line contains the only natural number — cardinality of the i-th query subarray.
Examples:
| Input |
Output |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1
27
16
27 |
20
20
20 |
| |
![]()
|
|
Темы:
Mo algorithm
Prefix sums(minimums, ...)
Evan has a favorite number k and an array ai of length n. Now it asks you to answer m requests.
For each query given by a pair of numbers l and r, it is required to find the number of pairs of integers i and j such that l ≤ i ≤ j ≤ r and xor of numbers ai , ai + 1, ..., aj is k.
Input:
The first line contains integers n, m and k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 106) — the length of the array, the number of requests, and Evan's favorite number, respectively.
The second line contains n integers ai (0 ≤ ai ≤ 106) — Evan's array.
Then there are m lines. The i-th line contains numbers li and ri (1 ≤ li ≤ r< sub>i ≤ n) defining the i-th query.
Output:
Print m lines, the answers to the questions in the order they appear in the input.
Examples:
| Input |
Output |
6 2 3
1 2 1 1 0 3
16
3 5
| 7
0 |
5 3 1
1 1 1 1 1
15
24
1 3
| 9
4
4 |
| |
![]()
|
|
Темы:
Mo algorithm
Segment tree, RSQ, RMQ
Given a permutation of n elements.
Answer m queries about the number of inversions for a permutation subsegment from l to r.
An inversion is a pair of indices i, j such that i < j and ai > aj, where ai is the i-th element of the permutation.
Input:
The first line contains the number n (1 <= n <= 105).
The second line contains a permutation of n elements (the elements of the permutation are pairwise distinct integers from 1 to n).
The third line contains number m (1 <= m <= 105).
The next m lines contain two integers l and r - the bounds of the query (1 <= l, r <= n).
Output:
Print m lines - the answers to these queries.
Examples:
| Input |
Output |
5
4 5 2 3 1
3
1 3
3 5
15 |
2
2
8 |
6
5 2 4 3 1 6
3
46
25
15 |
1
4
8 |
| |
![]()
|