企业网站美工设计,同城网,做网站 钱,济南网站建设 首选搜点网络题意: 两个操作, 单点修改 询问一段区间是否能在至多一次修改后,使得区间$GCD$等于$X$ 题解: 正确思路; 线段树维护区间$GCD$,查询$GCD$的时候记录一共访问了多少个$GCD$不被X整除的区间即可,大于一个就NO 要注意的是,如果真的数完一整个区间,肯定会超时,因此用一个外部变量存储…题意: 两个操作, 单点修改 询问一段区间是否能在至多一次修改后,使得区间$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 iia;iib;ii)
using namespace std;
int casn,n,m,k;
class segtree{
#define nd node[now]
#define ndl node[now1]
#define ndr node[now1|1]public:struct segnode {int l,r;ll gcd,mn;int mid(){return (rl)1;}int len(){return r-l1;}void update(int x){mngcdx;}};vectorsegnode node;int cnt;segtree(int n) {node.resize(n2|3);maketree(1,n);}void pushup(int now){nd.gcd__gcd(ndl.gcd,ndr.gcd);nd.mnmin(ndl.mn,ndr.mn);}void pushdown(int now){}void maketree(int s,int t,int now1){nd{s,t,0,0};if(st){ll x;cinx;nd.update(x);return ;}maketree(s,nd.mid(),now1);maketree(nd.mid()1,t,now1|1);pushup(now);}void update(int pos,ll x,int now1){if(posnd.r||posnd.l) return ;if(nd.len()1){nd.update(x);return ;}pushdown(now);update(pos,x,now1); update(pos,x,now1|1);pushup(now);}int query(int s,int t,ll x){cnt0;count(s,t,x);return cnt1;}void count(int s,int t,ll x,int now1){if(cnt1||snd.r||tnd.l||nd.gcd%x0) return ;if(nd.len()1) {cnt; return ;}count(s,t,x,now1);count(s,t,x,now1|1);}
};int main() {IO;cinn;segtree tree(n);cinm;while(m--){ll a,b,c,d;cina;if(a1) {cinbcd;if(tree.query(b,c,d)) coutYESendl;else coutNOendl;}else {cinbc;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 pairint,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 iia;iib;ii)
#define per(ii,a,b) for(int iib;iia;--ii)
#define forn(ii,x) for(int iihead[x];ii;iie[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#xxendl
#define show2(x,y) cout#xx #yyendl
#define show3(x,y,z) cout#xx #yy #zzendl
#define show4(w,x,y,z) cout#ww #xx #yy #zzendl
#define show5(v,w,x,y,z) cout#v v #ww #xx #yy #zzendl
#define showa(a,b) cout#a[b]a[b]endl
using namespace std;
const int maxn1e610,maxm2e610;
const ll INF0x3f3f3f3f3f3f;
const int mod1e97;
const double PIacos(-1.0);
//head
int casn,n,m,k;
int num[maxn];
class segtree{
#define nd node[now]
#define ndl node[now1]
#define ndr node[now1|1]public:struct segnode {int l,r;ll gcd,mn;int mid(){return (rl)1;}int len(){return r-l1;}void update(int x){mngcdx;}};vectorsegnode node;segtree(int n) {node.resize(n2|3);maketree(1,n);}void pushup(int now){nd.gcd__gcd(ndl.gcd,ndr.gcd);nd.mnmin(ndl.mn,ndr.mn);}void pushdown(int now){}void maketree(int s,int t,int now1){nd{s,t,0,0};if(st){ll x;cinx;nd.update(x);return ;}maketree(s,nd.mid(),now1);maketree(nd.mid()1,t,now1|1);pushup(now);}void update(int pos,ll x,int now1){if(posnd.r||posnd.l) return ;if(nd.len()1){nd.update(x);return ;}pushdown(now);update(pos,x,now1); update(pos,x,now1|1);pushup(now);}ll query_minid(int s,int t,int now1){if(nd.len()1) return s;if(ndl.mnndr.mn) return query_minid(s,t,now1);else return query_minid(s,t,now1|1);}ll query_min(int s,int t,int now1){if(snd.r||tnd.l) return INF;if(snd.lnd.rt) return nd.mn;return min(query_min(s,t,now1),query_min(s,t,now1|1));}ll query_gcd(int s,int t,int now1){if(snd.r||tnd.l) return 0;if(snd.ltnd.r)return nd.gcd;return __gcd(query_gcd(s,t,now1),query_gcd(s,t,now1|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;cinn;segtree tree(n);cinm;while(m--){ll a,b,c,d;cina;if(a1) {cinbcd;int idtree.query_minid(b,c);ll mntree.query_min(b,c);tree.update(id,d);if(tree.query_gcd(b,c)d)coutYESendl;else coutNOendl;tree.update(id,mn);}else {cinbc;tree.update(b,c);}}return 0;
}转载于:https://www.cnblogs.com/nervendnig/p/10227074.html
