Codeforces 678F - Lena and Queries

Problem Statement:
http://codeforces.com/contest/678/problem/F

Summary:
There are n <= 300000 queries of the form: add lines ax+b, remove line ax+b, and the maximum intersection between vertical line x = q and all lines.

[Square Root Decomposition] Codeforces 617E. XOR and Favorite Number

Problem Statement:
617E. XOR and Favorite Number

Solution:
Spent quite a long time trying to solve this problem using segment tree and suffix/prefix ideas... So it turns out that this problem is solvable using a new technique (to me)!

Square Root Decomposition
The type of problem that can be solved using this technique: Given an array A of numbers N, and a set of M queries in the form (i, j), find the maximum, minimum, sum, mean, or mode (or some other aggregate function), of A[i], A[i+1], ..., A[j].