Fast Matrix Operations (UVA - 11992,二维线段树 + 简单应用)

2024-03-30 14:08

本文主要是介绍Fast Matrix Operations (UVA - 11992,二维线段树 + 简单应用),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.题目链接:

UVA-11992

二.题目大意:

有一个 r × c 大小的矩阵,最多有 10^{6} 个元素,r ≤ 20.

矩阵中元素的初始值均为 0.

现有三种操作

① 1 x1 y1 x2 y2 v :将 (x1, y1) 到 (x2, y2) 之间的元素都加上值 v.

② 2 x1 y1 x2 y2 v:将 (x1, y1) 到 (x2, y2) 之间的元素都置为值 v.

③ 3 x1 y1 x2 y2  :查询 (x1, y1) 到 (x2, y2) 之间的元素的 和、最大值、最小值,并将其输出.

操作总数 m ≤ 10^{6}.

三.分析:

这三种操作当然是线段树的基本操作啦.

由于 r ≤ 20,所以建造 r 个线段树即可.

把 左右区间、最小值、最大值、和、懒惰标记、set 值封装在结构体了就可以了.

这里注意一点:

在函数 down 中 set 和 add 的顺序

假设操作时先进行了 set 后进行了 add,那么这里肯定是要先 set 再 add 的.

相反,由于在 set 时,已经将 tree[row][k].add = 0,所以此时也是可以先进行 set的.

四.代码实现:

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;const int M = (int)1e6 + 10;
const int inf = 0x3f3f3f3f;
struct node1
{int l, r;int sum, add;int Max, Min;int Set;
}tree[21][M * 3];struct node2
{int sum;int Min;int Max;
}tnode;void build(int k, int l, int r, int row)
{tree[row][k].l = l;tree[row][k].r = r;tree[row][k].sum = 0;tree[row][k].add = 0;tree[row][k].Max = 0;tree[row][k].Min = 0;tree[row][k].Set = -1;if(l == r)return;int m = (l + r) / 2;build(k * 2, l, m, row);build(k * 2 + 1, m + 1, r, row);
}void down(int row, int k)
{int lk = 2 * k;int rk = 2 * k + 1;if(~tree[row][k].Set){tree[row][lk].Set = tree[row][rk].Set = tree[row][k].Set;tree[row][lk].add = tree[row][rk].add = 0;tree[row][k].Set = -1;tree[row][lk].sum = (tree[row][lk].r - tree[row][lk].l + 1) * tree[row][lk].Set;tree[row][rk].sum = (tree[row][rk].r - tree[row][rk].l + 1) * tree[row][rk].Set;tree[row][lk].Max = tree[row][lk].Min = tree[row][lk].Set;tree[row][rk].Max = tree[row][rk].Min = tree[row][rk].Set;}if(tree[row][k].add > 0){tree[row][lk].add += tree[row][k].add;tree[row][rk].add += tree[row][k].add;tree[row][lk].sum += (tree[row][lk].r - tree[row][lk].l + 1) * tree[row][k].add;tree[row][rk].sum += (tree[row][rk].r - tree[row][rk].l + 1) * tree[row][k].add;tree[row][lk].Min += tree[row][k].add;tree[row][lk].Max += tree[row][k].add;tree[row][rk].Min += tree[row][k].add;tree[row][rk].Max += tree[row][k].add;tree[row][k].add = 0;}
}void add(int k, int y1, int y2, int v, int row)
{if(tree[row][k].l >= y1 && tree[row][k].r <= y2){tree[row][k].sum += (tree[row][k].r - tree[row][k].l + 1) * v;tree[row][k].add += v;tree[row][k].Min += v;tree[row][k].Max += v;return;}if(tree[row][k].add || ~tree[row][k].Set)down(row, k);int m  = (tree[row][k].l + tree[row][k].r) / 2;if(y1 <= m)add(k * 2, y1, y2, v, row);if(m < y2)add(k * 2 + 1, y1, y2, v, row);tree[row][k].sum = tree[row][k * 2].sum + tree[row][k * 2 + 1].sum;tree[row][k].Max = max(tree[row][k * 2].Max, tree[row][k * 2 + 1].Max);tree[row][k].Min = min(tree[row][k * 2].Min, tree[row][k * 2 + 1].Min);
}void Set(int k, int y1, int y2, int v, int row)
{if(tree[row][k].l >= y1 && tree[row][k].r <= y2){tree[row][k].sum = (tree[row][k].r - tree[row][k].l + 1) * v;tree[row][k].add = 0;tree[row][k].Set = v;tree[row][k].Min = v;tree[row][k].Max = v;return;}if(tree[row][k].add || ~tree[row][k].Set)down(row, k);int m  = (tree[row][k].l + tree[row][k].r) / 2;if(y1 <= m)Set(k * 2, y1, y2, v, row);if(m < y2)Set(k * 2 + 1, y1, y2, v, row);tree[row][k].sum = tree[row][k * 2].sum + tree[row][k * 2 + 1].sum;tree[row][k].Max = max(tree[row][k * 2].Max, tree[row][k * 2 + 1].Max);tree[row][k].Min = min(tree[row][k * 2].Min, tree[row][k * 2 + 1].Min);
}void query(int k, int y1, int y2, int row)
{if(tree[row][k].l >= y1 && tree[row][k].r <= y2){tnode.sum += tree[row][k].sum;tnode.Max = max(tnode.Max, tree[row][k].Max);tnode.Min = min(tnode.Min, tree[row][k].Min);return;}if(tree[row][k].add || ~tree[row][k].Set)down(row, k);int m = (tree[row][k].l + tree[row][k].r) / 2;if(y1 <= m)query(k * 2, y1, y2, row);if(m < y2)query(k * 2 + 1, y1, y2, row);
}int main()
{int r, c, m;while(~scanf("%d %d %d", &r, &c, &m)){for(int i = 1; i <= r; ++i)build(1, 1, c, i);while(m--){int t, x1, y1, x2, y2;scanf("%d %d %d %d %d", &t, &x1, &y1, &x2, &y2);if(t == 1){int v;scanf("%d", &v);for(int i = x1; i <= x2; ++i)add(1, y1, y2, v, i);}else if(t == 2){int v;scanf("%d", &v);for(int i = x1; i <= x2; ++i)Set(1, y1, y2, v, i);}else if(t == 3){int sum = 0;int Max = -inf;int Min = inf;for(int i = x1; i <= x2; ++i){tnode.sum = 0;tnode.Max = -inf;tnode.Min = inf;query(1, y1, y2, i);sum += tnode.sum;Max = max(Max, tnode.Max);Min = min(Min, tnode.Min);}printf("%d %d %d\n", sum, Min, Max);}}}return 0;
}

 

这篇关于Fast Matrix Operations (UVA - 11992,二维线段树 + 简单应用)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/861690

相关文章

基于Python实现一个简单的题库与在线考试系统

《基于Python实现一个简单的题库与在线考试系统》在当今信息化教育时代,在线学习与考试系统已成为教育技术领域的重要组成部分,本文就来介绍一下如何使用Python和PyQt5框架开发一个名为白泽题库系... 目录概述功能特点界面展示系统架构设计类结构图Excel题库填写格式模板题库题目填写格式表核心数据结构

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建:像搭积木一样组合控件二、菜单系统:给应用装上“控制中枢”三、事件驱动:让界面“活”

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

《如何确定哪些软件是Mac系统自带的?Mac系统内置应用查看技巧》如何确定哪些软件是Mac系统自带的?mac系统中有很多自带的应用,想要看看哪些是系统自带,该怎么查看呢?下面我们就来看看Mac系统内... 在MAC电脑上,可以使用以下方法来确定哪些软件是系统自带的:1.应用程序文件夹打开应用程序文件夹

Python Flask 库及应用场景

《PythonFlask库及应用场景》Flask是Python生态中​轻量级且高度灵活的Web开发框架,基于WerkzeugWSGI工具库和Jinja2模板引擎构建,下面给大家介绍PythonFl... 目录一、Flask 库简介二、核心组件与架构三、常用函数与核心操作 ​1. 基础应用搭建​2. 路由与参

Spring Boot中的YML配置列表及应用小结

《SpringBoot中的YML配置列表及应用小结》在SpringBoot中使用YAML进行列表的配置不仅简洁明了,还能提高代码的可读性和可维护性,:本文主要介绍SpringBoot中的YML配... 目录YAML列表的基础语法在Spring Boot中的应用从YAML读取列表列表中的复杂对象其他注意事项总

windows和Linux安装Jmeter与简单使用方式

《windows和Linux安装Jmeter与简单使用方式》:本文主要介绍windows和Linux安装Jmeter与简单使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows和linux安装Jmeter与简单使用一、下载安装包二、JDK安装1.windows设

电脑系统Hosts文件原理和应用分享

《电脑系统Hosts文件原理和应用分享》Hosts是一个没有扩展名的系统文件,当用户在浏览器中输入一个需要登录的网址时,系统会首先自动从Hosts文件中寻找对应的IP地址,一旦找到,系统会立即打开对应... Hosts是一个没有扩展名的系统文件,可以用记事本等工具打开,其作用就是将一些常用的网址域名与其对应

CSS 样式表的四种应用方式及css注释的应用小结

《CSS样式表的四种应用方式及css注释的应用小结》:本文主要介绍了CSS样式表的四种应用方式及css注释的应用小结,本文通过实例代码给大家介绍的非常详细,详细内容请阅读本文,希望能对你有所帮助... 一、外部 css(推荐方式)定义:将 CSS 代码保存为独立的 .css 文件,通过 <link> 标签

Python使用Reflex构建现代Web应用的完全指南

《Python使用Reflex构建现代Web应用的完全指南》这篇文章为大家深入介绍了Reflex框架的设计理念,技术特性,项目结构,核心API,实际开发流程以及与其他框架的对比和部署建议,感兴趣的小伙... 目录什么是 ReFlex?为什么选择 Reflex?安装与环境配置构建你的第一个应用核心概念解析组件