首页 > 代码库 > 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;
}