登录
当前位置： 首页 > 工具软件 > luck-mobile > 使用案例 >

（二维线段树）hdu 1823 Luck and Love & poj 1195 Mobile phones & poj 2155 Matrix

花俊雄
2023-12-01

题目：
hdu1823

题意：
一个二维矩阵，有如下操作：
I x y v：在点 [ x , y ] 添加一个 v 值（同一个点可能有多个 v 值）
Q x1 y1 x2 y2：在区间 [ x1 , y1] ~ [ x2 , y2 ] 中查找最大的 v 值

poj1195

题意：
一个二维矩阵，有如下操作：
0 S：创建一个S * S的二维矩阵
1 x y v：在点 [ x , y ] 的值加上 v
2 x1 y1 x2 y2：计算在区间 [ x1 , y1] ~ [ x2 , y2 ] 中所有点的和
3：结束

poj2155

题意：
一个二维矩阵，有如下操作：
C x1 y1 x2 y2：在区间 [ x1 , y1] ~ [ x2 , y2 ] 的值取反（即1→0, 0→1)
Q x y：查询 点[ x , y ] 的值

思路：
二维线段树的查找与添加

另一种思路：二维树状数组写法

关于poj 2155：
如果线段树记录的是区间的值的话，会TLE（ + lazy 也会 TLE），如果记录的是区间的取反次数的话则不会 TLE （有点玄学，我用随机数据测了一下前后者运行所用的时间，是前者小于后者，但是在poj则TLE，可能是我写的代码的问题）

注意：
二维线段树的更新方式有两种：

1.查询是区间 [ xl, xr ] [yl, yr] ，更新的是点[ x ] [y]
as：在 [ 1，4 ] 更新 [ 2，2 ] 的一维区间

(更新范围)对于一维的
[ 1, 4 ] （即tree[1][yl, yr]）
[ 1, 2 ] （即tree[2][yl, yr]）
[ 2, 2 ] （即tree[5][yl, yr]）

一维的点更新代码（第二维的更新更一维线段树的更新一样）

void addx(int x, int y, int v, int l, int r, int pos){
    addy(pos, y, v, 1, Size, 1);
	if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (mid >= x)
		addx(x, y, v, lson);
    else
        addx(x, y, v, rson);
}

2.查询的是点 [ x ] [y], 更新的是区间 [ xl, xr ] [yl, yr]
as：在 [ 1，4 ] 更新 [ 1, 2 ] 的一维区间

(更新范围)对于一维的
 [ 1, 2 ] （即tree[2][y]）
 不需要更新[ 1, 4 ] ， [ 1, 1 ] ，  [ 2, 2 ]

一维的区间更新代码（第二维的更新更一维线段树的更新一样）

void addx(int xl, int xr, int yl, int yr, int v, int l, int r, int pos){
	if (xl <= l && r <= xr){
    	addy(pos, y, v, 1, Size, 1);
        return;
	} 
    int mid = (l + r) >> 1;
    if (mid >= x)
		addx(xl, xr, yl, yr, v, lson);
    else
        addx(xl, xr, yl, yr, v, rson);
}

poj 1195代码

#include <iostream>
#include <algorithm>
#define lson l, mid, pos << 1
#define rson mid + 1, r, pos << 1 | 1
using namespace std;
const int MAXN = 1030;
int tree[MAXN<<2][MAXN<<2];
int Size, a, b, c, d;
void updatay(int x, int p){
	tree[x][p] = tree[x][p<<1] + tree[x][p<<1|1];
}
void addy(int x, int y, int v, int l, int r, int pos){
    if (l == r){
        tree[x][pos] += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= y)
		addy(x, y, v, lson);
    else
        addy(x, y, v, rson);
    updatay(x, pos);
}
void addx(int x, int v, int l, int r, int pos){
    addy(pos, b, v, 1, Size, 1);
	if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (mid >= x)
		addx(x, v, lson);
    else
        addx(x, v, rson);
}
int findy(int x, int L, int R, int l, int r, int pos){
	if (l >= L && r <= R)
		return tree[x][pos];
	int mid = (l + r) >> 1;
	int ans = 0;
	if (mid >= L)
		ans += findy(x, L, R, lson);
	if (mid < R)
		ans += findy(x, L, R, rson);
	return ans;
}
int findx(int xl, int xr, int l, int r, int pos){
	if (l >= xl && r <= xr)
		return findy(pos, b, d, 1, Size, 1);
	int mid = (l + r) >> 1;
	int ans = 0;
	if (mid >= xl)
		ans += findx(xl, xr, lson);
	if (mid < xr)
		ans += findx(xl, xr, rson);
	return ans;
}
int main(){
	int n, ans;
    while (~scanf("%d", &n) && n != 3){
    	if (n == 0)
    		scanf("%d", &Size);
    	else if (n == 1){
    		scanf("%d%d%d", &a, &b, &c);
    		b++;
    		addx(a+1, c, 1, Size, 1);
		}
		else if (n == 2){
			scanf("%d%d%d%d", &a, &b, &c, &d);
			b++;
			d++;
			ans = findx(a+1, c+1, 1, Size, 1);
			printf("%d\n", ans);
		}
    }
    return 0;
}

hdu 1823代码解法1

#include <iostream>
#include <algorithm>
#include <cstring>
#define lson l, mid, pos << 1
#define rson mid + 1, r, pos << 1 | 1
using namespace std;
const int MAXH = 110; 
const int MAXN = 1010;
int tree[MAXH<<2][MAXN<<2];
int maxh = 101, maxn = 1001;  //maxn是1001而不是1000, 因为有0.0这个元素, maxh同理 
int a, aa;
double b, c;
void updatay(int x, int p){
	tree[x][p] = max(tree[x][p<<1], tree[x][p<<1|1]);
}
void addy(int x, int y, int v, int l, int r, int pos){
    if (l == r){
        tree[x][pos] = max(tree[x][pos], v);  //可能叠加，取最大
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= y)
		addy(x, y, v, lson);
    else
        addy(x, y, v, rson);
    updatay(x, pos);
}
void addx(int x, int v, int l, int r, int pos){
    addy(pos, (int)b, v, 1, maxn, 1);
	if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (mid >= x)
		addx(x, v, lson);
    else
        addx(x, v, rson);
}
int findy(int x, int L, int R, int l, int r, int pos){
	if (l >= L && r <= R)
		return tree[x][pos];
	int mid = (l + r) >> 1;
	int ans = 0;
	if (mid >= L)
		ans = findy(x, L, R, lson);
	if (mid < R)
		ans = max(ans, findy(x, L, R, rson));
	return ans;
}
int findx(int xl, int xr, int l, int r, int pos){
	if (l >= xl && r <= xr)
		return findy(pos, (int)b, (int)c, 1, maxn, 1);
	int mid = (l + r) >> 1;
	int ans = 0;
	if (mid >= xl)
		ans = findx(xl, xr, lson);
	if (mid < xr)
		ans = max(ans, findx(xl, xr, rson));
	return ans;
}
int main(){
	int m;
	double ans;
	char op;
    while (~scanf("%d", &m) && m != 0){
    	memset(tree, 0, sizeof(tree));
    	while (m--){
    		scanf(" %c", &op);
    		if (op == 'I'){
    			scanf("%d%lf%lf", &a, &b, &c);
    			a = a - 99;
				b = b * 10 + 1;
    			c = c * 10 + 1;  //缘分值向右偏移 1 ，为什么？因为线段树初始化为0，缘分值也有0，会冲突，既无法判断范围内有没有mm
    			addx(a, (int)c, 1, maxh, 1);
			}
			else{
				scanf("%d%d%lf%lf", &a, &aa, &b, &c);
				a = a - 99;
				aa = aa - 99;
				b = b * 10 + 1;
    			c = c * 10 + 1;
    			if (a > aa)
    				swap(a, aa);  //这是个坑
    			if (b > c)
    				swap(b, c);  //这是个坑
    			ans = (findx(a, aa, 1, maxh, 1) - 1) * 1.0 / 10;
    			if (ans < 0) // ans == -0.1
    				printf("-1\n");
    			else
					printf("%.1lf\n", ans);
			}
		}
    }
    return 0;
}

hdu 1823代码解法2

#include <iostream>
#include <algorithm>
#include <cstring>
#define lson l, mid, pos << 1
#define rson mid + 1, r, pos << 1 | 1
using namespace std;
const int MAXH = 110; 
const int MAXN = 1010;
int tree[MAXH<<2][MAXN<<2];
int maxh = 101, maxn = 1001;  //maxn是1001而不是1000, 因为有0.0这个元素, maxh同理 
int a, aa;
double b, c;
void updatay(int x, int p){
	tree[x][p] = max(tree[x][p<<1], tree[x][p<<1|1]);
}
void addy(int x, int y, int v, int l, int r, int pos){
    if (l == r){
        tree[x][pos] = max(tree[x][pos], v);  //可能叠加 
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= y)
		addy(x, y, v, lson);
    else
        addy(x, y, v, rson);
    updatay(x, pos);
}
void addx(int x, int v, int l, int r, int pos){
    addy(pos, (int)b, v, 1, maxn, 1);
	if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (mid >= x)
		addx(x, v, lson);
    else
        addx(x, v, rson);
}
int findy(int x, int L, int R, int l, int r, int pos){
	if (l >= L && r <= R)
		return tree[x][pos];
	int mid = (l + r) >> 1;
	int ans = -1;
	if (mid >= L)
		ans = findy(x, L, R, lson);
	if (mid < R)
		ans = max(ans, findy(x, L, R, rson));
	return ans;
}
int findx(int xl, int xr, int l, int r, int pos){
	if (l >= xl && r <= xr)
		return findy(pos, (int)b, (int)c, 1, maxn, 1);
	int mid = (l + r) >> 1;
	int ans = -1;
	if (mid >= xl)
		ans = findx(xl, xr, lson);
	if (mid < xr)
		ans = max(ans, findx(xl, xr, rson));
	return ans;
}
int main(){
	int m;
	double ans;
	char op;
    while (~scanf("%d", &m) && m != 0){
    	memset(tree, -1, sizeof(tree));
    	while (m--){
    		scanf(" %c", &op);
    		if (op == 'I'){
    			scanf("%d%lf%lf", &a, &b, &c);
    			a = a - 99;
				b = b * 10 + 1;
    			c = c * 10;   //不用偏移，因为线段树初始化为-1，不与0.0冲突
    			addx(a, (int)c, 1, maxh, 1);
			}
			else{
				scanf("%d%d%lf%lf", &a, &aa, &b, &c);
				a = a - 99;
				aa = aa - 99;
				b = b * 10 + 1;
    			c = c * 10 + 1;
    			if (a > aa)
    				swap(a, aa);  //...
    			if (b > c)
    				swap(b, c);  //...
    			ans = findx(a, aa, 1, maxh, 1) * 1.0 / 10;
    			if (ans == -1)
    				printf("-1\n");
    			else
					printf("%.1lf\n", ans);
			}
		}
    }
    return 0;
}

poj 2155 代码

#include <iostream>
#include <algorithm>
#define lson l, mid, pos << 1
#define rson mid + 1, r, pos << 1 | 1
using namespace std; 
const int MAXN = 1010;
int tree[MAXN<<2][MAXN<<2];  //记录一个区间的取反次数 
int n, ans;
void buildy(int x, int l, int r, int pos){
	tree[x][pos] = 0;
	if (l != r){
		int mid = (l + r) >> 1;
		buildy(x, lson);
		buildy(x, rson);
	}
} 
void buildx(int l, int r, int pos){
	buildy(pos, 1, n, 1);
	if (l != r){
		int mid = (l + r) >> 1;
		buildx(lson);
		buildx(rson);
	}
} 
void addy(int x, int yl, int yr, int l, int r, int pos){
    if (yl <= l && r <= yr){
        tree[x][pos]++;
        return;
    }
    int mid = (l + r) >> 1;
    if (mid >= yl)
        addy(x, yl, yr, lson);
    if (mid < yr)
        addy(x, yl, yr, rson);
}
void addx(int xl, int xr, int yl, int yr, int l, int r, int pos){
    if (xl <= l && r <= xr){
    	addy(pos, yl, yr, 1, n, 1);  //因为这个不是 x 点更新而是 x 区间更新 
        return;
	}
    int mid = (l + r) >> 1;
    if (mid >= xl)
        addx(xl, xr, yl, yr, lson);
    if (mid < xr) 
        addx(xl, xr, yl, yr, rson);
}
void findy(int x, int y, int l, int r, int pos){
	ans += tree[x][pos];
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (mid >= y)
        findy(x, y, lson);
    else
        findy(x, y, rson);
}
void findx(int x, int y, int l, int r, int pos){
	findy(pos, y, 1, n, 1);  //因为更新的时候是区间更新所有每个关于待查询的 x 都要查询一次 
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (mid >= x)
        findx(x, y, lson);
    else
        findx(x, y, rson);
}
int main(){
//    freopen("_in.txt", "r", stdin);
//	freopen("_out1.txt", "w", stdout);
    int t, m, a, b, c, d;
    char op;
    scanf("%d", &t);
    while (t--){
    	scanf("%d%d", &n, &m);
    	buildx(1, n, 1);
    	while (m--){
			scanf(" %c", &op);
	    	if (op == 'C'){
	    		scanf("%d%d%d%d", &a, &b, &c, &d);
	    		addx(a, c, b, d, 1, n, 1);
			}
			else{
				ans = 0;
				scanf("%d%d", &a, &b);
				findx(a, b, 1, n, 1);
				printf("%d\n", ans % 2);
			}
		}
		printf("\n");
	}
    return 0;
}
 类似资料：

相关阅读

Android 二维码扫描和生成二维码功能Android：二维ArrayList帮助BSP树作为多维搜索结构Android 二维码 生成和识别二维码 附源码下载将一维数组迭代为二维数组

相关文章

2024美团春季笔试第二场 T4 区间众数求和 线段树做法Java二维数组二分搜索树玩转二叉树习题7-2 二叉排序树(二叉搜索树)

相关问答

二叉树与二叉搜索树Big oh分析给定二叉树是否为二叉搜索树纤维、纱线等BlueJ二维数组二叉树验证

相关文档

社群思维复杂性思维Ceph 运维手册树莓派与 Linux数据结构思维
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.