P4848 崂山白花蛇草水
题目描述
神犇 Aleph 在 SDOI Round2 前立了一个 flag:如果进了省队,就现场直播喝崂山白花蛇草水。凭借着神犇 Aleph 的实力,他轻松地进了山东省省队,现在便是他履行诺言的时候了。蒟蒻 Bob 特地为他准备了 999,999,999,999,999,999 瓶崂山白花蛇草水,想要灌神犇 Aleph。神犇 Aleph 求(跪着的)蒟蒻 Bob 不要灌他,由于神犇 Aleph 是神犇,蒟蒻 Bob 最终答应了他的请求,但蒟蒻 Bob 决定将计就计,也让神犇 Aleph 回答一些问题。
具体说来,蒟蒻 Bob 会在一个宽敞的广场上放置一些崂山白花蛇草水(可视为二维平面上的一些整点),然后询问神犇 Aleph 在矩形区域 $x_1\le x\le x_2,y_1\le y\le y_2$ 中,崂山白花蛇草水瓶数第 $k$ 多的是多少。为了避免麻烦,蒟蒻 Bob 不会在同一个位置放置两次或两次以上的崂山白花蛇草水,但蒟蒻 Bob 想为难一下神犇 Aleph,希望他能在每次询问时立刻回
答出答案。
神犇 Aleph 不屑于做这种问题,所以把这个问题交给了你。
输入格式
无
输出格式
无
说明/提示
对于所有数据,$n\le500000$,$q\le100000$,$1\le x, y\le n$,$1\le v\le 10^9$,$1\le x_1\le x_2\le n$,$1\le y_1\le y_2\le n$,$1\le k\le q$。