P2163 [SHOI2007] The Gardener's Trouble

Long, long ago, on a distant continent there was a beautiful kingdom. The king who ruled this beautiful country was a gardening enthusiast, and in his royal garden he planted all kinds of exotic flowers and grasses. One day the king was strolling in the garden, lost in thought. He asked a gardener: "Lately I have been pondering a question: if we arrange the flowerbeds into six hexagons, then..." "Then, in essence it's a depth-first search, Your Majesty." The gardener bowed deeply to the king. "Hmm... I have heard of a monster called the Hydra, and it is very fond of eating apple trees..." "Yes, clearly this is a classic dynamic programming problem. As early as the N 元 $4002$ 年 we had already uncovered its secret, Your Majesty." "Damn it, what on earth are you?" "Please calm down, Your Majesty. In our line of work we often get inexplicably asked questions related to OI. I'm just being prepared for anything!" The king's dignity was hurt, which was intolerable.

It seems ordinary hard problems cannot stump this gardener. The king decided to exhaust his strength with a war of attrition: "Young man, there are $n$ trees in my garden, and each tree can be represented by an integer coordinate. Soon, my $m$ knights will come in turns to ask you how many trees lie inside a certain rectangle. If you cannot answer immediately and correctly, be ready to leave!" After saying this, the king stormed off. Now it was the gardener's turn to be dumbfounded—he had not prepared for such a problem. Fortunately, as the president of the "National Gardeners Protection Alliance"—you—can become his last lifeline.

The first line contains two integers $n, m$, representing the number of trees and the number of queries. The next $n$ lines each contain two integers $x, y$, indicating that there is a tree at coordinate $(x, y)$. It is possible that two trees share the same coordinate. The next $m$ lines each contain four integers $a, b, c, d$, describing a query: count how many trees are inside the rectangle with lower-left corner $(a, b)$ and upper-right corner $(c, d)$, including the boundary.

For each query, output a single integer on its own line indicating the answer.

#### Constraints and Conventions - For $30\%$ of the testdata, it is guaranteed that $n, m \leq 10$. - For $100\%$ of the testdata, it is guaranteed that $0 \leq n \leq 5 \times 10^5$, $1 \leq m \leq 5 \times 10^5$, $0 \leq x, y, a, b, c, d \leq 10^7$, $a \leq c$, $b \leq d$. Translated by ChatGPT 5