luogu3755&&bzoj4822老c的任务

luogu3755&&bzoj4822老c的任务

​​ 题目描述

老C是个程序员。

最近老C从老板那里接到了一个任务——给城市中的手机基站写个管理系统。作为经验丰富的程序员，老C轻松地完成了系统的大部分功能，并把其中一个功能交给你来实现。

由于一个基站的面积相对于整个城市面积来说非常的小，因此每个的基站都可以看作坐标系中的一个点，其位置可以用坐标(x,y)来表示。此外，每个基站还有很多属性，例如高度、功率等。运营商经常会划定一个区域，并查询区域中所有基站的信息。

现在你需要实现的功能就是，对于一个给定的矩形区域，回答该区域中（包括区域边界上的）所有基站的功率总和。如果区域中没有任何基站，则回答0。

输入输出格式

输入格式：

第一行两个整数n,m，表示一共有n个基站和m次查询。接下来一共有n行，每行由

x_i,y_i,p_i

xi,yi,pi三个空格隔开的整数构成，表示一个基站的坐标

(x_i,y_i)

(xi,yi)和功率

p_i

pi。不会有两个基站位于同一坐标。

接下来一共有m行，每行由

x1_j,y1_j,x2_j,y2_j

x1j,y1j,x2j,y2j四个空格隔开的整数构成，表示一次查询的矩形区域。该矩形对角坐标为

(x1_j,y1_j)

(x1j,y1j)和

(x2_j,y2_j)

(x2j,y2j)，且4边与坐标轴平行。

输出格式：

输出m行，每行一个整数，对应每次查询的结果。

输入输出样例

输入样例#1： 复制

4 2 0 0 1 0 1 2 2 2 4 1 0 8 0 0 1 1 1 1 5 6 输出样例#1： 复制

11 4 输入样例#2： 复制

3 2 -100 0 16 1 -10 32 1000 100 64 0 0 0 1 -1000 -1000 10000 10000 输出样例#2： 复制

0 112 说明

对于第1~2个测试点，1≤n,m≤100；

对于第3~5个测试点，1≤n≤50000,1≤m≤10000；

对于第6~10个测试点，1≤n≤100000,1≤m≤100000，数据有梯度；

对于所有测试点，−231≤xi,yi,pi,x1j,y1j,x2j,y2j<231,x1j≤x2j,y1j≤y2j − 2 31 ≤ x i , y i , p i , x 1 j , y 1 j , x 2 j , y 2 j < 2 31 , x 1 j ≤ x 2 j , y 1 j ≤ y 2 j 。

我可能是自带大常数 跑的很慢

我每个点 先都离散化一波 然后将询问离线 按照询问的行从小到大排序 然后扫描线 往上做 每次都用前缀和相减 然后 记录一个 当在他下面的时候的值 再记录一个当出他的值 然后相减即可

#pragma GCC optimize (2)#include#includeusing namespace std;#define N 110000inline char gc(){ static char now[1<<16],*T,*S; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int x,y,v;}v[N];struct node1{ int x,y1,y2,id,op;}qr[N<<1];inline bool cmp(node a,node b){return a.xn) break; while (cnt<=tot&&qr[cnt].x<=v[tt].x&&qr[cnt].op==1){ ans[qr[cnt].op][qr[cnt].id]=query(qr[cnt].y2)-query(qr[cnt].y1-1);++cnt; } int last=v[tt].x;add(v[tt].y,v[tt].v);++tt; while (last==v[tt].x){add(v[tt].y,v[tt].v);last=v[tt++].x;} while (cnt<=tot&&qr[cnt].x<=v[tt].x&&qr[cnt].op==2){ ans[qr[cnt].op][qr[cnt].id]=query(qr[cnt].y2)-query(qr[cnt].y1-1);++cnt; } }*/ for (int i=1;i<=m;++i) printf("%lld\n",ans[2][i]-ans[1][i]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。