弱鸡记录一道模拟题

前言：
这不能算是题解，只是日记+笔记而已
如果您想看正经规范的题解，请移步
题解
最近女赛寄了，并不是因为队员的原因，因为疫情??
我们组没能凑齐最终上场的队员，最后相当于是两个菜鸡上的，我+另外一个已经保研的学姐,这种组合让我成功输掉了比赛，不然总归是能拿个银??
唉，算了不想了
从最基础的开始做吧
真的在比赛的时候就有个怪圈，平时又是练习图论，又是练习数学，最后上场跟榜走的时候竟然只能从模拟这种题（就比较水的开始写起）偏偏还不太擅长做这种题，（平时都不练啊,就很奇怪
所以今天来练练
果然就寄了hh
P1003 [NOIP2011 提高组] 铺地毯
这道题之前做过，之前过的时候数据量没有这么大然后那次比较那啥，用的线段树过的，之后也没看题解，自己当时应该是做麻烦了，毕竟只是一道简单题hh
如果是线段树的话，说一下思路，线段树也是需要使用二维的线段树的，也就是使用二维数组，不能用两个一维数组组在一起，不然的话比如说更新同一段x的不同y值就会出问题
我想的二维线段树解法是，在x方向先找到要更新的段
然后从入口进去
入口就是：

if(l>=L&&r<=R)
1

函数是：

update(int L,int R,int l,int r,int cnt,int v)
{  
     update(L,R,l,(l+r)/2,cnt*2,v);
     update(L,R,(l+r)/2+1,r,cnt*2+1,v);
}//伪代码
1
2
3
4
5

然后从上面提到的那个入口进去让他去更新y值
可以这么写

if(l>=L&&r<=R)
update(tree[cnt],y1,y2,1,n,1,v);
1
2

这样的话就相当于更新tree[x_l~tree_r]段的y值，之后查询再返回相应的值
但是有个问题
这个题的数据量是五次方，之前怕超时，现在不超时了，超内存了，得，于是我们换一个方法
当然是看了题解之后
直接存储矩形的左上和右下两个顶点不就行了吗，奶奶的
然后挨个举行判断
giao
我只想到不能暴力枚举了
寄
结果越想越麻烦
hh
贴个代码吧

#include
using namespace std;
struct point
{
	int x; int y;
};
struct rectangle
{
	point p1;
	point p2;
};
vector<rectangle> edge;
int main(void)
{
	int n;
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int a, b,lenx, leny;
		scanf_s("%d%d%d%d", &a, &b, &lenx, &leny);
		edge.push_back({ {a,b},{a + lenx,b + leny} });
	}
	int x, y;
	scanf_s("%d%d", &x, &y);
	int ans = -1;
	for (int i = 0; i < n; i++)
	{
		if (x >= edge[i].p1.x&&x <= edge[i].p2.x&&y>=edge[i].p1.y&&y<=edge[i].p2.y)
		{
			ans = i + 1;
		}
	}
	printf("%d", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

后记：这是VS2017的代码