題意:
兩個操作,
單點修改
詢問一段區間是否能在至多一次修改后,使得區間$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 testauto _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;
}
?
)
詳解)