Bash and a Tough Math Puzzle(CodeForces-11D)(线段树)

题目

传送门

CF
Vjudge

题目

Bash likes playing with arrays. He has an array $a_1$,?$a_2$,?… an of n integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is almost correct.

Suppose he guesses that the gcd of the elements in the range $[l,?r]$ of a is x. He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is x after making the change. Note that when he guesses, he doesn’t actually change the array — he just wonders if the gcd of the segment can be made x. Apart from this, he also sometimes makes changes to the array itself.

Since he can’t figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process q queries of one of the following forms:

$1?l?r?x$ — Bash guesses that the gcd of the range $[l,?r]$ is x. Report if this guess is almost correct.
$2?i?y$ — Bash sets ai to y.
Note: The array is 1-indexed.

Input
The first line contains an integer n $(1?\le ?n?\le ?5?10^5)$ — the size of the array.

The second line contains n integers $a_1,?a_2,?...,?a_n$ $(1?\le ?a_i?\le ?10^9)$ — the elements of the array.

The third line contains an integer q $(1?\le ?q?\le ?4?10^5)$ — the number of queries.

The next q lines describe the queries and may have one of the following forms:

$1?l?r?x(1?\le ?l?\le ?r?\le ?n,?1?\le ?x?\le ?10^9).$
$2?i?y(1?\le ?i?\le ?n,?1?\le ?y?\le ?10^9).$
Guaranteed, that there is at least one query of first type.

Output
For each query of first type, output “YES” (without quotes) if Bash’s guess is almost correct and “NO” (without quotes) otherwise.

Examples
Input

3 2 6 3 4 1 1 2 2 1 1 3 3 2 1 9 1 1 3 2 

Output

YES YES NO 

Input

5 1 2 3 4 5 6 1 1 4 2 2 3 6 1 1 4 2 1 1 5 2 2 5 10 1 1 5 2 

Output

NO YES NO YES 

Note
In the first sample, the array initially is {2,?6,?3}.

For query 1, the first two numbers already have their gcd as 2.

For query 2, we can achieve a gcd of 3 by changing the first element of the array to 3. Note that the changes made during queries of type 1 are temporary and do not get reflected in the array.

After query 3, the array is now {9,?6,?3}.

For query 4, no matter which element you change, you cannot get the gcd of the range to be 2.

题目大意

现在给你一个长度为$n$的序列$a$$(1?\le ?n?\le ?5?10^5)$接下来有q次操作$(1?\le ?q?\le ?4?10^5)$分为两种:
1 l r x:查询区间$[l,r]$是否能通过不改变或只临时改变其中一个元素的值使得
$gcd(a[i])=x(i\in [l,r])$输出"YES"或“NO”
2 i y:将a[i]值改为y

思路

这是一道很裸的线段树的题.我们对于一个区间[L,R]只需要记录一下该区间所有元素的最大公因数为多少
我们令Gcd[l,r]为该区间所有元素最大公因数,显然有:
$Gcd[l,r]=gcd(Gcd[l,mid],Gcd[mid+1,r])$
那么对于操作2,我们直接下传值返回更新
对于操作1,我们知道如果Gcd[L,R]为x的倍数的话,我们可以直接令其中任意一个数为x就可以满足条件
我们令cnt筛除不符合条件的元素的变量
如果不满足,由于最多只可修改一次,那么我们把查询区间分成若干个子区间,如果有区间Gcd[l,r]%x!=0那么我们只允许出现一个元素不符合条件
如果该区间的左右子区间(有点绕)Gcd均不符,那么不符合的元素肯定大于1个,就直接返回,而如果到了叶节点,就直接cnt++,而如果只有一个儿子Gcd不符,递归处理即可

代码

常规版

//343ms 23500kB #include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<climits> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; int read(){
     int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){
     if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){
     x=x*10+s-'0';s=getchar();}return x*f; } #define lch i<<1 #define rch i<<1|1 #define MAXN 500000 #define INF 0x3f3f3f3f #define Mod int(1e9+7) struct Tree{
     int l,r,gcd;Tree(){
     }Tree(int L,int R,int G){
     l=L,r=R,gcd=G;} }tree[MAXN<<2]; inline int gcd(int a,int b){
     return !b?a:gcd(b,a%b);} void Build(int i,int l,int r){
     tree[i].l=l,tree[i].r=r;if(l==r){
     tree[i].gcd=read();return ;}int mid=(l+r)>>1;Build(lch,l,mid);Build(rch,mid+1,r);tree[i].gcd=gcd(tree[lch].gcd,tree[rch].gcd);return ; } void Update(int i,int p,int x){
     if(tree[i].l==p&&tree[i].r==p){
     tree[i].gcd=x;return ;}int mid=(tree[i].l+tree[i].r)>>1;if(p<=mid) Update(lch,p,x);else Update(rch,p,x);tree[i].gcd=gcd(tree[lch].gcd,tree[rch].gcd);return ; } int cnt; void Query(int i,int L,int R,int x){
     if(cnt>1) return ;if(L<=tree[i].l&&tree[i].r<=R){
     if(tree[i].gcd%x==0)return ;else if(tree[i].l==tree[i].r){
     cnt++;return ;}int lg=tree[lch].gcd,rg=tree[rch].gcd;if(lg%x&&rg%x){
     cnt=2;return ;}if(lg%x)Query(lch,L,R,x);if(rg%x)Query(rch,L,R,x);return ;}int mid=(tree[i].l+tree[i].r)>>1;if(L<=mid) Query(lch,L,R,x);if(mid+1<=R) Query(rch,L,R,x);return ; } int main(){
     int n=read();Build(1,1,n);int q=read();for(int i=1;i<=q;i++){
     int o=read(),l,r,p,x;if(o-1) p=read(),x=read(),Update(1,p,x);else l=read(),r=read(),x=read(),cnt=0,Query(1,l,r,x),puts(cnt>1?"NO":"YES");}return 0; } 

懒人加速版

//296 ms7800 KB #include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<climits> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; int read(){
     int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){
     if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){
     x=x*10+s-'0';s=getchar();}return x*f; } #define lch i<<1 #define rch i<<1|1 #define MAXN 500000 #define INF 0x3f3f3f3f #define Mod int(1e9+7) int Gcd[MAXN<<2]; inline int gcd(int a,int b){
     return !b?a:gcd(b,a%b);} void Build(int i,int l,int r){
     if(l==r){
     Gcd[i]=read();return ;}int mid=(l+r)>>1;Build(lch,l,mid);Build(rch,mid+1,r);Gcd[i]=gcd(Gcd[lch],Gcd[rch]);//向上更新return ; } void Update(int i,int l,int r,int p,int x){
     if(l==p&&r==p){
     Gcd[i]=x;return ;}int mid=(l+r)>>1;if(p<=mid) Update(lch,l,mid,p,x);else Update(rch,mid+1,r,p,x);Gcd[i]=gcd(Gcd[lch],Gcd[rch]);return ; } int cnt; void Query(int i,int l,int r,int L,int R,int x){
     if(cnt>1) return ;//不符合直接返回int mid=(l+r)>>1;if(L<=l&&r<=R){
     //该区间为查询区间子区间if(Gcd[i]%x==0)//子区间符合条件return ;else if(l==r){
     //为叶节点cnt++;return ;}//子区间Gcd%x!=0,cnt必定会改变int lg=Gcd[lch],rg=Gcd[rch];if((lg%x&&rg%x)||cnt){
     //两区间不符条件或cnt已有值cnt=2;return ;}//此时只有一个子区间不满足条件if(lg%x) Query(lch,l,mid,L,R,x);//递归处理if(rg%x) Query(rch,mid+1,r,L,R,x);return ;}if(L<=mid) Query(lch,l,mid,L,R,x);//找子区间if(mid+1<=R) Query(rch,mid+1,r,L,R,x);return ; } int main(){
     int n=read();Build(1,1,n);int q=read();for(int i=1;i<=q;i++){
     int o=read(),l,r,p,x;if(o-1) p=read(),x=read(),Update(1,1,n,p,x);else l=read(),r=read(),x=read(),cnt=0,Query(1,1,n,l,r,x),puts(cnt>1?"NO":"YES");}return 0; }