luoguP2163 [SHOI2007]园丁的烦恼

安利系列博文

https://www.cnblogs.com/tyner/p/11565348.html

https://www.cnblogs.com/tyner/p/11605073.html

题意

https://www.luogu.org/problem/P2163

如摘要所示，二位静态数点

分析

离线下来

先，按照y为第一关键字，x为第二关键字排序，把n个数点，和询问的4*m个点都加进去，然后优先数点

这样就可以用关于 x 的树状数组进行求和和加点操作，进而用查询矩形的四个端点的sum加加减减就好了

可是这代码不知道为什么RE了一个点，，，以后再调吧

小伙伴们记得提醒博主这个傻子哦...

或者大佬能帮我调调....

（RE对于博主来说，只是常规操作..）

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAX = 500000+99;

const int INF = 2147000047;

int n,m;

int t[MAX];

struct node{

	int xx, x, y;//x为离散化之后的x坐标

	int is;//is = 1表示数点， 0表示查询点

	//这样我们就可以在排序的时候分清数点与查询点 ，并且优先数点了

	int id;

	//用以按要求输出答案

	node(int xx=0, int y=0, int is=0, int id=0) : xx(xx), y(y), is(is), id(id) {}

}d[MAX*5];

bool cmp1(node a, node bb) {

	if(a.y == bb.y) {

		if(a.x == bb.x) return a.is > bb.is;

		return a.x < bb.x;

	}

	return a.y < bb.y;

}

bool cmp2(node a, node bb) {

	return a.xx < bb.xx;

}

int cnt, max_x, ans[MAX];//ans[id] = 第id个查询点的前缀和

void add_node(int xx, int y, int is, int id) {

	++cnt;

	d[cnt] = node(xx, y, is, id);

}

bool cmp3(node a, node bb) {

	return a.id < bb.id;

}

void add(int x, int k) { while(x <= max_x) t[x] += k, x += x&(-x);}

int query(int x) {

	int res = 0;

	while(x) res += t[x], x -= x&(-x);

	return res;

}

void init() {

	scanf("%d%d",&n,&m);

	int x1, y1, x2, y2;

	for(int i = 1; i <= n; i++) {

		scanf("%d%d",&x1, &y1);

		add_node(x1, y1, 1, INF);

	}

	for(int i = 1; i <= (m<<2); i += 4) {

		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

		add_node(x2, y2, 0, i);

		add_node(x1-1, y2, 0, i+1);

		add_node(x2, y1-1, 0, i+2);

		add_node(x1-1, y1-1, 0, i+3);

	}

	sort(d+1, d+1+cnt, cmp2);

	int tot = 1;

    d[1].x = 1;//记得初始化成1

	for(int i = 2; i <= cnt; i++) {

		if(d[i].xx != d[i-1].xx) ++tot;

		d[i].x = tot;

	}

    max_x = d[cnt].x;

//    for(int i = 1; i <= cnt; i++) {

//        if(d[i].is == 1) printf("数点：");

//        else printf("查询点%d为", d[i].id);

//        printf("%d %d\n", d[i].x, d[i].y);

//    }

}

void print_ans() {

	sort(d+1, d+1+cnt, cmp3);

	for(int i = 1; i <= (m<<2); i += 4) printf("%d\n", ans[i]-ans[i+1]-ans[i+2]+ans[i+3]);

}

void solve() {

	sort(d+1, d+cnt+1, cmp1);

	for(int i = 1; i <= cnt; i++) {

		if(d[i].is == 1) add(d[i].x, 1);//会重复加点吗

		else ans[d[i].id] = query(d[i].x);

	}

	print_ans();

}

int main() {

	init();

	solve();

	return 0;

}

/*

3 1

0 0

0 1

1 0

0 0 1 1

*/

巴特西

luoguP2163 [SHOI2007]园丁的烦恼

题意

分析

最新文章

热门文章