Counting Digits 2

2.0s 256M

You are given a sequence of length \(N\) consisting of positive integers \(a_1, a_2, \ldots, a_N\). Then \(Q\) queries follow. For the \(i\)-th query you are given three positive integers \(L_i, R_i, b_i\), and you must report how many times the value \(b_i\) appears in the subarray \([L_i, R_i]\) of \(a\).

The intended solution runs in \(O((N+Q)\log N)\) time or better.

Input

The first line contains two integers \(N\) and \(Q\).

The second line contains \(N\) positive integers \(a_1, a_2, \ldots, a_N\).

Each of the next \(Q\) lines contains three positive integers \(L_i, R_i, b_i\), describing one query.

Constraints

  • \(1 \le N, Q \le 5 \times 10^5\)
  • \(1 \le a_i, b_i \le N\)
  • \(1 \le L_i \le R_i \le N\)

Output

For each query, output a single line containing the answer.

Sample Input 1

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

Sample Output 1

3
1
1
2
0
1

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.