对于操作 \(1\),关键是如何查找 \([l,r]\) 中不能整除 \(x\) 的个数。
可以想到用线段树暴力优化求解:
用线段树维护区间 \(\gcd\),如果一段区间的 \(\gcd\) 都能整除 \(x\),那么这段区间的所有数也都能整除 \(x\),那么我们可以利用这个特点,节省大部分递归时间。
每次查询,用 \(cnt\) 表示区间中不能整除 \(x\) 的个数。
YES
。YES
。NO
。查询时还需要一点小剪枝,即查询过程中只要 \(cnt>1\) 时,立即停止查询,输出 NO
。
操作 \(2\) 为线段树最基本的单点修改。
/* 查询 */ void check(node *now, ll l, ll r, ll k) { if (l <= now->L && now->R <= r + 1 && now->gcd % k == 0) return; //优化线段树的查询过程 if (l <= now->L && now->R <= r + 1 && now->L + 1 == now->R){ if (now->gcd % k != 0){ cnt++; if (cnt >= 2) return; //剪枝 } return; } ll mid = (now->L + now->R) >> 1; if (l < mid) check(now->lc, l, r, k); if (r >= mid) check(now->rc, l, r, k); } /* 单点修改 + 维护gcd */ void add(node *now,ll x,ll k) { if(now->L + 1 == now->R) now->gcd = k; //修改 else { ll mid=(now->L + now->R)>>1; if(x<mid) add(now->lc,x,k); if(x>=mid) add(now->rc,x,k); now->gcd = gcd(now->lc->gcd,now->rc->gcd); //维护gcd } } /* 主函数 */ int main() { n=read(); node *root; root=new node; build(root,1,n+1); for(int i=1;i<=n;++i){ ll x=read(); add(root,i,x); } m=read(); for(int i=1;i<=m;++i){ ll opt=read(); if(opt==1){ ll l=read(),r=read(),k=read(); cnt=0; //勿忘初始化 check(root,l,r,k); if(cnt>1) puts("NO"); else puts("YES"); } else{ ll x=read(),k=read(); add(root,x,k); } } return 0; }
本题是关于线段树暴力优化的问题,还有两道题与这道题思想类似:
CF438D The Child and Sequence;
P4145 上帝造题的七分钟2 / 花神游历各国。