Distance

یک جدول $n m$ به شما داده شده است که خانه‌های آن به صورت جفت‌های $( 1 \leq i \leq n ,1 \leq j \leq m)$ شماره‌گذاری شده‌اند. فاصله‌ی دو خانه $(i_1,j_1)$ و $(i_2,j_2)$ برابر است با $|i_1-i_2| + |j_1-j_2|$. تعدادی از خانه‌های جدول سیاه‌اند.

به شما تعدادی جفت خانه $(y_i,y_j)$ و $(x_i,x_j)$ داده شده است، شما باید به ازای هر جفت خانه $(x,y)$ تعداد خانه‌های سیاهی که به $x$ نزدیک تراند و تعداد خانه‌های سیاهی که به $y$ نزدیک تر‌اند و تعداد خانه‌های سیاهی که فاصله برابر از $x$ و $y$ دارند را به دست آورید.

ورودی

در سطر اول ورودی چهار عدد $(1 \leq n,m \leq 10^9)$ و $(1 \leq p,q \leq 10^5)$ آمده است. در $p$ سطر بعدی $(i,j)$ خانه‌های سیاه آمده است. در $q$ سطر آخر ورودی در هر سطر چهار عدد $x_i$ و $x_j$ و $y_i$ و $y_j$ به ترتیب آمده‌اند که مختصات دو خانه $x$ و $y$ را مشخص می‌کنند.

خروجی

در هر کدام از $q$ سطر خروجی سه عدد چاپ کنید که عدد اول تعداد خانه‌های سیاه نزدیک تر به $x$ است، عدد دوم تعداد خانه‌های نزدیک تر به $y$ و عدد آخر تعداد خانه‌هایی است که فاصله برابر از $x$ و $y$ دارند.

محدودیت‌ها

  • محدودیت زمان: ۶ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودی نمونه خروجی نمونه
6 5 6 1
1 2
6 5
5 1
3 3
3 4
4 1
2 3 4 3		1 3 2

پاسخ

فرض کنید که مقدار $sq(i,j)$ برابر باشد با تعداد خانه‌های سیاه $(x,y)$ که $x \leq i$ و $y \leq j$ برقرار باشد. همچنین مقدار $l_1(i,j)$ برابر باشد با تعداد خانه‌های سیاهی که دو شرط $x \leq i$ و $x+y \leq i+j$ را دارند و مقدار $l_2(i,j)$ برابر با تعداد خانه‌های سیاهی باشد که دو شرط $x \leq i$ و $x-y \leq i-j$ را دارند.

می‌توان نشان داد که که اگر دو خانه $x$ و $y$ در نظر بگیریم ، می‌توان تعداد خانه‌هایی که به هر کدام از آن ها نزدیک تراند را به صورت عبارتی بر حسب تعداد محدودی از $sq$ ها و $l_1$ ها و $l_2$ ها بنویسیم. در ابتدا این مقادیر را محاسبه نمی‌کنیم و پس از این که برای تمام جفت خانه‌های $x$ و $y$ پاسخ سؤال را بر حسب توابع گفته شده محاسبه کردیم، شروع به محاسبه مقادیر می‌کنیم و پاسخ دقیق در خواست‌ها را به‌دست می‌آوریم.

محاسبه مقدار دقیق $sq$ ها $l_1$ ها و $l_2$ ها را می‌توان به صورت مشابه و با استفاده از الگوریتم sweep line و با استفاده از داده ساختار segment tree انجام داد. توجه کنید که ما قبل از محاسبه آن‌ها می‌دانیم که چه داده‌هایی را احتیاج داریم.

▸ سوال قبل سوال بعد ◂