CSES 1143

Solved with significant help

Started off originally thinking i could get away searching for the first hotel with enough capacity i.e. the lowest capacity hotel enough to house

Then I realised that wasn’t what the question was asking

Learned segment trees, specific implementation details are still shaky.

Each seg tree has build, query, and update.

for build:

you have a node left and right. the first node covers the entire tree.
you split it into left and right, and recurse left and right all the way down until you hit the base case.
then the base case is just itself.

For query, check the current node and see if the current node is greater than or equal to the request, and if the current node is less than, then it’s simply impossible. Otherwise, check the left node and see if it’s greater than, and then just keep recursing down and always try to go left until you get down to where left is equal to right, and then that’s the leftmost node that satisfies it.

For update, you have to go all the way down to the bottom, change it, and then go back up. Find which node you’re looking for by checking if the current middle is less than or greater than the position of the node you want to change, and then recurse down. And then if you hit the base case, which is node is equal to position, then you set that node, you set the value of that node, and then as you’re returning back up, you just build the tree the same way you would in the build function, where you take the max of the two child nodes.

Had to bump max values to 9e5+5 to pass because seg tree arrays needs 4n memory

CSES 1649

so this looks like a segtree but just keeping the minimum value.

i recognized the segtree bit but didn’t understand how to implement query.

update is identical to regular update, build is the same except you just take the min.

query is the special bit. you have to return INF if the query is fully outside the bounds to ensure that that wrong answer doesnt propagate back up through the tree. if the node is within the bounds then you just return the min in the bounds. otherwise you keep subdividing.

CSES 1648

solved without help

straightforward segtree, just modify query

query was modified by two cases: does the current range sit inside the entire query? and does it sit entirely outside the query?
and then just recurse into the two halves if the condition isn’t met.