首页 > 代码库 > FZU1608 Huge Mission 线段树lazy区间更新+求和
FZU1608 Huge Mission 线段树lazy区间更新+求和
就这破题目坑了我一个大晚上,直到今天一觉醒过来才搞定,原因之一:这题目的题意真的是太狗了,还不如直接看着案例猜来的快啊,
题意:给了你一些区间,x,y,第三个参数w是效率,代表这段时间他的单位时间效率,效率总和就是 (y-x)*w,然后有的时间段会被重复啊,比如前面给了1,4,1,后面又给了2,4,3他们为了是的时间段1,4的效率总和最大肯定是选择 2,4区间的效率值选择3,意思就是后面出现更好的情况就覆盖前面的,问你总得最大效率和
当然这题目坑的原因还有一个就是以前学习线段树 做的时候都是看着学长给的版子做的,完全没有去看他人的版子,导致昨晚没看懂题意的情况下,抱着看别人的代码猜题意的心里,结果弄错了一些细节,因为别人的版子跟我的不一样啊,哭瞎,昨晚先搞定了一种做法的,今天早上才搞定了自己错误的小细节,长脑子了,真的!
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #include<cctype> #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; const int N = 50000 + 5; typedef struct Node { int l,r; int num; }; Node tree[N * 4]; void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].num = 0; if(l == r)return; int mid = (l + r)/2; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void Pushdown(int id) { if(tree[id].num > 0) { tree[id<<1].num = max(tree[id].num,tree[id<<1].num); tree[id<<1|1].num = max(tree[id].num,tree[id<<1|1].num); tree[id].num = 0; } } void update(int L,int R,int l,int r,int id,int val) { if(tree[id].num >= val)return;//剪枝, if(L <= l && R >= r) { if(tree[id].num < val)tree[id].num = val;return; } Pushdown(id); int mid = (l + r)/2; if(L <= mid)update(L,R,l,mid,id<<1,val); if(R > mid)update(L,R,mid+1,r,id<<1|1,val); //else { // update(l,mid,id<<1,val); // update(mid+1,r,id<<1|1,val); //} } int query(int l,int r,int id) { if( l == r)return tree[id].num; Pushdown(id); int mid = (l + r)/2; int ans1 = 0,ans2 = 0; if(l <= mid)ans1 = query(l,mid,id<<1); if(r > mid)ans2 = query(mid+1,r,id<<1|1); return ans1 + ans2; } int main() { int n,m; while(scanf("%d %d",&n,&m) == 2) { build(1,n,1); int q = m; int x,y,w; while(q--) { scanf("%d %d %d",&x,&y,&w); update(x+1,y,1,n,1,w); } int ans = query(1,n,1); printf("%d\n",ans); } return 0; }
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #include<cctype> #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; const int N = 50000 + 5; typedef struct Node { int l,r; int num; }; Node tree[N * 4]; int ans; void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].num = 0; if(l == r)return; int mid = (l + r)/2; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void Pushdown(int id) { if(tree[id].num > 0) { tree[id<<1].num = max(tree[id].num,tree[id<<1].num); tree[id<<1|1].num = max(tree[id].num,tree[id<<1|1].num); tree[id].num = 0; } } void update(int l,int r,int id,int val) { if(tree[id].num >= val)return;//剪枝, if(l <= tree[id].l && r >= tree[id].r) { if(tree[id].num < val)tree[id].num = val;return; } /*Pushdown(id);*/ int mid = (tree[id].l + tree[id].r)/2; if(r <= mid)update(l,r,id<<1,val); else if(l > mid)update(l,r,id<<1|1,val); else { update(l,mid,id<<1,val); update(mid+1,r,id<<1|1,val); } } void query(int l,int r,int id) { if( l == r) { ans += tree[id].num;return; } Pushdown(id); int mid = (tree[id].l + tree[id].r)/2; if(r <= mid)query(l,r,id<<1); else if(l > mid)query(l,r,id<<1|1); else { query(l,mid,id<<1); query(mid+1,r,id<<1|1); } } int main() { int n,m; while(scanf("%d %d",&n,&m) == 2) { build(1,n,1); int q = m; int x,y,w; while(q--) { scanf("%d %d %d",&x,&y,&w); update(x+1,y,1,w); } ans = 0; query(1,n,1); printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。