HDu 4902 Nice boatセグメントツリー
2685 ワード
//
// ,push_down
// gcd , push_down
#include
#include
#include
using namespace std ;
const int maxn = 1e5+10 ;
#define left v<<1
#define right v<<1|1
int h[maxn];
struct node
{
int l , r ;
int op ;
int x ;
int value ;
}tree[maxn<<2] ;
int gcd(int a , int b)
{
if(b == 0)
return a ;
return gcd(b , a%b) ;
}
void build(int l , int r , int v)
{
tree[v].l = l ;
tree[v].r = r ;
tree[v].op = 0 ;
if(l == r)
{
tree[v].value = h[l] ;
return ;
}
int mid = (l + r) >> 1 ;
build(l , mid , left);
build(mid+1 , r , right) ;
}
void push_down(int v)
{
if(tree[v].l == tree[v].r)
{
if(tree[v].op == 1)
tree[v].value = tree[v].x ;
else if(tree[v].op == 2 && tree[v].value > tree[v].x)
tree[v].value = gcd(tree[v].value , tree[v].x) ;
tree[v].op = 0 ;
return ;
}
if(tree[v].op == 1)
{
tree[left].op = tree[right].op = 1 ;
tree[left].x = tree[right].x = tree[v].x ;
}
else if(tree[v].op == 2)
{
push_down(left) ;
push_down(right) ;
tree[left].op = tree[right].op = 2 ;
tree[left].x = tree[right].x = tree[v].x ;
}
tree[v].op = 0 ;
}
void update(int l , int r , int v , int op ,int x)
{
push_down(v) ;
if(l <= tree[v].l && tree[v].r <= r)
{
tree[v].op = op ;
tree[v].x = x ;
return ;
}
int mid = (tree[v].l + tree[v].r) >> 1 ;
if(l <= mid)
update(l , r , left , op , x) ;
if(r > mid)
update(l , r , right , op , x) ;
}
int query(int pos , int v)
{
push_down(v) ;
if(tree[v].l == pos && tree[v].r == pos)
return tree[v].value ;
int mid = (tree[v].l + tree[v].r) >> 1 ;
if(pos <= mid)return query(pos , left) ;
if(pos > mid)return query(pos , right) ;
}
int main()
{
// freopen("in.txt" ,"r" , stdin) ;
int t ;
scanf("%d" , &t) ;
while(t--)
{
int n ;
scanf("%d" , &n) ;
for(int i = 1;i <= n;i++)
scanf("%d" , &h[i]) ;
int op , x , l , r ;
build(1 , n , 1) ;
int m ;
scanf("%d" , &m) ;
while(m--)
{
scanf("%d%d%d%d" , &op , &l , &r , &x) ;
update(l , r , 1 , op , x) ;
}
for(int i = 1;i <= n;i++)
printf("%d " , query(i , 1)) ;
puts("") ;
}
return 0 ;
}