Segment Tree Practice 4

Points: 17

Time limit: 0.6s

Memory limit: 256M

Author:

Problem type

Given an array $A$ ~A~ of size $N$ ~N~, support the $Q$ ~Q~ of the following queries:

Count the number of elements appearing exactly once in the range $[l, r]$ ~[l, r]~.

$1 \le N, Q \le 2 \times 10^5$ ~1 \le N, Q \le 2 \times 10^5~

$1 \le l \le r \le N$ ~1 \le l \le r \le N~

$1 \le A_i \le N$ ~1 \le A_i \le N~

The first line contains $2$ ~2~ integers $N$ ~N~ and $Q$ ~Q~.

The second line contains $N$ ~N~ integers $A_1, A_2, \ldots, A_N$ ~A_1, A_2, \ldots, A_N~, the elements of $A$ ~A~.

The next $Q$ ~Q~ lines each contain $2$ ~2~ integers $l_i$ ~l_i~ and $r_i$ ~r_i~, representing a query on the range $[l_i, r_i]$ ~[l_i, r_i]~.

For each query output one integer on its own line, the answer to that query.

7 5
1 2 3 2 4 3 1
2 5
1 7
4 7
3 6
1 1

Comments

2

thomas_li commented on June 16, 2025, 12:25 p.m.

Is it possible to solve this problem using bitset?

2

thomas_li commented on June 16, 2025, 1:35 p.m.

I solved it with byte set: https://dmoj.ca/src/7195549

1

Publicly declaring my intention to cheat was a calculated risk, but boy am I bad at math commented on June 14, 2025, 11:16 p.m.

Is it possible to solve this problem using segment tree?

3

bruce commented on June 16, 2025, 2:18 a.m.

Yes. You can answer all the queries offline with segment tree.