Cfdiv1+2-bash and a high math puzzle- (gcd+ summary of segment tree single point interval maintenance)

Xiaoyang's shell
Bash and a Tough Math Puzzle

The question ：
There is one n Array of , Then there is m operations , There are two kinds of , One is to let va[a] = b, One is to ask you l To r Of this section gcd Is it close to x. near x Is defined as , Or equal to x, Or you can change a number in this range and then equal x.

reflection ：
1. See this question , First of all gcd The nature of ,gcd(a1,a2,a3) = gcd(a1,a2-1,a3-a2). That is, the difference of this interval gcd. But this topic is not used , Because you change one number at a time , That is, single point modification , Just maintain it directly gcd That's it . As long as there are various topics with interval mergence , For example, the best value , The sum of the , Section GCD. If there is a single point of modification , Then you can directly segment the tree . If the interval is modified , Generally, we need to look at the nature of this maintenance thing .
2. Then it is whether to approach x, At most, you can change one number . This is similar to the segment tree maintenance I did before hash Dichotomy determines whether two strings are similar Scientific fantasy . You can delete one , Then you can get two different places , Then you can modify , The rest of the left and right ends must meet the meaning of the question .
3. I found it timed out after writing . Because the complexity is m*log(n)*log(n).2e8 Well , But it timed out . So we need to change the judgment method . At this time, I thought of the problem I had done before ： Zhejiang Province competition -Bin Packing Problem. This problem needs to find a leftmost place to fit x The point of , If you also find two points , Also timeout . Then look directly in the tree , about l To r, See if the maximum value of the left subtree >=x, If you can go left and right , If you can't go to the right . Until you find the leaf node , hold x Just install it . If you don't find it in the end , Then open a new box .
4. So this question can also be like this , Search the tree directly , The complexity is log(n) Of , Because you can throw away half every time , Only go to the illegal half . This question , If the left interval gcd No x Multiple , Just go to the left , If the right side is not the right side . If both sides are not, then it is directly illegal , Because you can change one number at most , In this way, there are two illegal . Of course, this interval is within the range of the query , But both are legal , Just stop searching . Just two different ways of writing . One is ： Just described , Take whichever side is illegal , If both sides are illegal, it is illegal to exit directly . One is ： Just look at how many illegal numbers there are , Add up , Search around every time , But in this way, both sides will search , But you write that if this section is legal return 0 Can , So you won't search .
5. At first, I thought that at most one point was not equal to x, And then the rest gcd==x. actually , It should be to see whether it is x Multiple , because 6 6 12 It's also close 3 Of , Because I changed one of them into 3, The remaining interval gcd All are 3 The multiple of is also ok . Of course, when you ask ,gcd It could be a negative number , Just take the absolute value . But the positive and negative do not affect whether the module is taken =0 What happened .

Code ：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define node_l node<<1
#define node_r node<<1|1

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 5e5+20,M = 2010;

int T,n,m,k;
int va[N];
int maxn = 0;

int gcd(int a,int b)
{
    
	if(!b) return a;
	return gcd(b,a%b);
}

struct seg_gcd
{
    
	struct node{
    
		int L,R;
		int ans;
	}t[4*N];
	void pushup(int node)
	{
    
		t[node].ans = gcd(t[node_l].ans,t[node_r].ans);	
	}
	void build(int node,int l,int r)
	{
    
		t[node].L = l,t[node].R = r;
		if(l==r)
		{
    
			t[node].ans = va[l];
			return ;
		}
		int mid = (l+r)>>1;
		build(node_l,l,mid);build(node_r,mid+1,r);
		pushup(node);
	}
	void update(int node,int x,int value)
	{
    
		if(t[node].L==x&&t[node].R==x)
		{
    
			t[node].ans = value;
			return ;
		}
		int mid = (t[node].L+t[node].R)>>1;
		if(x<=mid) update(node_l,x,value);
		else update(node_r,x,value);
		pushup(node);
	}
	int query(int node,int l,int r)
	{
    
		if(t[node].L>=l&&t[node].R<=r) return t[node].ans;
		int mid = (t[node].L+t[node].R)>>1;
		if(r<=mid) return query(node_l,l,r);
		else if(l>mid) return query(node_r,l,r);
		else return gcd(query(node_l,l,mid),query(node_r,mid+1,r));
	}
	int check(int node,int l,int r,int c)
	{
    
		if(maxn>=2) return maxn; // If it is illegal at this time , Just directly return 2
		if(t[node].L>=l&&t[node].R<=r&&t[node].ans%c==0) return 0; // If there is no need to search this section , It will save a lot of time here , Because if you can , It is illegal to have only half of the interval each time .
		if(t[node].L==t[node].R) return (t[node].ans%c!=0); // If this point is illegal, it needs to be operated once 
		int mid = (t[node].L+t[node].R)>>1;
		if(r<=mid) return maxn = check(node_l,l,r,c);
		else if(l>mid) return maxn = check(node_r,l,r,c);
		else return maxn = check(node_l,l,mid,c)+check(node_r,mid+1,r,c);
	}
}t_gcd;

signed main()
{
    
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i];
	t_gcd.build(1,1,n);
	cin>>m;
	while(m--)
	{
    
		int op,a,b,c;
		cin>>op;
		if(op==1)
		{
    
			cin>>a>>b>>c;
			maxn = 0;
			if(t_gcd.check(1,a,b,c)<=1) cout<<"YES\n";
			else cout<<"NO\n";
		}
		else
		{
    
			cin>>a>>b;
			t_gcd.update(1,a,b);
		}
	}
	return 0;
}
/*  The writing method of two minute timeout  bool check(int l,int r,int c) { int anw = t_gcd.query(1,l,r); return anw%c==0; } if(op==1) { cin>>a>>b>>c; int l = a,r = b; while(l<r) { int mid = (l+r+1)>>1; if(check(a,mid,c)) l = mid; else r = mid-1; } int mid = 0; if(check(a,l,c)) mid = l+2; else mid = l+1; if(mid>b||check(mid,b,c)) cout<<"YES\n"; else cout<<"NO\n"; } /* 

interval GCD

The question ：
Is to give you a n Array of , There are two operations , One is to add the numbers of a range D, One is to query this interval gcd.

reflection ：
1. This question is obviously different from the previous one , Here is interval modification , So you can't maintain it directly . however gcd There is a property , Namely gcd(a1,a2,a3)=gcd(a1,a2-a1,a3-a2) That is, some numbers gcd It's their difference gcd. But what can this do ？
2. If we maintain the difference of this array in the segment tree , Then interval modification corresponds to single point modification for difference , Is to modify l and r+1 These two points . But you maintain the difference , Although the interval modification has been changed into a single point modification , But how can you ask gcd Well ？
3. That formula is used here , Maintain differential gcd. But I can only find out 1 To n Of this interval gcd ah , If o l and r Of this section gcd Well ？ direct query(l,r) It's not l To r Of gcd, Because of you l The value of the point is va[l]-va[l-1], It should be va[l]-0. So every time you need to know va[l] What is the value of , then gcd(va[l],query(l+1,r)) This is the real l To r Of gcd.
4. So we maintain differential , So if we maintain another interval sum for the difference , If the query query_sum(1,l) Value , Is this value true va[l], Because the prefix sum of the difference is the original value . In fact, we found that , Maintain the interval sum for the difference group , But we actually only ask 1 To i Value , That is, prefix and . Therefore, this prefix and can also be maintained with a tree array . Every modification is also a modification l and r+1 That's all right. . But it is more convenient to write only one segment tree , So here we use segment tree to maintain .
5. Here you can maintain the interval modification gcd 了 . But every query interval gcd The complexity of log(n)*log(n).