You are not logged in. Please login at www.codechef.com to post your questions!

×

segment tree

Can anyonre give me a hint how to solve this problem here!

asked 30 Aug '17, 01:04

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

edited 30 Aug '17, 01:05

An approach for this problem is explained here: http://codeforces.com/blog/entry/10183?#comment-156355.

(05 Feb '18, 20:23) shubhambhattar3★

You can solve this problem by using Offline solution method and by creating Balance Binary Search Tree incrementally.. First iterate over all queries and store for each index what is query on that.. While creating Balanced BST you can find out number of smaller elements till now in log(N) using Binary Search tree that we have made till that point, and store answer for that pair(i,k) in some dict ansThatWeFound. Now iterate through query again, for ans(i,j,k) = ansThatWeFound(j,k) - ansThatWeFound(i-1,k). Hope this was clear enough and was providing enough info to approach this question now.. :) I you have some doubt then you can ask that in comments..

link

answered 30 Aug '17, 01:24

kauts_kanu's gravatar image

5★kauts_kanu
1.1k110
accept rate: 19%

can i do this with fenwick trees ??
amm creating the tree with sorted subarray will cost me N log(n) log(logn)
and for each query it will cost log(n)*log(log(n))

(30 Aug '17, 22:28) phantomhive4★

Assuming that you are familiar with segment tree

You can solve this problem by building a segment tree, with a sorted sub-array in every vertex and then divide [l, r] into sub-segments, and do binary search on sub-segments.

link

answered 30 Aug '17, 01:19

a_d_i's gravatar image

2★a_d_i
1746
accept rate: 23%

Using sorted sub-array in every vertex will take $n^2 log(n)$ time, no?? If I am getting correctly what you are saying..

(30 Aug '17, 01:28) kauts_kanu5★

$\log(n)^2$ for each query

(30 Aug '17, 01:49) a_d_i2★

no.. while creating tree itself.. Can you post some pseudo code here..??

(30 Aug '17, 01:54) kauts_kanu5★
2

@kauts_kanu, this is also known as mergesort tree. But I had to use input via getchar_unlocked() to get overcome TLE, so be careful about that @phantomhive.

(30 Aug '17, 09:00) meooow ♦6★

Did not know about this.. thanks.. :)

(30 Aug '17, 15:46) kauts_kanu5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,755

question asked: 30 Aug '17, 01:04

question was seen: 525 times

last updated: 05 Feb '18, 20:23