poj 3468..(存线段树个人模板(自敲)pushdown函数还不理解)

2024-08-31 00:58

本文主要是介绍poj 3468..(存线段树个人模板(自敲)pushdown函数还不理解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

线段树很重要!!!

#include<iostream>
#include<cstdio>using namespace std;
int a[100005];struct node
{int l,r,Min,mid;long long sum,add;
}s[500010];void pushDown(int idx){  long long tmp = s[idx].add;  int l = idx << 1, r = (idx << 1) ^ 1;  s[l].add += tmp;  s[l].sum += (s[l].r - s[l].l + 1) * tmp;  s[r].add += tmp;  s[r].sum += (s[r].r - s[r].l + 1) * tmp;  s[idx].add = 0; 
}void build(int id,int l,int r)
{s[id].l=l;s[id].r=r;s[id].mid=(l+r)/2;s[id].add=0;if(l==r){s[id].sum=a[l]; s[id].Min=a[l];return;}else{build(id*2,l,(l+r)/2);build(id*2+1,(l+r)/2+1,r);s[id].sum=s[id*2].sum+s[id*2+1].sum;s[id].Min=min(s[id*2].Min,s[id*2+1].Min);}
}//int query(int id,int l,int r)//单点查询 
//{
//	if((l<=s[id].l)&&(r>=s[id].r))
//		return s[id].Min;
//	
//	else if(l>s[id].mid)
//		return query(id*2+1,l,r);
//	
//	else if(r<=s[id].mid)
//		return query(id*2,l,r);
//	
//	else
//		return min(query(id*2+1,l,r),query(id*2,l,r));
//}//void up(int id,int l,int r,int ind,int add)//单点更新 
//{
//	if(l==r)
//	{
//		s[id].Min+=add;
//		return ;
//	}
//	int m=(l+r)/2;
//	if(ind<=m)
//		up(id*2,l,m,ind,add);
//	else
//		up(id*2+1,m+1,r,ind,add);
//	
//	s[id].Min=min(s[id*2].Min,s[id*2+1].Min);
//}void update(int idx, int l, int r, int val)   //区间更新
{  if((s[idx].r < l)||(s[idx].l > r))  return ;  if(s[idx].l >= l&&s[idx].r <= r){  s[idx].sum += (s[idx].r - s[idx].l + 1) * val;  s[idx].add += val;  return ;  }  if(s[idx].add != 0)  pushDown(idx);  update(idx * 2, l, r, val);  update(idx * 2 + 1, l, r, val);  s[idx].sum = s[idx * 2].sum + s[idx * 2 + 1].sum;  
}long long query(int idx, int l, int r)     //区间查询 
{ if(s[idx].r < l||s[idx].l > r)  return 0;  if(s[idx].l >= l&&s[idx].r <= r)  return s[idx].sum;  if(s[idx].add != 0)  pushDown(idx);  long long x = query(idx * 2, l, r);  long long y = query(idx * 2 + 1, l, r);  return x + y;  
}  int main()
{int n, i, q, l, r;long long t;  char ord;  while(~scanf("%d%d", &n, &q)){  for(i = 1;i <= n;i++)  scanf("%lld", &a[i]);  build(1, 1, n);  while(q--){  scanf("\n%c", &ord);  if(ord == 'Q'){  scanf("%d%d", &l, &r);  printf("%lld\n", query(1, l, r));  } else {  scanf("%d %d %lld", &l, &r, &t);  update(1, l, r, t);  }  }  }  return 0;  
}  
//	for(int i=1;i<=20;i++) a[i]=i;
//	
//	for(int i=1;i<=20;i++) printf("%d ",a[i]);
//	
//	build(1,1,20);
//	
//	up(1,1,20,4,30);
//  
//  	printf("%d\n",query(1,1,20));
//  
//  	//up(1,1,20,4,-40);
//  
//  	printf("%d\n",query(1,2,20));
//  
//  	//up(1,1,5,2,12);
//  
//  	printf("%d\n",query(1,4,20));
//  
// 	//up(1,1,5,2,12);
//  
// 	 printf("%d\n",query(1,5,20));
// 	 for(int i=1;i<=20;i++) printf("%d ",a[i]);
//  
//	//freopen("in.txt","r",stdin);int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,1,n);int t;scanf("%d",&t);for(int i=0;i<t;i++){int a,b;scanf("%d %d",&a,&b);//cin>>a>>b;if(a<b)printf("%d\n",query(1,a,b));else if(a>=b)printf("%d\n",query(1,b,a));}
//	
//	
//	
//	
//	
//	
//	return 0;
//}


这篇关于poj 3468..(存线段树个人模板(自敲)pushdown函数还不理解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1122434

相关文章

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

使用DeepSeek搭建个人知识库(在笔记本电脑上)

《使用DeepSeek搭建个人知识库(在笔记本电脑上)》本文介绍了如何在笔记本电脑上使用DeepSeek和开源工具搭建个人知识库,通过安装DeepSeek和RAGFlow,并使用CherryStudi... 目录部署环境软件清单安装DeepSeek安装Cherry Studio安装RAGFlow设置知识库总

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》:本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》:本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意

深入理解Apache Airflow 调度器(最新推荐)

《深入理解ApacheAirflow调度器(最新推荐)》ApacheAirflow调度器是数据管道管理系统的关键组件,负责编排dag中任务的执行,通过理解调度器的角色和工作方式,正确配置调度器,并... 目录什么是Airflow 调度器?Airflow 调度器工作机制配置Airflow调度器调优及优化建议最

Java function函数式接口的使用方法与实例

《Javafunction函数式接口的使用方法与实例》:本文主要介绍Javafunction函数式接口的使用方法与实例,函数式接口如一支未完成的诗篇,用Lambda表达式作韵脚,将代码的机械美感... 目录引言-当代码遇见诗性一、函数式接口的生物学解构1.1 函数式接口的基因密码1.2 六大核心接口的形态学