HDu 3954(セグメントツリー区間更新)

転載マーク:http://www.cnblogs.com/wang-jue/articles/2920341.html
考え方:この問題で得られた経験は各英雄の等級と関係があり、一般的にはセグメントツリーで各英雄まで更新される可能性がありますが、これはタイムアウトに違いありません.だから私はlazyの思想をどのように使うかを考えて、私はもしこの区間の英雄がすでに最高の等級であれば、この区間はlazyでマークすることができるに違いないことを発見して、書き終わってからTLEになりました.そこでこのブログを探して、彼の最初の考えも私と同じです.ここには実は隠れた情報があり、もしこの区間のヒーローがアップグレードできなかったら、この区間はlazyでマークできるのは間違いありません.もしこの区間にヒーローがアップグレードするなら、葉ノードに更新します.このように、この区間で英雄がアップグレードする場合、彼が必要とする最小限の経験を示すドメインを追加する必要があります.よく考えてみると、この区間に英雄がアップグレードしなければ、この区間の最大経験値は最大の等級*倍率を直接加えればいいに違いない.したがってlazyは入力毎の倍率を記録するだけでよい.これはこの問題で一番考えにくいところです.
まず私のTLEのコードをください.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 10005;
struct Segment
{
	int l,r;
	int max_exp,rank;
	int	lazy,cover;
}tree[maxn<<2];
int n,k,m,exprience[15];

void build(int rt,int l,int r)
{
	tree[rt].l = l, tree[rt].r = r;
	tree[rt].rank = 1;
	tree[rt].max_exp = tree[rt].lazy =tree[rt].cover = 0;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}

void PushDown(int rt)
{
	if(tree[rt].lazy)
	{
		tree[rt<<1].lazy += tree[rt].lazy;
		tree[rt<<1|1].lazy += tree[rt].lazy;
		tree[rt<<1].max_exp += k * tree[rt].lazy;
		tree[rt<<1|1].max_exp += k * tree[rt].lazy;
		tree[rt].lazy = 0;
	}
}

void update(int rt,int l,int r,int val)
{
	if(tree[rt].l == tree[rt].r)
	{
		tree[rt].max_exp += tree[rt].rank * val;
		if(tree[rt].max_exp >= exprience[tree[rt].rank+1] && tree[rt].rank < k)
			tree[rt].rank++;
		if(tree[rt].rank >= k) 
		{
			tree[rt].cover = 1;
			tree[rt].rank = k;
		}
		return;
	}
	if(tree[rt].cover && l <= tree[rt].l && tree[rt].r <= r)
	{
		tree[rt<<1].cover = tree[rt<<1|1].cover = 1;
		tree[rt].lazy += val;
		tree[rt].max_exp += k * val;
		return;
	}
	PushDown(rt);
	int mid = (tree[rt].l + tree[rt].r) >> 1;
	if(l <= mid) update(rt<<1,l,r,val);
	if(mid < r) update(rt<<1|1,l,r,val);
	if(tree[rt<<1].cover && tree[rt<<1|1].cover)
		tree[rt].cover = 1;
	tree[rt].max_exp = max(tree[rt<<1].max_exp,tree[rt<<1|1].max_exp);
}

int query(int rt,int l,int r)
{
	if(l <= tree[rt].l && tree[rt].r <= r)
		return tree[rt].max_exp;
	PushDown(rt);
	int mid = (tree[rt].l + tree[rt].r) >> 1;
	int ans = 0;
	if(l <= mid) ans = max(ans,query(rt<<1,l,r));
	if(mid < r) ans = max(ans,query(rt<<1|1,l,r));
	return ans;
}

int main()
{
	int t,cas = 1,a,b,c;
	char str[2];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&k,&m);
		for(int i = 2; i <= k; i++)
			scanf("%d",&exprience[i]);
		build(1,1,n);
		printf("Case %d:
",cas++);
		while(m--)
		{
			getchar();
			scanf("%s",str);
			if(str[0] == 'W')
			{
				scanf("%d%d%d",&a,&b,&c);
				update(1,a,b,c);
			}
			else
			{
				scanf("%d%d",&a,&b);
				printf("%d
",query(1,a,b));
			}
		}
	}
	return 0;
}

これは他の人の考えを理解したコードです.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 10005;
struct Segment
{
	int l,r;
	int max_exp,dis_min,rank;
	int	lazy;
}tree[maxn<<2];
int n,k,m,exprience[15];

void build(int rt,int l,int r)
{
	tree[rt].l = l, tree[rt].r = r;
	tree[rt].rank = 1;
	tree[rt].dis_min = exprience[2];
	tree[rt].max_exp = tree[rt].lazy = 0;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}

void PushUp(int rt)
{
	tree[rt].max_exp = max(tree[rt<<1].max_exp,tree[rt<<1|1].max_exp);
	tree[rt].dis_min = min(tree[rt<<1].dis_min,tree[rt<<1|1].dis_min);
	tree[rt].rank = max(tree[rt<<1].rank,tree[rt<<1|1].rank);
}

void PushDown(int rt)
{
	if(tree[rt].lazy)
	{
		tree[rt<<1].lazy += tree[rt].lazy;
		tree[rt<<1|1].lazy += tree[rt].lazy;
		tree[rt<<1].max_exp += tree[rt<<1].rank * tree[rt].lazy;
		tree[rt<<1|1].max_exp += tree[rt<<1|1].rank * tree[rt].lazy;
		tree[rt<<1].dis_min -= tree[rt].lazy;
		tree[rt<<1|1].dis_min -= tree[rt].lazy;
		tree[rt].lazy = 0;
	}
}

void update(int rt,int l,int r,int val)
{
	if(l <= tree[rt].l && tree[rt].r <= r)
	{
		if(tree[rt].dis_min > val)	//        
		{
			tree[rt].lazy += val;
			tree[rt].max_exp += tree[rt].rank * val;
			tree[rt].dis_min -= val;
			return;
		}
		else if(tree[rt].l == tree[rt].r)
		{
			tree[rt].max_exp += tree[rt].rank * val;
			while(tree[rt].max_exp >= exprience[tree[rt].rank + 1])
				tree[rt].rank++;
			tree[rt].dis_min = (exprience[tree[rt].rank + 1] - tree[rt].max_exp) / tree[rt].rank + ((exprience[tree[rt].rank + 1] - tree[rt].max_exp) % tree[rt].rank != 0);
			return;
		}
	}
	PushDown(rt);
	int mid = (tree[rt].l + tree[rt].r) >> 1;
	if(l <= mid) update(rt<<1,l,r,val);
	if(mid < r) update(rt<<1|1,l,r,val);
	PushUp(rt);
}

int query(int rt,int l,int r)
{
	if(l <= tree[rt].l && tree[rt].r <= r)
		return tree[rt].max_exp;
	PushDown(rt);
	int mid = (tree[rt].l + tree[rt].r) >> 1;
	int ans = 0;
	if(l <= mid) ans = max(ans,query(rt<<1,l,r));
	if(mid < r) ans = max(ans,query(rt<<1|1,l,r));
	return ans;
}

int main()
{
	int t,cas = 1,a,b,c;
	char str[2];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&k,&m);
		for(int i = 2; i <= k; i++)
			scanf("%d",&exprience[i]);
		exprience[k+1] = 1 << 30;
		build(1,1,n);
		printf("Case %d:
",cas++);
		while(m--)
		{
			getchar();
			scanf("%s",str);
			if(str[0] == 'W')
			{
				scanf("%d%d%d",&a,&b,&c);
				update(1,a,b,c);
			}
			else
			{
				scanf("%d%d",&a,&b);
				printf("%d
",query(1,a,b));
			}
		}
		printf("
");
	}
	return 0;
}