المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۲:سوال ۱۹

سوال ۱۹

در هر خانه‌ی یک جدول $n\times n$، یک عدد صحیح با قدر مطلق کم‌تر از ۱۰۰۰ نوشته شده است. در هر $Query$، یک مستطیل داده می‌شود و برنامه‌ی شما باید عدد مربوط به آن را حساب کند. مستطیل با خانه‌ی بالا و سمت چپش و خانه‌ی پایین و سمت راستش مشخص می‌شود. به عبارت دیگر، اگر $a_{ij}$ خانه‌ی ردیف $i$ ام و ستون $j$ ام جدول باشد (که $a_{11}$ خانه‌ی بالا و سمت چپ جدول است)، مستطیل با $i_1$، $j_1$، $i_2$ و $j_2$ مشخص می‌شود و شامل تمام $a_{ij}$ هایی است که $i_1\leq i \leq i_2$ و $j_1 \leq j \leq j_2$. تعداد ستون‌های مستطیل $(j_2-j_1+1)$ عددی زوج می‌باشد. عدد مستطیل عبارت است از جمع عددهای ستون‌های $j_1$، $j_1+2$، $j_1+4$، …، $j_2-1$ منهای جمع عددهای ستون‌های $j_1+1$، $j_1+3$، $j_1+5$،…، $j_2$ در مستطیل.

ورودی

در سطر اول فایل ورودی دو عدد $n$ و $k$ آمده‌اند، که $k$ تعداد $Query$ ها می‌باشد. سپس جدول نوشته شده است. ($n$ و $k$ به ترتیب از ۱۰۰۰ و $10^6$ بیش‌تر نیستند.)

سپس در $k$ خط، در هر خط اعداد $i_1$، $j_1$، $i_2$ و $j_2$ به ترتیب نوشته شده‌اند.

خروجی

در خروجی $k$ خط بنویسید، به طوری که در خط $i$ ام عدد مستطیل $i$ ام ورودی باشد.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 2
12 -7 3 5
1 2 0 -2
0 30 17 10
7 3 9 4
1 1 4 4
2 2 3 3
4
15

ابزار صفحه