当前位置: 开发笔记 > 编程语言 > 正文

HDU5126starscdq分治+树状数组

作者：用户fkise9sswv | 来源：互联网 | 2023-05-19 06:40

题目链接：点击打开链接题意：T个casen个操作1、(x,y,z)在三维平面的点上增加12、询问区间范围内的权值和。思路：cdq分治套cdq分治，然后套

题目链接：点击打开链接

题意：

T个case

n个操作

1、 (x,y,z) 在三维平面的点上增加1

2、询问区间范围内的权值和。

思路：

cdq分治套cdq分治，然后套树状数组即可。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
const int inf = 1e8;
const double eps = 1e-8;
const double pi = acos(-1.0);
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != &＃39;-&＃39; && (c<&＃39;0&＃39; || c>&＃39;9&＃39;)) c = getchar();
	sgn = (c == &＃39;-&＃39;) ? -1 : 1;
	ret = (c == &＃39;-&＃39;) ? 0 : (c - &＃39;0&＃39;);
	while (c = getchar(), c >= &＃39;0&＃39;&&c <= &＃39;9&＃39;) ret = ret * 10 + (c - &＃39;0&＃39;);
	ret *= sgn;
	return 1;
}
template 
inline void pt(T x) {
	if (x <0) { putchar(&＃39;-&＃39;); x = -x; }
	if (x>9) pt(x / 10);
	putchar(x % 10 + &＃39;0&＃39;);
}
using namespace std;
const int N = 50010 <<3;
int maxn, c[N];
int lowbit(int x){ return x&-x; }
void add(int x,int val){
	while (x <= maxn)c[x] += val, x += lowbit(x);
}
int sum(int x){
	int ans = 0;
	while (x)ans += c[x], x -= lowbit(x);
	return ans;
}
typedef long long ll;
typedef pair pii;
class Node{
public:
	int op, x, y, z, id, add, ans;
	Node(){}
	Node(int _op, int _x, int _y, int _z, int _id, int _add) : op(_op), x(_x), y(_y), z(_z), id(_id), add(_add), ans(0){}
};
int ans[N];
bool cmp(const Node &e1, const Node & e2) {
	if (e1.x == e2.x)return e1.id > 1;
	tt = 1;
	for (int i = l; i <= mid; i++)if (t[i].op == 1)v[++tt] = t[i];
	for (int i = mid + 1; i <= r; i++)if(t[i].op == 2)v[++tt] = t[i];	
	sort(v + 1, v + tt + 1, cmp2);
	for (int i = 1; i <= tt; i++)
	if (v[i].op == 1)
		add(v[i].z, 1);
	else
		ans[v[i].id] += sum(v[i].z) * v[i].add;
	for (int i = 1; i <= tt; i++)if (v[i].op == 1)add(v[i].z, -1);
	cal(l, mid); cal(mid + 1, r);
}
void solve(int l, int r){
	if (l == r)return;
	int mid = (l + r) >> 1;
	top = 1;
	for (int i = l; i <= mid; i++)if (q[i].op == 1)t[++top] = q[i];
	for (int i = mid + 1; i <= r; i++)if (q[i].op == 2)	t[++top] = q[i];	
	sort(t + 1, t + top + 1, cmp);
	cal(1, top);
	solve(l, mid); solve(mid + 1, r);
}
vectorG;
int main(){
	int T; rd(T);
	while (T-- > 0){
		rd(n);
		G.clear();
		int siz = 0;
		for (int i = 1, op, x1, x2, y1, y2, z1, z2; i <= n; i++)
		{
			rd(op);
			if (op == 1)
			{
				q[++siz].op = 1;
				ans[i] = -1;
				rd(q[siz].x); rd(q[siz].y); rd(q[siz].z); G.push_back(q[siz].z);
			}
			else {
				rd(x1); rd(y1); rd(z1); rd(x2); rd(y2); rd(z2);
				G.push_back(z2); G.push_back(z1); G.push_back(z1 - 1);
				ans[i] = 0;
				q[++siz] = Node(2, x2, y2, z2, i, 1);
				q[++siz] = Node(2, x1 - 1, y2, z2, i, -1);
				q[++siz] = Node(2, x2, y1 - 1, z2, i, -1);
				q[++siz] = Node(2, x1 - 1, y1 - 1, z2, i, 1);

				q[++siz] = Node(2, x2, y2, z1 - 1, i, -1);
				q[++siz] = Node(2, x1 - 1, y2, z1 - 1, i, 1);
				q[++siz] = Node(2, x2, y1 - 1, z1 - 1, i, 1);
				q[++siz] = Node(2, x1 - 1, y1 - 1, z1 - 1, i, -1);
			}
		}
		sort(G.begin(), G.end());
		G.erase(unique(G.begin(), G.end()), G.end());
		maxn = G.size();
		for (int i = 1; i <= siz; i++)q[i].z = lower_bound(G.begin(), G.end(), q[i].z) - G.begin() + 1;
		solve(1, siz);
		for (int i = 1; i <= n; i++)if (ans[i] >= 0)pt(ans[i]), putchar(&＃39;\n&＃39;);
	}
	return 0;
}

HDU 5126 stars cdq分治+树状数组

推荐阅读

java
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
java
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
js
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
js
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
js
高质量SQL书写的30条建议

本文提供了30条关于优化SQL的建议，包括避免使用select *，使用具体字段，以及使用limit 1等。这些建议是基于实际开发经验总结出来的，旨在帮助读者优化SQL查询。 ... [详细]

蜡笔小新 2023-12-13 13:24:33
js
asp.net微信公众平台开发目录汇总陆续更新的相关内容

本文内容为asp.net微信公众平台开发的目录汇总，包括数据库设计、多层架构框架搭建和入口实现、微信消息封装及反射赋值、关注事件、用户记录、回复文本消息、图文消息、服务搭建（接入）、自定义菜单等。同时提供了示例代码和相关的后台管理功能。内容涵盖了多个方面，适合综合运用。 ... [详细]

蜡笔小新 2023-12-14 22:40:22
js
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
js
基于layUI的图片上传前预览功能的2种实现方式

本文介绍了基于layUI的图片上传前预览功能的两种实现方式：一种是使用blob+FileReader，另一种是使用layUI自带的参数。通过选择文件后点击文件名，在页面中间弹窗内预览图片。其中，layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块，并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]

蜡笔小新 2023-12-14 17:06:58
js
Alink回归预测的不完善问题及期待

本文讨论了Alink回归预测的不完善问题，指出目前主要针对Python做案例，对其他语言支持不足。同时介绍了pom.xml文件的基本结构和使用方法，以及Maven的相关知识。最后，对Alink回归预测的未来发展提出了期待。 ... [详细]

蜡笔小新 2023-12-14 14:25:33
js
C#之数据集：DataSet对象的使用及相关方法详解

本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]

蜡笔小新 2023-12-14 12:09:13
java
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
js
SpringBoot集成前端模版（thymeleaf）的配置步骤

本文介绍了在SpringBoot中集成thymeleaf前端模版的配置步骤，包括在application.properties配置文件中添加thymeleaf的配置信息，引入thymeleaf的jar包，以及创建PageController并添加index方法。 ... [详细]

蜡笔小新 2023-12-14 10:11:46
js
ABAP开发发送邮件程序的配置和代码整理

本文介绍了通过ABAP开发往外网发邮件的需求，并提供了配置和代码整理的资料。其中包括了配置SAP邮件服务器的步骤和ABAP写发送邮件代码的过程。通过RZ10配置参数和icm/server_port_1的设定，可以实现向Sap User和外部邮件发送邮件的功能。希望对需要的开发人员有帮助。摘要长度：184字。 ... [详细]

蜡笔小新 2023-12-13 15:50:17
java
Java验证码——kaptcha的使用配置及样式

本文介绍了如何使用kaptcha库来实现Java验证码的配置和样式设置，包括pom.xml的依赖配置和web.xml中servlet的配置。 ... [详细]

蜡笔小新 2023-12-13 13:58:25
js
指针的引用以及在什么情况下使用指针的引用

本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址，通过指针可以修改指针所指的变量的值。然而，如果想要修改指针的指向，就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法，并思考了在修改指针的指向后，取指针的输出结果。 ... [详细]

蜡笔小新 2023-12-13 12:54:29

用户fkise9sswv

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章