1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼

Time Limit: 15 Sec  Memory Limit: 357 MB

Submit: 648  Solved: 273

[Submit][Status][Discuss]

Description

很久很久以前,在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者,在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里,若有所思,他问一个园丁道: “最近我在思索一个问题,如果我们把花坛摆成六个六角形,那么……” “那么本质上它是一个深度优先搜索,陛下”,园丁深深地向国王鞠了一躬。 “嗯……我听说有一种怪物叫九头蛇,它非常贪吃苹果树……” “是的,显然这是一道经典的动态规划题,早在N元4002年我们就已经发现了其中的奥秘了,陛下”。 “该死的,你究竟是什么来头?” “陛下息怒,干我们的这行经常莫名其妙地被问到和OI有关的题目,我也是为了预防万一啊!” 王者的尊严受到了伤害,这是不可容忍的。看来一般的难题是难不倒这位园丁的,国王最后打算用车轮战来消耗他的实力: “年轻人,在我的花园里的每一棵树可以用一个整数坐标来表示,一会儿,我的骑士们会来轮番询问你某一个矩阵内有多少树,如果你不能立即答对,你就准备走人吧!”说完,国王气呼呼地先走了。 这下轮到园丁傻眼了,他没有准备过这样的问题。所幸的是,作为“全国园丁保护联盟”的会长——你,可以成为他的最后一根救命稻草。

Input

第一行有两个整数n,m(0≤n≤500000,1≤m≤500000)。n代表皇家花园的树木的总数,m代表骑士们询问的次数。 文件接下来的n行,每行都有两个整数xi,yi,代表第i棵树的坐标(0≤xi,yi≤10000000)。 文件的最后m行,每行都有四个整数aj,bj,cj,dj,表示第j次询问,其中所问的矩形以(aj,bj)为左下坐标,以(cj,dj)为右上坐标。

Output

共输出m行,每行一个整数,即回答国王以(aj,bj)和(cj,dj)为界的矩形里有多少棵树。

Sample Input

3 1 0 0 0 1 1 0 0 0 1 1

Sample Output

3

HINT

Source

题解:一个超级神奇的题目,对于此题,首先很快可以想到用树状数组来搞,然后第一反应就是二维的,但想想这数据规模显然不现实。。。于是就想办法变成一维的,将Y坐标全部离散化(包括询问里面的),然后按照X坐标优先,Y坐标其次优先从小到大排序,然后遇到查询点就查询,否则就加入数组,然后没了,就是程序略长

  1 /**************************************************************
  2     Problem: 1935
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:7968 ms
  7     Memory:100224 kb
  8 ****************************************************************/
  9  
 10 var
 11    i,j,k,l,m,n,nx,ny:longint;
 12    a:array[0..600000,1..2] of longint;
 13    b:array[0..1200000,1..2] of longint;
 14    c:array[0..4000000] of longint;
 15    d:array[0..3000000,1..2] of longint;
 16    e:array[0..3000000,1..4] of longint;
 17 procedure swap(var x,y:longint);
 18           var z:longint;
 19           begin
 20                z:=x;x:=y;y:=z;
 21           end;
 22 procedure sort(l,r:longint);
 23           var i,j,x,y:longint;
 24           begin
 25                i:=l;j:=r;x:=d[(l+r) div 2,1];
 26                repeat
 27                      while d[i,1]<x do inc(i);
 28                      while d[j,1]>x do dec(j);
 29                      if i<=j then
 30                         begin
 31                              swap(d[i,1],d[j,1]);
 32                              swap(d[i,2],d[j,2]);
 33                              inc(i);dec(j);
 34                         end;
 35                until i>j;
 36                if i<r then sort(i,r);
 37                if l<j then sort(l,j);
 38           end;
 39 procedure sort0(l,r:longint);
 40           var i,j,x,y,z:longint;
 41           begin
 42                i:=l;j:=r;x:=e[(l+r) div 2,1];y:=e[(l+r) div 2,2];z:=e[(l+r) div 2,3];
 43                repeat
 44                      while (e[i,1]<x) or ((e[i,1]=x) and (e[i,2]<y)) or ((e[i,1]=x) and (e[i,2]=y) and (e[i,3]>z)) do inc(i);
 45                      while (e[j,1]>x) or ((e[j,1]=x) and (e[j,2]>y)) or ((e[j,1]=x) and (e[j,2]=y) and (e[j,3]<z)) do dec(j);
 46                      if i<=j then
 47                         begin
 48                              swap(e[i,1],e[j,1]);
 49                              swap(e[i,2],e[j,2]);
 50                              swap(e[i,3],e[j,3]);
 51                              inc(i);dec(j);
 52                         end;
 53                until i>j;
 54                if i<r then sort0(i,r);
 55                if l<j then sort0(l,j);
 56           end;
 57 procedure sort1(l,r:longint);
 58           var i,j,x,y:longint;
 59           begin
 60                i:=l;j:=r;x:=e[(l+r) div 2,3];
 61                repeat
 62                      while e[i,3]<x do inc(i);
 63                      while e[j,3]>x do dec(j);
 64                      if i<=j then
 65                         begin
 66                              swap(e[i,1],e[j,1]);
 67                              swap(e[i,2],e[j,2]);
 68                              swap(e[i,3],e[j,3]);
 69                              swap(e[i,4],e[j,4]);
 70                              inc(i);dec(j);
 71                         end;
 72                until i>j;
 73                if i<r then sort1(i,r);
 74                if l<j then sort1(l,j);
 75           end;
 76 procedure add(x,y:longint);
 77          begin
 78               if x<=0 then exit;
 79               while x<=nx do
 80                     begin
 81                          inc(c[x],y);
 82                          inc(x,x and (-x));
 83                     end;
 84          end;
 85 function sum(x:longint):longint;
 86          begin
 87               sum:=0;
 88               while x>0 do
 89                     begin
 90                          inc(sum,c[x]);
 91                          dec(x,x and (-x));
 92                     end;
 93          end;
 94 begin
 95      readln(n,m);
 96      for i:=1 to n do readln(a[i,1],a[i,2]);
 97      for i:=1 to m do readln(b[i*2-1,1],b[i*2-1,2],b[i*2,1],b[i*2,2]);
 98      for i:=1 to n do
 99          begin
100               d[i,1]:=a[i,2];
101               d[i,2]:=i;
102          end;
103      for i:=1 to m*2 do
104          begin
105               d[n+i,1]:=b[i,2];
106               d[n+i,2]:=-i;
107          end;
108      sort(1,n+m*2);j:=0;d[0,1]:=-1;
109      for i:=1 to n+m*2 do
110          begin
111               if d[i,1]<>d[i-1,1] then inc(j);
112               if d[i,2]>0 then a[d[i,2],2]:=j else b[-d[i,2],2]:=j;
113          end;
114      nx:=j;
115      for i:=1 to m do
116          begin
117               e[i*4-3,1]:=b[i*2-1,1]-1;e[i*4-3,2]:=b[i*2-1,2]-1;
118               e[i*4-2,1]:=b[i*2-1,1]-1;e[i*4-2,2]:=b[i*2,2];
119               e[i*4-1,1]:=b[i*2,1];e[i*4-1,2]:=b[i*2-1,2]-1;
120               e[i*4,1]:=b[i*2,1];e[i*4,2]:=b[i*2,2];
121          end;
122      for i:=1 to n do begin e[m*4+i,1]:=a[i,1];e[m*4+i,2]:=a[i,2]; end;
123      for i:=1 to m*4+n do e[i,3]:=i;
124      sort0(1,m*4+n);
125      fillchar(c,sizeof(c),0);
126      for i:=1 to m*4+n do if e[i,3]<=(m*4) then e[i,4]:=sum(e[i,2]) else add(e[i,2],1);
127      sort1(1,m*4+n);
128      for i:=1 to m do writeln(e[i*4,4]-e[i*4-1,4]-e[i*4-2,4]+e[i*4-3,4]);
129      readln;
130 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】问题 1431: 分糖果

问题描述 有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏: 每个小朋友都把自己的糖果分一半给左手边的孩子。 一轮分糖后,...

852
来自专栏专知

【Leetcode 206】关关的刷题日记70 – Leetcode 206. Reverse Linked List

关关的刷题日记70 – Leetcode 206. Reverse Linked List 题目 Reverse a singly linked list. 题...

3368
来自专栏数据结构与算法

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

3678
来自专栏数据结构与算法

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

2946
来自专栏专知

关关的刷题日记78 – Leetcode 69. Sqrt(x)

关关的刷题日记78 – Leetcode 69. Sqrt(x) 题目 Implement int sqrt(int x). Compute and retur...

3516
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

3755
来自专栏java工会

猿诗·用java随机生成一首诗

2013
来自专栏数据结构与算法

BZOJ3884: 上帝与集合的正确用法(欧拉函数 扩展欧拉定理)

第二天, 上帝创造了一个新的元素,称作“α”。“α”被定义为“元”构成的集合。容易发现,一共有两种不同的“α”。

1332
来自专栏算法修养

HYSBZ 2160 拉拉队排练(回文树)

2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

3387
来自专栏前端新视界

一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等(感谢博友提供的关于该问题的相关资料 划分问题)。由于时间仓促,加之面试时头昏脑涨,这道题...

2368

扫码关注云+社区