hrbust 1832 股票难题II

发布时间:2016-12-8 10:03:51 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hrbust 1832 股票难题II",主要涉及到hrbust 1832 股票难题II方面的内容,对于hrbust 1832 股票难题II感兴趣的同学可以参考一下。

今天写了一道线段树区间合并的操作,刚开始遇到各种bug,有些气馁,但后来自己慢慢的通过模拟发现了并慢慢的改正了一些bug,经过一系列的改正,最终完全用线段树AC了,并与用rmq预处理比较时间和空间复杂度,发现线段树的跑的时间是716ms,空间复杂度是2952k, 而rmq的跑了1222ms,空间复杂度是14020k,对比一下,线段树完成的求最值操作远远优于rmq~~~ 线段树代码如下: #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #define inf 99999999 #define Maxn 100005 using namespace std; int maxv[Maxn<<2]; //定义最大值 int minv[Maxn<<2]; //最小值 int val[Maxn]; int mov[Maxn<<2]; //某一区间内的最大差值 void build(int l, int r, int rt) //建树 { if(l==r) { maxv[rt]=val[l]; minv[rt]=val[l]; mov[rt]=0; return ; } int mid=(l+r)/2; build(l, mid, rt<<1); build(mid+1, r, rt<<1|1); maxv[rt]=max(maxv[rt<<1], maxv[rt<<1|1]); //当前节点最大的差值来源于3部分 minv[rt]=min(minv[rt<<1], minv[rt<<1|1]); //一部分来源于左子结点的最大差值和右子结点的最大差值 int pp=max(mov[rt<<1], mov[rt<<1|1]); //还有合并之后的区间的右子结点最大值-左子结点最小值 mov[rt]=max(maxv[rt<<1|1]-minv[rt<<1], pp); //取三部分的最大值为当前节点的最大差值 } int querymax(int L, int R, int l, int r, int rt) //求某一给定区间的在区间[l, r]的最大值 { if(L<=l&&r<=R) return maxv[rt]; int mid=(l+r)/2; int s1=-inf, s2=-inf; if(L<=mid) s1=querymax(L, R, l, mid, rt*2); if(R>mid) s2=querymax(L, R, mid+1, r, rt*2+1); return max(s1, s2); } int querymin(int L, int R, int l, int r, int rt) //求某一给定区间的在区间[l, r]的最小值 { if(L<=l&&r<=R) return minv[rt]; int mid=(l+r)/2; int s1=inf, s2=inf; if(L<=mid) s1=querymin(L, R, l, mid, rt*2); if(R>mid) s2=querymin(L, R, mid+1, r, rt*2+1); return min(s1, s2); } int query(int L, int R, int l, int r, int rt) //询问区间[L, R]在区间[l, r]内的最大差值 { if(L<=l&&r<=R) { return mov[rt]; } int mid=(l+r)/2; if(R<=mid) return query(L, R, l, mid, rt<<1); else if(L>mid) return query(L, R, mid+1, r, rt<<1|1); else { int t1=-inf, t2=-inf, t3=-inf, t4=-inf; if(L<=mid) t1 = query(L, R, l, mid, rt<<1); if(R>mid) t2 = query(L, R, mid+1, r, rt<<1|1); //最大差值也由以上三部分组成 t3 = max(t1, t2); t4 = querymax(L, R, mid+1, r, rt<<1|1)-querymin(L, R, l, mid, rt<<1); return max(t3, t4); } } int main() { int n, m; int a, b; while(scanf("%d", &n)!=EOF) { for(int i=0; i<=n; i++) { scanf("%d", &val[i]); } build(0, n, 1); scanf("%d", &m); while(m--) { int ans; scanf("%d%d",&a, &b); ans=query(a, b, 0, n, 1); printf("%d\n", ans); } printf("\n"); } return 0; } RMQ代码如下: #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <algorithm> #define maxn 100050 using namespace std; int mac[maxn<<3]; int dpl[maxn<<1][25]; int dpm[maxn<<1][25]; int val[maxn]; void makermq(int n){ int i, j; for (i=0; i<=n; i++){ dpl[i][0] = dpm[i][0] = val[i]; } for (j=1; (1<<j) <=n; j++){ for (i=0; i+(1<<j)-1<=n; i++){ dpm[i][j] = max(dpm[i][j-1], dpm[i+(1<<(j-1))][j-1]); dpl[i][j] = min(dpl[i][j-1], dpl[i+(1<<(j-1))][j-1]); } } } int rmqm(int l, int r){ int k = (int)(log((r-l+1)*1.0) / log(2.0)); return max(dpm[l][k], dpm[r-(1<<k)+1][k]); } int rmql(int l, int r){ int k = (int)(log((r-l+1)*1.0) / log(2.0)); return min(dpl[l][k], dpl[r-(1<<k)+1][k]); } void build(int l, int r, int rt){ if (l == r){ mac[rt] = 0; return; } int mid = (l+r)>>1; build(l, mid, rt<<1); build(mid+1, r, rt<<1|1); mac[rt] = max(mac[rt<<1], mac[rt<<1|1]); mac[rt] = max(mac[rt], rmqm(mid+1,r) - rmql(l,mid)); } int query(int L, int R, int l, int r, int rt){ if (L <= l && r <= R){ return mac[rt]; } int mid = (l+r)>>1; if (R <= mid){ return query(L, R, l, mid, rt<<1); } else if (L > mid){ return query(L, R, mid+1, r, rt<<1|1); } else{ int t1 = query(L, R, l, mid, rt<<1); int t2 = query(L, R, mid+1, r, rt<<1|1); int t3 = max(t1, t2); t3 = max(t3, rmqm(mid+1, R)-rmql(L, mid)); return t3; } } int main(){ int n, q; int i, j, k; while (scanf("%d",&n)!=EOF){ for (i=0; i<=n; i++) scanf("%d", &val[i]); makermq(n); build(0, n, 1); scanf("%d", &q); int a, b; while (q--){ scanf("%d %d", &a, &b); int res = query(a, b, 0, n, 1); printf("%d\n",res); } puts(""); } return 0; }

上一篇:(android功能代码) android文件上传服务器
下一篇:HDU 4696 Answers (水题)

相关文章

相关评论