首页 > 代码库 > 【BZOJ】1012: [JSOI2008]最大数maxnumber（树状数组+区间最值）
【BZOJ】1012: [JSOI2008]最大数maxnumber（树状数组+区间最值）
http://www.lydsy.com/JudgeOnline/problem.php?id=1012
树状数组原来我只懂得sum和add的操作，今天才知道可以有求区间最值的操作，我学习了一下写了个，1a了。
区间最值其实和区间求和差不多，就是将sum数组的含义转移到max，然后通过特定的区间更新max。
在区间求和中，当我们维护max[i]的时候，要找到它前面所有的max[j]来更新，在这里因为是树状数组，所以可以降成一个log级，画图可知，max[i]需要的max只有max[i-2^0],max[i-2^1],max[i-2^2]..max[i-lowbit(i)+1]
更新操作简单，即
void change(int r) { c[r]=num[r]; for(int i=1; i<lowbit(r); i<<=1) c[r]=max(c[r], c[r-i]);}接下来是求区间最值，很容易看出，我们找[l,r]的最值就是找在次区间的max，即递减r，在这里可以有个优化，即当找到一个max[i]，有i-lowbit(i)>=l时，更新后，i直接-=lowbit(i)，然后继续递减。当l>=r就跳出循环
int getk(int l, int r) { int ret=num[r]; while(l<=r) { ret=max(ret, num[r]); for(--r; r-l>=lowbit(r); r-=lowbit(r)) ret=max(ret, c[r]); } return ret;}其实在这里更新操作可以和区间最值放在一起，(现在用c代表max)即c[i]=max(getk(i-lowbit(i)+1, i), num[i]);
本题代码：
#include <cstdio>using namespace std;#define lowbit(x) (x&-x)#define max(a,b) ((a)>(b)?(a):(b))const int N=200005;int num[N], c[N], cnt;int getk(int l, int r) { int ret=num[r]; while(l<=r) { ret=max(ret, num[r]); for(--r; r-l>=lowbit(r); r-=lowbit(r)) ret=max(ret, c[r]); } return ret;}int main() { int n, d, t=0, a; char ch[3]; scanf("%d%d", &n, &d); while(n--) { scanf("%s%d", ch, &a); if(ch[0]==‘A‘) { num[++cnt]=(t+a)%d; c[cnt]=max(getk(cnt-lowbit(cnt)+1, cnt-1), num[cnt]); } else { printf("%d\n", t=getk(cnt-a+1, cnt)); } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。