Number of elements less than or equal to current number in a given range.

Правка en5, от atlasworld, 2019-02-12 23:40:21

You , are given an array of n elements and q queries . Both n and q can range upto 10^5 , and 1<=a[i] <= 10^9.

how to find / count all the elements less than a given element in each query .

queries are in the form of l , r , x where x is number and l and r are starting and ending indices.

Example: index 1 based

a[] = {5 , 3 , 2 , 2 , 3 , 1 , 2 , 9 , 10 , 2 }

q1 = 5 9 5

ans = 3 { 3 , 1 , 2}

q2 = 1 4 2

ans = 2 {2 , 2 }

The problem gives a feel of segment tree , but how to solve it using ST ?

any idea.

#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en5 atlasworld 2019-02-12 23:40:21 2
en4 atlasworld 2019-02-12 23:39:29 121
en3 atlasworld 2019-02-12 23:38:33 8
en2 atlasworld 2019-02-12 23:38:13 36
en1 atlasworld 2019-02-12 23:37:52 523 Initial revision (published)
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8136484026908875, "perplexity": 2251.7936978629637}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-39/segments/1568514574501.78/warc/CC-MAIN-20190921125334-20190921151334-00530.warc.gz"}