【二次元差分】Monitor
5262 ワード
Monitor
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=6514
Time Limit:6000/3000 MS(Java/Others) メモリLimit:163840/163840 K(Java/Others)Total Submission(s):600 Acceepted Submission(s):190
Problem Description
Xiaoteng has a large are a of land for growing crops、and the land can be seen as a rectangles of n×m. But recently Xiaoteng found that his crops were oten stolen by a group of people,so he decided to install some montors to find all the people and then negotiate with them.However,Xiao Teng borge the montronight p monitors installed by Xiaoteng、and the rectangle montord by each monitor is known. Xiao Teng Gress that the thieves would also steal q times of crops.he also gess the range the y were going to steal,which was also a rectangles.Xiao Teng wants to know monts can see all the thieves at.
Input
The re are muttiple test cases.Each case starts with a line containing two integers n,m(1≦n,1≦m,n×m≦107) which represent the ara of the land.And the secend line contain a integer p(1≦p≦106) which represent the number of the monitor Xiaoteng has installed.This is followed by p lines each describing a rectangle.Each of these line s contains four intergers x 1,y 1,x 2 and y 2(1≦x 1≦x 2≦n,1≦y 1≦y 2≦m) ,meaning the lower left coner and up per right coner of the rectanle.Next line contain a integer q(1≦q≦106) which represent the number of times that thieves will steal the crops.This is followed by q lines each describing a rectanle.Each of these line s contains four intergers x 1,y 1,x 2 and y 2(1≦x 1≦x 2≦n,1≦y 1≦y 2≦m)、meaning the lower left coner and up per right coner of the rectangle.
Output
For each case you shoul d print q LINE.Each LINE containing YES or NO. mean the all thieves whether can be seen.
Sample Input
Sample Output
ベント
In the picture、the red solid rectangles mean the monitor Xiaoteng installed、and the blue dotted rectanles mean the ara will be stolen.
タイトルの大意:
複数のグループの入力があります.各グループの入力に対して、まず2つの整数nを入力します.mは次の行は整数pで、下のp行は4つの整数x 1を入力します.y 1、x 2、y 2は、(x 1、y 1)から(x 2、y 2)までの矩形領域を表しています.それから、整数qを入力します.この矩形全体がマークされていれば、YESを出力します.そうでなければ、NOを出力します.
問題解決の考え方:
私たちは図の中でマークされた長方形領域の全部の数を1にして、面積のプレフィックスとを求めます.検索過程では、面積プレフィックスとこの領域の面積だけを求めます.求められた面積はこの矩形の実際の面積と同じであれば、この領域が全部カバーされていることを証明します.私たちは、似たような差分の思想によって、mapp[x 1][y 1]、mapp[x 2＋1][y 2＋1]を一つずつ加えて、mapp[x 1]、[y 2＋1]を、mapp[x 2＋1][y 1]を一つずつ差し引いて、それらのmapp[i][j]1に対して、1つの面積として、最後のプレフィックスとして検索することができます.注:この問題配列範囲は不確定です.n、mの値によって空間を開くしかないです.そうでないとメモリが制限されます.
コード:
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=6514
Time Limit:6000/3000 MS(Java/Others) メモリLimit:163840/163840 K(Java/Others)Total Submission(s):600 Acceepted Submission(s):190
Problem Description
Xiaoteng has a large are a of land for growing crops、and the land can be seen as a rectangles of n×m. But recently Xiaoteng found that his crops were oten stolen by a group of people,so he decided to install some montors to find all the people and then negotiate with them.However,Xiao Teng borge the montronight p monitors installed by Xiaoteng、and the rectangle montord by each monitor is known. Xiao Teng Gress that the thieves would also steal q times of crops.he also gess the range the y were going to steal,which was also a rectangles.Xiao Teng wants to know monts can see all the thieves at.
Input
The re are muttiple test cases.Each case starts with a line containing two integers n,m(1≦n,1≦m,n×m≦107) which represent the ara of the land.And the secend line contain a integer p(1≦p≦106) which represent the number of the monitor Xiaoteng has installed.This is followed by p lines each describing a rectangle.Each of these line s contains four intergers x 1,y 1,x 2 and y 2(1≦x 1≦x 2≦n,1≦y 1≦y 2≦m) ,meaning the lower left coner and up per right coner of the rectanle.Next line contain a integer q(1≦q≦106) which represent the number of times that thieves will steal the crops.This is followed by q lines each describing a rectanle.Each of these line s contains four intergers x 1,y 1,x 2 and y 2(1≦x 1≦x 2≦n,1≦y 1≦y 2≦m)、meaning the lower left coner and up per right coner of the rectangle.
Output
For each case you shoul d print q LINE.Each LINE containing YES or NO. mean the all thieves whether can be seen.
Sample Input
Sample Output
ベント
In the picture、the red solid rectangles mean the monitor Xiaoteng installed、and the blue dotted rectanles mean the ara will be stolen.
タイトルの大意:
複数のグループの入力があります.各グループの入力に対して、まず2つの整数nを入力します.mは次の行は整数pで、下のp行は4つの整数x 1を入力します.y 1、x 2、y 2は、(x 1、y 1)から(x 2、y 2)までの矩形領域を表しています.それから、整数qを入力します.この矩形全体がマークされていれば、YESを出力します.そうでなければ、NOを出力します.
問題解決の考え方:
私たちは図の中でマークされた長方形領域の全部の数を1にして、面積のプレフィックスとを求めます.検索過程では、面積プレフィックスとこの領域の面積だけを求めます.求められた面積はこの矩形の実際の面積と同じであれば、この領域が全部カバーされていることを証明します.私たちは、似たような差分の思想によって、mapp[x 1][y 1]、mapp[x 2＋1][y 2＋1]を一つずつ加えて、mapp[x 1]、[y 2＋1]を、mapp[x 2＋1][y 1]を一つずつ差し引いて、それらのmapp[i][j]1に対して、1つの面積として、最後のプレフィックスとして検索することができます.注:この問題配列範囲は不確定です.n、mの値によって空間を開くしかないです.そうでないとメモリが制限されます.
コード:
#include
#include
#include
#include
#include
#include
#include