hdu6406 Taotao Picks Apples(线段树)
2024-08-25 12:04:42
Taotao Picks Apples
解题思路
建立一颗线段树,维护当前区间内的最大值maxx和可摘取的苹果数num。最大值很容易维护,主要是可摘取的苹果数怎么合并。合并左右孩子时,左孩子里可摘取苹果必然还是可以摘取,所以我们讨论右孩子。
如果右孩子的最大值小于左孩子,根据题目条件,右孩子里的苹果都不能摘取了,合并结果就是左孩子的数量,如果右孩子的最大值大于左孩子,那么右孩子里存在可以摘取的苹果,接下来就是一个递归的过程,假设右孩子为t,左孩子的最大值为k,如果t->lchild->maxx < k, 那么t->lchild中不存在可摘取的苹果,递归t->rchild求t->rchild中的数量,如果t->lchild->maxx > k,那么t->lchild和t->rchild中都存在可摘取的苹果,而此时t->rchild已经不受k的影响了,只受t->lchild->maxx的影响,所以可以直接加上t->rchild->num,再加上递归求出的t->lchild中的数量。
代码如下
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
inline int read(){
int res = 0, w = 0; char ch = 0;
while(!isdigit(ch)){
w |= ch == '-', ch = getchar();
}
while(isdigit(ch)){
res = (res << 3) + (res << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -res : res;
}
const int N = 100005;
int v[N];
struct node{
int l, r;
int maxx, num;
}tree[N << 2];
int get(int k, int x) //递归过程
{
if(tree[k].num == 1){
return tree[k].maxx > x;
}
if(tree[2*k].maxx > x)
return get(2*k, x) + (tree[k].num - tree[2*k].num);
else if(tree[2*k].maxx == x)
return tree[k].num - tree[2*k].num;
else
return get(2*k+1, x);
}
void pushup(int k) //合并
{
tree[k].maxx = max(tree[2*k].maxx, tree[2*k+1].maxx);
tree[k].num = tree[2*k].num;
if(tree[2*k+1].maxx > tree[2*k].maxx)
tree[k].num += get(2*k+1, tree[2*k].maxx);
}
void build(int k, int l, int r)
{
tree[k].l = l, tree[k].r = r;
if(l == r){
tree[k].maxx = v[l];
tree[k].num = 1;
return;
}
int mid = (l + r) / 2;
build(2*k, l, mid);
build(2*k+1, mid+1, r);
pushup(k);
}
void update(int k, int p, int q)
{
if(tree[k].l == tree[k].r){
tree[k].maxx = q;
return;
}
int mid = (tree[k].l + tree[k].r) / 2;
if(p <= mid)
update(2*k, p, q);
else
update(2*k+1, p, q);
pushup(k);
}
inline int query()
{
return tree[1].num;
}
int main()
{
int t;
cin >> t;
while(t --){
int n, m;
n = read(), m = read();
for(int i = 1; i <= n; i ++)
v[i] = read();
build(1, 1, n);
for(int i = 1; i <= m; i ++){
int p, q;
p = read(), q = read();
update(1, p, q);
printf("%d\n", query());
update(1, p, v[p]);
}
}
return 0;
}
最新文章
- Linux下管道编程
- mysql源码解读之事务提交过程(二)
- 查找“CDN、负载均衡、反向代理”等大型网络真实IP地址的方法
- 自定义控件(视图)2期笔记09:自定义视图之继承自ViewGroup(仿ViewPager效果案例)
- 未能写入输出文件 c:/WINDOWS/Microsoft.NET/Framework/v2.0.50727/Temporary
- js本地存储解决方案(localStorage与userData)
- Linux PostgreSQL 基础配置指南
- J2EE项目中异常处理
- 初探中间件(middleware)
- 一把刀终极配置 For XP v2.0 免费绿色版
- EntityFramework Core迁移时出现数据库已存在对象问题解决方案
- 【.net 深呼吸】监听剪贴板更新(针对Vista之后系统)
- Python函数篇(3)-内置函数、文件处理
- 微信小程序基于最新版1.0开发者工具分享-小试牛刀(视频)+发布流程
- slf4j 与 log4j2 实战讲解与日志分割
- Asp.Net Core 2.0 项目实战(7)MD5加密、AES&;DES对称加解密
- 基于element ui的级联选择器组件实现的分类后台接口
- linux之关于学习必备知识
- PDF.js 分片下载的介绍2:分片下载demo
- SharePoint开启错误提示
热门文章
- 当一个控件属性不存在的时候,IDE会出错在这里(说明是TWinControl.ReadState在读属性,并执行相关动作)
- Spring之基于注解的注入
- 3021Java_数据类型
- 浅谈我在.net core一年里的收获
- Java项目接入sso单点登录
- 怎么安装IDEA?
- 【设计模式】行为型10中介者模式(Mediator Pattern)
- Java 8 新特性-Stream更优雅的处理集合入门
- resolv.conf 的超时(timeout)与重试(attempts)机制
- You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near &#39;wher id = 41&#39; at line 1