暴力线段树......

Nice boat

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=101000;

int n,m;

int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

int a[maxn<<2];

void build(int l,int r,int rt)
{
	if(l==r)
	{
		scanf("%d",a+rt);
		return ;
	}
	int m=(l+r)/2;
	build(lson);build(rson);
}

void push_down(int l,int r,int rt)
{
	if(a[rt])
	{
		a[rt<<1]=a[rt<<1|1]=a[rt];
		a[rt]=0;
	}
}

void upd_1(int L,int R,int x,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		a[rt]=x;
		return ;
	}
	push_down(l,r,rt);
	int m=(l+r)/2;
	if(L<=m) upd_1(L,R,x,lson);
	if(R>m) upd_1(L,R,x,rson);
}

void upd_2(int L,int R,int x,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		if(a[rt])
		{
			if(a[rt]>x)
				a[rt]=gcd(a[rt],x);
			return ;
		}
	}
	push_down(l,r,rt);
	int m=(l+r)/2;
	if(L<=m) upd_2(L,R,x,lson);
	if(R>m) upd_2(L,R,x,rson);
}

void overtree(int l,int r,int rt)
{
	if(l==r)
	{
		printf("%d ",a[rt]);
		return ;
	}
	push_down(l,r,rt);
	int m=(l+r)/2;
	overtree(lson);
	overtree(rson);
}

int main()
{
	int t_t;
	scanf("%d",&t_t);
	while(t_t--)
	{
		scanf("%d",&n);
		build(1,n,1);
		scanf("%d",&m);
		while(m--)
		{
			int kind,left,right,xxx;
			scanf("%d%d%d%d",&kind,&left,&right,&xxx);
			if(kind==1)
			{
				upd_1(left,right,xxx,1,n,1);
			}
			else
			{
				upd_2(left,right,xxx,1,n,1);
			}
		}
		overtree(1,n,1);
		putchar(10);
	}
	return 0;
}

HDOJ 4902 Nice boat,布布扣,bubuko.com

HDOJ 4902 Nice boat

原文：http://blog.csdn.net/ck_boss/article/details/38323375