algoprog.kz

Интересная задача.

Все что нужно сделать, это посчитать суммарную площадь четырех прямоугольников на плоскости.

Прямоугольники задаются координатами противоположных углов.

Порядок решения: - Заведем двумерную матрицу [0...2000, 0...2000] и заполним ее нулями.

• Считав координаты, увеличим их на 1000.

• Заполни элементы нашей матрицы, попадающие в новый диапазон единичками.

• Количество единиц в матрице и есть ответ.

Примечание:

• Я решал ее на С++, где координаты не могут быть отрицательными, поэтому все увеличивал на 1000. Если язык, на котором вы пишете позволяет создать матрицу [-1000...1000, -1000...1000], то задача становится еще легче.
• При максимальном тесте, матрица будет содержать 2000*2000=4000000 элементов, так что с памятью и временем преблем не должно быть.
• Так, как нас интересуют только два возможных значения, то матрицу можно задать типом bool (boolean).

_Вроде все, надеюсь, что все понятно и хоть кому-нибудь это поможет._

Эту задачу можно решить при помощи RSQ (решение "втупую" может и не пройти). Просто строим бинарное дерево за O(N), затем пускаем цикл с 1 до N, и находим максимальную сумму (за O(NlogN)) на отрезке (1-i,i-N). В итоге эффективность нашего алгоритма будет примерно O(NlogN + N) = O(NlogN). ))

Вот самый простой способ нахождения суммы на отрезке за O(logN):

int rsq(int l, int r)
  {
    int ans=0,x,y; 
    x=l+n-1; y=r+n-1;

while(x<y)
{
if(x&1)  ans+=a[x], x++; 
if(!(y&1)) ans+=a[y], y--;

x/=2; y/=2;
}
if(x<y) ans+=a[x]+a[y];
else if(x==y) ans+=a[x];

return ans;

}