树状数组(hdu-4325,hdu-1166,pat-1057)

1、hdu-4325

题意:插花,要么给出插花的范围,要么查询某个点的花的个数。

思路:通过更新,每次更新区间S到T的数值,表插入花(这一点一开始没想到),

要么查询某个点的花的数目。

(与以往单纯的区间查询和单点修改的区间和不太相同)。

2、hdu-1166

典型的单点查找,区间求和的问题。(套模板就行)

3、pat-1057(甲级)

题意:堆栈有pop和push两种操作,

现在增加一种新的操作,查询中间值。

如果堆栈的大小n使偶数,查询第n/2个最小数。

思路:每次插入或删除时更新区间,就表示标记或去标记(与hdu-4325类似),

找中间值时可以用二分查找,找到标记次数等于k的就行了。

原文地址:https://www.cnblogs.com/2018zxy/p/10084207.html

时间: 12-07

树状数组(hdu-4325,hdu-1166,pat-1057)的相关文章

树状数组模板 Tree Array

---恢复内容开始--- 这几天去浙江省选当垫底(Orz我是蒟蒻),然后顺便复习下树状数组 关于树状数组,其实很好理解,主要就是lowbit()操作的巧妙 树状数组是一种非常优雅的数据结构.当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组. 换句话说,树状数组最基本的应用: 对于一个数组,如果有多次操作,每次的操作有两种:1.修改数组中某一元素的值,2.求和,求数组元素a[1]+a[2]+…a[num]的和. ——Km的小天地 其实树状数组自己写

hdu 1166:敌兵布阵(树状数组,练习题)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 37773    Accepted Submission(s): 15923 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就

HDU 1166 敌兵布阵 (线段树 & 树状数组)

敌兵布阵 Time Limit:1000MS    Memory Limit:32768KB    64bit IO Format:%I64d & %I64u SubmitStatus 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166 Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的

HDU 1166 敌兵布阵 (树状数组)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166 敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 59954    Accepted Submission(s): 25368 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子

HDU 4325 Flowers(树状数组)

Flowers Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3150    Accepted Submission(s): 1549 Problem Description As is known to all, the blooming time and duration varies between different kinds

HDU 1166 敌兵布阵(树状数组)

之前用过了线段树的做法,树状数组的也补上吧 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int c[50005],n; int lowbit(int x) { return x&(-x); } void add(int i,int x) { while(i <= n) { c[i] += x; i += lowbit(i); } } int cal(i

hdu 1166 树状数组 线段树

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 51177    Accepted Submission(s): 21427 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务

杭电 HDU ACM 1166 敌兵布阵(树状数组)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 55172    Accepted Submission(s): 23126 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务

hdu 1541/poj 2352:Stars(树状数组,经典题)

Stars Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4052    Accepted Submission(s): 1592 Problem Description Astronomers often examine star maps where stars are represented by points on a plan

HDU 5542 The Battle of Chibi dp+树状数组

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5542 题意:给你n个数,求其中上升子序列长度为m的个数 可以考虑用dp[i][j]表示以a[i]结尾的长度为j的上升子序列有多少 裸的dp是o(n2m) 所以需要优化 我们可以发现dp的第3维是找比它小的数,那么就可以用树状数组来找 这样就可以降低复杂度 #include<iostream> #include<cstdio> #include<cstring> #include