Для понимания, решим вспомогательную задачу: $S=n$, $x_1=x_2=dots=x_n= 1$. Утверждается, что в таком случае заплаченная сумма не зависит от порядка действий, и равна $(n(n-1))/2$. Несложно показать по индукции.

Из этого можно догадаться, что если ответ достижим, то он не зависит от порядка действий. Можно провести аналогию с графами: положим S = $sum x_i$. Изначально есть полный граф на $S$ вершин, а после всех действий должен остаться граф, состоящий из полных графов на $x_1, x_2, dots, x_n$ вершинах без ребер между ними. Тогда, стоимость операции - количество рёбер между двумя частями, которые мы разбиваем. Тогда, итоговая стоимость - количество рёбер, которые мы стерли. Понятно, что количество стертых ребер не зависит от порядка действий. 

В таком случае, критерий существования ответа: $S >= sum_(i=l)^r x_i$, тогда с предподстчетом префиксных сумм и префиксных сумм квадратов, можно будет овтечать на запросы за $O(1)$.