好贷网好贷款

HDU 3954 线段树 特殊LAZY操作

发布时间:2016-12-3 14:56:59 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 3954 线段树 特殊LAZY操作",主要涉及到HDU 3954 线段树 特殊LAZY操作方面的内容,对于HDU 3954 线段树 特殊LAZY操作感兴趣的同学可以参考一下。

此题的线段树结构体中要有  data[k].min  最小升级系数的引入 代表此区间内有人升级所需的最小经验值 因为如果此区间中有人升级,则需要进行LAZY操作 注意此处的经验值是‘绝对’经验值 即:   d=up[data[k].le+1]-data[k].exp;   data[k].min=d/data[k].le;   if (d%data[k].le!=0) data[k].min++;  可以直接和读入的exp进行比较   而且在两种情况下都要进行LAZY操作 成段更新的区间剖分时,和此区间中有人要升级时。 因为此时用区间的lazy值叠加的话会影响结果,只有区间内的等级都一样,lazy才可以叠加   #include "stdio.h" #include "string.h" #include "math.h" #include "stdlib.h" int up[21]; int ans; struct comp { int l,r,mid; int exp,le,lazy,min; } data[40001]; int min(int a,int b) { if (a<b) return a; else return b; } int max(int a,int b) { if (a<b) return b; else return a; } void build(int l,int r,int k) { data[k].l=l; data[k].r=r; data[k].mid=(l+r)/2; data[k].exp=0; // 记录此区间经验最大值 data[k].le=1; // 记录此区间等级最大值 data[k].min=up[2]; // 记录此区间升级最小系数 data[k].lazy=0; if (l==r) return ; build(l,data[k].mid,k*2); build(data[k].mid+1,r,k*2+1); } void PushDown(int k) { if (data[k].lazy!=0) { data[k*2].exp+=data[k*2].le*data[k].lazy; data[k*2].lazy+=data[k].lazy; data[k*2].min-=data[k].lazy; data[k*2+1].exp+=data[k*2+1].le*data[k].lazy; data[k*2+1].lazy+=data[k].lazy; data[k*2+1].min-=data[k].lazy; data[k].lazy=0; } return ; } void PushUp(int k) { data[k].exp=max(data[k*2].exp,data[k*2+1].exp); data[k].le=max(data[k*2].le,data[k*2+1].le); data[k].min=min(data[k*2].min,data[k*2+1].min); } void update(int l,int r,int k,int exp) { int d; if (data[k].l==data[k].r) { data[k].exp+=data[k].le*exp; while (data[k].exp>=up[data[k].le+1]) data[k].le++; d=up[data[k].le+1]-data[k].exp; data[k].min=d/data[k].le; if (d%data[k].le!=0) data[k].min++; return ; } if (data[k].l==l && data[k].r==r) { if (exp>=data[k].min) // 若存在升级情况,分别进入两个子区间更新 { PushDown(k); update(l,data[k].mid,k*2,exp); update(data[k].mid+1,r,k*2+1,exp); PushUp(k); } else { data[k].exp+=data[k].le*exp; data[k].min-=exp; data[k].lazy+=exp; } return ; } PushDown(k); if (r<=data[k].mid) update(l,r,k*2,exp); else if (l>data[k].mid) update(l,r,k*2+1,exp); else { update(l,data[k].mid,k*2,exp); update(data[k].mid+1,r,k*2+1,exp); } PushUp(k); } void search(int l,int r,int k) { if (data[k].l==l && data[k].r==r) { if (ans<data[k].exp) ans=data[k].exp; return ; } PushDown(k); if (r<=data[k].mid) search(l,r,k*2); else if (l>data[k].mid) search(l,r,k*2+1); else { search(l,data[k].mid,k*2); search(data[k].mid+1,r,k*2+1); } } int main() { int t,ii,i,k,m,n,a,b,c; char ch[10]; scanf("%d",&t); for (ii=1;ii<=t;ii++) { printf("Case %d:\n",ii); scanf("%d%d%d",&n,&k,&m); for (i=2;i<=k;i++) scanf("%d",&up[i]); up[k+1]=0x7fffffff; build(1,n,1); while (m--) { scanf("%s",ch); if (ch[0]=='W') { scanf("%d%d%d",&a,&b,&c); update(a,b,1,c); } else { ans=0; scanf("%d%d",&a,&b); search(a,b,1); printf("%d\n",ans); } } printf("\n"); } return 0; }  

上一篇:谷歌三大核心技术(二)Google MapReduce中文版
下一篇:android 定制对话框 Layoutlnflater

相关文章

相关评论