All submissions for this problem are available.
A segment tree is built to perform queries in the range 1 to N. The following pseudo code counts the number of nodes which return a value when the tree is queried from l to r:
cnt = 0
Now, for a given N, find the array A1, A2 .... Ak where Ai is the number of distinct segments(l,r) when
query(node, start, end, l, r):
if(start > r or end < l):
if(start >= l and end <=r):
cnt = cnt + 1
mid = (start + end)/2
query(2*node, start, mid, l, r)
query(2*node+1, mid+1, end, l, r)
cnt = i.
Input:The first line of input contains a single integer T denoting the number of test cases. The only line of each test case contains a single integer N denoting the range
Output:For each test case, print two lines. First line contains the value of k, where k is the maximum index such that A[k] != 0 . Next line contains k space separated integers denoting the elements of array A.
- 1 <= T <= 10
- 1 <= N <= 50000
9 4 2
|Tags||dynamic-programming, gvaibhav21, insomnia18, segment-tree|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions