hdu 4902 Nice boat（线段树区间修改，输出最终序列）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4902

1
10
16807 282475249 1622650073 984943658 1144108930 470211272 101027544 1457850878 1458777923 2007237709 
10
1 3 6 74243042
2 4 8 16531729
1 3 4 1474833169
2 1 8 1131570933
2 7 9 1505795335
2 3 7 101929267
1 4 10 1624379149
2 2 8 2110010672
2 6 7 156091745
1 2 5 937186357

16807 937186357 937186357 937186357 937186357 1 1 1624379149 1624379149 1624379149 

代码如下：

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
const int maxn = 111111;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define lson l, mid, ls
#define rson mid+1, r, rs
//num数组表示该区间是否都是同一个数，如果是num就等于这个数，否则等-1
int num[maxn << 2];
//flag标记，表示该区间是否应该被纯色化（变成一个数）。
int flag[maxn << 2];
//mmax数组表示该区间的最大值，因为gcd只对该区间比x大的起作用
int mmax[maxn << 2];
int GCD(int a, int b)
{
	return a ? GCD(b%a,a) : b;
}
void Pushup(int rt)
{
	if(num[ls] == num[rs])
		num[rt] = num[ls];
	else
		num[rt] = -1;
	mmax[rt] = max(mmax[ls], mmax[rs]);
}

void Pushdown(int rt)
{
	if(flag[rt] != -1)
	{ 
		flag[ls] = flag[rs] = flag[rt];
		mmax[ls] = mmax[rs] = mmax[rt];
		num[ls] = num[rs] = num[rt];
		flag[rt] = -1;
	}
}

void build(int l, int r, int rt)
{
	flag[rt] = -1;
	if(l == r)
	{
		scanf("%d",&num[rt]);
		mmax[rt] = num[rt];//初始化
		return ;
	}
	int mid = (l+r) >> 1;
	build(lson);
	build(rson);
	Pushup(rt);
}

void update(int L, int R, int x, int l, int r, int rt)
{
	if(L <= l && r <= R)
	{
		flag[rt] = num[rt] = mmax[rt] = x;
		return ;
	}
	Pushdown(rt);
	int mid = (l+r) >> 1;
	if(L <= mid)
		update(L, R, x, lson);
	if(mid < R)
		update(L, R, x, rson);
	Pushup(rt);
}

void modify(int L, int R, int x, int l, int r, int rt)
{
	if(L <= l && r <= R && num[rt] > x)
	{
		flag[rt] = num[rt] = mmax[rt] = GCD(num[rt], x);
		return ;
	}
	Pushdown(rt);
	int mid = (l+r) >> 1;
	if(L <= mid && mmax[ls] > x)
		modify(L, R, x, lson);
	if(mid < R && mmax[rs] > x)
		modify(L, R, x, rson);
	Pushup(rt);
}

void Cout(int l, int r, int rt)
{
	if(l == r)
	{
		printf("%d ",num[rt]);
		return ;
	}
	Pushdown(rt);
	int mid = (l+r) >> 1;
	Cout(lson);
	Cout(rson);
}

int main()
{ 
	int T;
	int R, L;
	int n, m;
	int op,l, r, x;
	int i, j, k;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		build(1,n,1);
		scanf("%d",&m);
		for(i = 0; i < m; i++)
		{
			scanf("%d%d%d%d",&op,&l,&r,&x);
			if(op == 1)
			{
				update(l, r, x, 1, n, 1);
			}
			else if(op == 2)
			{
				modify(l, r, x, 1, n, 1);
			}
		}
		Cout(1, n, 1);
		printf("\n");
	}
	return 0;
}

hdu 4902 Nice boat（线段树区间修改，输出最终序列）,布布扣,bubuko.com

hdu 4902 Nice boat（线段树区间修改，输出最终序列）

原文：http://blog.csdn.net/u012860063/article/details/38337715