http://acm.pku.edu.cn/JudgeOnline/problem?id=1195

МОБИЛЬНЫЕ ТЕЛЕФОНЫ

ЗАДАЧА

Предположим, что в регионе Тампере базовые станции обеспечения мобильной телефонной связи четвертого поколения действуют следующим образом. Регион поделен на квадраты. Квадраты образуют матрицу размера SxS, строки и столбцы которой пронумерованы от 0 до S-1. В каждом квадрате находится базовая станция. Количество работающих мобильных телефонов внутри квадрата может меняться, так как телефоны могут перемещаться из одного квадрата в другой, и телефоны могут включаться или выключаться. В некоторые моменты времени каждая базовая станция передает головной базовой станции отчет об изменении количества работающих телефонов и свои координаты (номер строки и номер столбца соответственно).

Напишите программу, которая получает эти отчеты и отвечает на запросы о текущем общем количестве работающих мобильных телефонов в некоторой прямоугольной области.

ВВОД И ВЫВОД

Целочисленные данные вводятся из стандартного входного потока. Входные данные кодируются следующим образом. Каждая строка содержит одну команду. Команда состоит из кода и набора параметров (целых чисел) в соответствии со следующей таблицей.

Команда Параметры Значение
0 S Инициализирует матрицу размера SxS нулями. Эта команда выдается только один раз и должна быть первой командой.
1 X Y A Прибавляет к количеству работающих мобильных телефонов в квадрате (X, Y) число A. Число A может быть как положительным, так и отрицательным.
2 L B R T Запрашивает текущее суммарное количество работающих мобильных телефонов в квадратах (X,Y), где L ≤ X ≤ R, B ≤ Y ≤ T
3   Завершает программу. Эта команда выдается только один раз и должна быть последней.

Программа отвечает на каждый запрос (команду с кодом 2), записывая целые числа в стандартный выходной поток.

Значения всегда будут в допустимых пределах, так что нет необходимости их проверять. В частности, добавление отрицательного числа A не приведет к уменьшению количества телефонов в квадрате до значения, меньшего нуля. Индексы в матрице начинаются от 0, например, для матрицы 4x4, мы имеем 0 ≤ X ≤ 3 и 0 ≤ Y ≤ 3.

Ваша программа не должна ничего выдавать в ответ на команды, отличные от команд с кодом 2. Если поступила команда 2, то ваша программа должна ответить на запрос, выдав в стандартный выходной поток строку, содержащую единственное целое число.

ИНСТРУКЦИИ ДЛЯ ПРОГРАММИРОВАНИЯ

Далее в примерах целочисленная переменная last предполагается последней, считанной из строки, а целочисленная переменная answer содержит ваш ответ.

Если вы пишите программу на C++ и используете iostreams, то вам следует использовать следующие инструкции для чтения из стандартного входного потока и записи в стандартный выходной поток:

cin>>last;
cout<<answer<<endl<<flush;

Если вы пишите программу на C или С++ и используете scanf и printf, то вам следует использовать следующие инструкции для чтения из стандартного входного потока и записи в стандартный выходной поток:

scanf ("%d", &last);   
printf("%d\n",answer); fflush (stdout);

Если вы пишите программу на Pascal, то вам следует использовать следующие инструкции для чтения из стандартного входного потока и записи в стандартный выходной поток:

Read(last); ... Readln;
Writeln(answer);

ПРИМЕР

stdin stdout пояснение
0 4   Инициализируется матрица размером 4x4.
1 1 2 3   Значение в квадрате (1, 2) увеличивается на 3.
2 0 0 2 2   Запрашивается текущая сумма значений из прямоугольника 0 ≤ X ≤ 2, 0 ≤ Y ≤ 2.
  3 Ответ на запрос.
1 1 1 2   Значение в квадрате (1, 1) увеличивается на 2.
1 1 2 -1   Значение в квадрате (1, 2) уменьшается на 1.
2 1 1 2 3   Запрашивается текущая сумма значений из прямоугольника 1 ≤ X ≤ 2, 1 ≤ Y ≤ 3.
  4 Ответ на запрос.
3   Программа завершается.

ОГРАНИЧЕНИЯ

Размер матрицы SxS 1x1 ≤ SxS ≤ 1024x1024
В любом квадрате матрицы в каждый момент времени может находиться V работающих телефонов V 0 ≤ V ≤ 215 –1 (= 32767)
Изменение количества телефонов в квадрате матрицы A -215 ≤ A ≤ 215–1 (= 32767)
Количество команд во входном потоке U 3 ≤ U ≤ 60002
Максимальное суммарное количество телефонов во всей матрице M M= 230

В 16-ти из 20-ти тестов размер матрицы будет не более 512x512.

program PKU1195;
{$I-, s-, q-, r-}

const maxn = 1024;

type integer = longint;

var s: array[1..maxn, 1..maxn] of integer;
    n, x, y, k, x0, y0, x1, y1, order: integer;

procedure add(x, y, t: integer);
var k: integer;
begin
  while x <= n do begin
    k := y;
    while k <= n do begin
      inc(s[x, k], t);
      k := k + k and (k xor (k - 1));
    end;
    x := x + x and (x xor (x - 1));
  end;
end;

function calc(x, y: integer): integer;
var sum, k: integer;
begin
  sum := 0;
  while x > 0 do begin
    k := y;
    while k > 0 do begin
      sum := sum + s[x, k];
      k := k - k and (k xor (k - 1));
    end;
    x := x - x and (x xor (x - 1));
  end;
  calc := sum;
end;

begin
  repeat
    read(order);
    case order of
      0: readln(n);
      1: begin read(x, y, k); add(x + 1, y + 1, k); end;
      2:
      begin
        read(x0, y0, x1, y1);
        writeln(calc(x1 + 1, y1 + 1) + calc(x0, y0) - calc(x0, y1 + 1) - calc(x1 + 1, y0));
      end;
    end;
  until order = 3
end.