多校第四场
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; #define Ls rt<<1 #define Rs rt<<1|1 #define Lson l,m,rt<<1 #define Rson m+1,r,rt<<1|1 int const MAXN = 1000010; struct Tree{ int l,r; int v,add; }tree[MAXN<<2]; int Gcd(int a,int b){ if(!b) return a; return Gcd(b,a%b); } inline void PushUp(int rt){ if(tree[Ls].v == tree[Rs].v)tree[rt].v = tree[Ls].v; else tree[rt].v = -1 ; } inline void PushDown(int rt){ if(tree[rt].add != -1){ tree[Ls].add = tree[Rs].add = tree[rt].add; tree[Ls].v = tree[Rs].v = tree[rt].add; tree[rt].add = -1; } } void build(int l,int r,int rt){ tree[rt].add = -1; if(l == r){ scanf("%d",&tree[rt].v); return ; } int m = (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){ tree[rt].v = tree[rt].add = x; return ; } PushDown(rt); int m = (l+r) >> 1 ; if(L <= m) Update(L,R,x,Lson); if(R > m) Update(L,R,x,Rson); PushUp(rt); } void Change(int L,int R,int x,int l,int r,int rt){ if(l >= L && r <= R){ if(tree[rt].v != -1){ if(tree[rt].v > x){ tree[rt].add = tree[rt].v = Gcd(tree[rt].v,x); } return ; } } PushDown(rt); int m = (l+r) >> 1; if(L <= m) Change(L,R,x,Lson); if(R > m) Change(L,R,x,Rson); PushUp(rt); } void Dfs(int l,int r,int rt) { if(l == r){ printf("%d ",tree[rt].v); return ; } PushDown(rt); int m = (l + r)>>1; Dfs(Lson); Dfs(Rson); } int main(){ int t; while(~scanf("%d",&t)){ while(t--){ int n,q; scanf("%d",&n); build(1,n,1); scanf("%d",&q); while(q--){ int a,l,r,x; scanf("%d%d%d%d",&a,&l,&r,&x); if(a&1) Update(l,r,x,1,n,1); else Change(l,r,x,1,n,1); } Dfs(1,n,1); printf("\n"); } } return 0; }