RubenAshughyan's blog

By RubenAshughyan, history, 6 weeks ago, In English,

This blog is to discuss the problems of Northwestern Russia Regional Contest round 2019 held on October 26.

The problems:

What was your approach on problem B (Bad Treap) ?

Read more »

  • Vote: I like it
  • +26
  • Vote: I do not like it

By RubenAshughyan, history, 9 months ago, In English,

Hi everyone. Today I encountered a data structures problem, which is a slight swist on standart segment tree problem.

You are given an array A of size N. N ≤ 10^5, A[i] ≤ 10^6, You need to process 3 types of queries

  1. Print the sum of all integers ai where L ≤ i ≤ R.

  2. Add x to each integer ai where L ≤ i ≤ R.

  3. For each integer A[i] where L ≤ i ≤ R, replace it with floor(sqrt(A[i])). Where sqrt(a) is the square root of a, and floor(b) is the integer value of b after removing everything on the right of the decimal point.

There can be Q≤20000 queries.

If we didn't have type 3 query, then we are left with standard lazy segment tree problem.

How to handle 3rd type queries?

Read more »

  • Vote: I like it
  • +46
  • Vote: I do not like it