题意:
两个操作,
单点修改
询问一段区间是否能在至多一次修改后,使得区间$GCD$等于$X$
题解:
正确思路;
线段树维护区间$GCD$,查询$GCD$的时候记录一共访问了多少个$GCD$不被X整除的区间即可,大于一个就NO
要注意的是,如果真的数完一整个区间,肯定会超时,因此用一个外部变量存储数量,一旦超过一个,就停止整个查询
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
int casn,n,m,k;
class segtree{
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
public:
struct segnode {
int l,r;ll gcd,mn;
int mid(){return (r+l)>>1;}
int len(){return r-l+1;}
void update(int x){mn=gcd=x;}
};
vector<segnode> node;
int cnt;
segtree(int n) {node.resize(n<<2|3);maketree(1,n);}
void pushup(int now){
nd.gcd=__gcd(ndl.gcd,ndr.gcd);
nd.mn=min(ndl.mn,ndr.mn);
}
void pushdown(int now){}
void maketree(int s,int t,int now=1){
nd={s,t,0,0};
if(s==t){
ll x;cin>>x;nd.update(x);
return ;
}
maketree(s,nd.mid(),now<<1);
maketree(nd.mid()+1,t,now<<1|1);
pushup(now);
}
void update(int pos,ll x,int now=1){
if(pos>nd.r||pos<nd.l) return ;
if(nd.len()==1){nd.update(x);return ;}
pushdown(now);
update(pos,x,now<<1); update(pos,x,now<<1|1);
pushup(now);
}
int query(int s,int t,ll x){cnt=0;count(s,t,x);return cnt<=1;}
void count(int s,int t,ll x,int now=1){
if(cnt>1||s>nd.r||t<nd.l||nd.gcd%x==0) return ;
if(nd.len()==1) {cnt++; return ;}
count(s,t,x,now<<1);count(s,t,x,now<<1|1);
}
}; int main() {
IO;
cin>>n;
segtree tree(n);
cin>>m;
while(m--){
ll a,b,c,d;
cin>>a;
if(a==1) {
cin>>b>>c>>d;
if(tree.query(b,c,d)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}else {
cin>>b>>c;
tree.update(b,c);
}
}
return 0;
}
错误思路(会WA8):
如果要修改一次使得$GCD$等于$X$,肯定是修改区间的最小值,线段树维护即可
错误原因在于,$GCD$大于$X$的时候,最小值可能是$X$的倍数,此时不应该修改最小值
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
#define forn(ii,x) for(int ii=head[x];ii;ii=e[ii].next)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define inline inline __attribute__( \
(always_inline, __gnu_inline__, __artificial__)) \
__attribute__((optimize("Ofast"))) __attribute__((target("sse"))) \
__attribute__((target("sse2"))) __attribute__((target("mmx")))
#define show(x) cout<<#x<<"="<<x<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show5(v,w,x,y,z) cout<<#v<<" "<<v<<" "<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl
using namespace std;
const int maxn=1e6+10,maxm=2e6+10;
const ll INF=0x3f3f3f3f3f3f;
const int mod=1e9+7;
const double PI=acos(-1.0);
//head
int casn,n,m,k;
int num[maxn];
class segtree{
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
public:
struct segnode {
int l,r;ll gcd,mn;
int mid(){return (r+l)>>1;}
int len(){return r-l+1;}
void update(int x){mn=gcd=x;}
};
vector<segnode> node;
segtree(int n) {node.resize(n<<2|3);maketree(1,n);}
void pushup(int now){
nd.gcd=__gcd(ndl.gcd,ndr.gcd);
nd.mn=min(ndl.mn,ndr.mn);
}
void pushdown(int now){}
void maketree(int s,int t,int now=1){
nd={s,t,0,0};
if(s==t){
ll x;cin>>x;nd.update(x);
return ;
}
maketree(s,nd.mid(),now<<1);
maketree(nd.mid()+1,t,now<<1|1);
pushup(now);
}
void update(int pos,ll x,int now=1){
if(pos>nd.r||pos<nd.l) return ;
if(nd.len()==1){nd.update(x);return ;}
pushdown(now);
update(pos,x,now<<1); update(pos,x,now<<1|1);
pushup(now);
}
ll query_minid(int s,int t,int now=1){
if(nd.len()==1) return s;
if(ndl.mn<=ndr.mn) return query_minid(s,t,now<<1);
else return query_minid(s,t,now<<1|1);
}
ll query_min(int s,int t,int now=1){
if(s>nd.r||t<nd.l) return INF;
if(s<=nd.l&&nd.r<=t) return nd.mn;
return min(query_min(s,t,now<<1),query_min(s,t,now<<1|1));
}
ll query_gcd(int s,int t,int now=1){
if(s>nd.r||t<nd.l) return 0;
if(s<=nd.l&&t>=nd.r)return nd.gcd;
return __gcd(query_gcd(s,t,now<<1),query_gcd(s,t,now<<1|1));
}
}; int main() {
//#define test
#ifdef test
auto _start = chrono::high_resolution_clock::now();
freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
// IO;
cin>>n;
segtree tree(n);
cin>>m;
while(m--){
ll a,b,c,d;
cin>>a;
if(a==1) {
cin>>b>>c>>d;
int id=tree.query_minid(b,c);
ll mn=tree.query_min(b,c);
tree.update(id,d);
if(tree.query_gcd(b,c)==d)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
tree.update(id,mn);
}else {
cin>>b>>c;
tree.update(b,c);
}
}
return 0;
}