Have you ever
wondered how many people trams transport annually in a city with a population
of ten million, where every third resident uses the tram twice a day?
Suppose there
are n cities on planet Earth that have tram systems.
Statistics enthusiasts have calculated, for each of these cities, how many
people were transported by trams over the past year. Based on this data, a
table was created in which the cities were initially sorted alphabetically.
Later, it turned out that the city names were not relevant for the statistical
analysis, so they were simply replaced with numbers from 1 to n.
The search
system that works with this data needs to quickly answer the following type of
query: is there a city among those numbered from l to r where exactly x people were
transported by trams over the year?
You are to
implement this query module.
Input. The first line
contains a single integer n (0 < n < 70000) – the number of cities.
The second line
contains n positive integers – the statistical data, where
the i-th number indicates the number of people transported by trams
in the i-th city over the past year. All values are positive
integers and do not exceed 109 – 1.
The third line
contains a single integer q (0 < q < 70000) – the number of queries.
Each of the next q lines contains a query described
by three integers l, r and x (1 ≤ l ≤ r ≤ n; 0 < x < 109).
Output. Print a string of q characters. The i-th
character should be ‘1’ if there exists
at least one city numbered from l to r where exactly x people were
transported by trams; otherwise, print ‘0’.
|
Sample
input |
Sample output |
|
5 123 666 314
666 434 5 1 5 314 1 5 578 2 4 666 4 4 713 1 1 123 |
10101 |
binary search
Let the array v
contain statistical data about the number of people transported by trams. For
each number of transported people x, store a vector of indices where
this value occurs. In other words, in the map representation p[x],
we keep the indices of the cities where exactly x people were
transported during the year.
A query of the
form (l, r,
x) is processed as follows:
·
If the value x is not present in the map
structure, we immediately print 0.
·
Otherwise, using a binary search (lower_bound),
find in the array p[x] the first index not less than l.
·
If the found index does not exceed r, then the
value x does indeed occur among the cities with indices from l to
r.
Example
Let us consider how the structure p
looks for the first example.
·
p[123]
= {1};
·
p[314]
= {3};
·
p[434]
= {5};
·
p[666]
= {2, 4};
For instance, to process the query (1, 5, 314), we need to perform the following steps:
·
Check
whether the array p[314] exists;
·
Then,
using binary search in the array p[314], find the smallest value not less than l
= 1. In this case, the value is 1;
·
Since
it does not exceed r = 5, the answer to the query is 1.
Let us define
the data structures used:
·
The array v stores statistical data on the number
of people transported by trams;
·
The map p contains, for each value x
occurring in the input array v, the list of indices (positions) where
this value appears.
vector<int>
v;
map<int, vector<int>>
p;
Read the input data.
cin >> n;
v.resize(n
+ 1);
for (i = 1; i <= n; i++)
{
cin >> v[i];
In city number i, v[i] people were transported. The cities
are numbered starting from 1.
p[v[i]].push_back(i);
}
Read the number of queries q.
cin >> q;
The answer will be generated in the string result.
result
= "";
Process the q queries (l, r, x) sequentially.
for (i = 0; i < q; i++)
{
cin >> l >> r >> x;
If no city has transported x passengers, record ‘0’ as the answer.
if
(p.find(x) == p.end())
{
result += '0';
continue;
}
It is necessary to determine whether the array p[x] contains at
least one number in the range from l to r. Search for the first
occurrence in p[x] that is not less than l.
vector<int>::iterator it = lower_bound(p[x].begin(), p[x].end(), l);
If such a number exists and it is not greater than r, record ‘1’ as
the answer.
if (it != p[x].end() && *it <= r)
result += '1';
else
result += '0';
}
Print thre answer.
cout << result << endl;