LOJ 576 - "libreoj noi round 2" sign in game [line segment tree]

On the subject

Topic link :https://loj.ac/p/576

---

The main idea of the topic

Give a length of $n$ Sequence $a$, There is also an unknown sequence $b$, You can spend ${\gcd }_{i=l}^r{a}_i$ At the cost of ${\sum }_{i=l}^r{b}_i$ Value .

Each modification $a$ One of the numbers , Get $b$ The minimum weight required for all numbers in .

$1\le n,q\le 10^5,1\le a_i\le 10^9$

---

Their thinking

Because there is an information problem , The result of limited information must not exceed the amount of information . So we need to know $n$ A number, then we need to ask at least $n$ Time .

Then consider $s_i={\sum }_{j=1}^i{b}_j$, Then every time we get a $s_r-s_{l-1}$, We can pass a $[l,r]$ and $[l^{\prime },r]$ I got $[l,l^{\prime }-1]$（ The opposite is true ）. That is, some endpoints are connected and cover each other. We can convert them into intervals with the same endpoints but no mutual coverage .

Then our goal is that all endpoints must be inside , Add the limitation of interconnection , It looks like the minimum spanning tree . Equivalent to a little $[0,n]$, We connect $l,r$ The price is ${\gcd }_{i=l+1}^r{a}_i$, Find the minimum spanning tree .

Then obviously we must find one $k$, then $0\sim k$ towards $n$ Even the edge ,$k+1\sim n$ towards $0$ Even the edge , Mainly to find this $k$, This $k$ Is the first satisfaction ${\gcd }_{i=1}^k{a}_i\le {\gcd }_{i=k}^n{a}_i$ The location of .

Then because of the prefix $gcd$ Most changes $\log$ Time , We can consider finding these positions .

Consider bisecting these positions on the segment tree , Seems to be ${\log }^3$ Of , In fact, suppose $L\sim mid$ There is no answer in , At this time, the prefix $gcd$ Still equal to $val$, So don't worry about the things in front , When reaching a position, judge whether the value of this interval is $val$ Just a multiple of .

Time complexity ：$O(n{\log }^{2}n)$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;
const ll N=1e5+10;
ll n,q,a[N],w[N<<2];
vector<pair<ll,ll> > pre,suf;
void Change(ll x,ll L,ll R,ll pos,ll val){
    
	if(L==R){
    w[x]=val;return;}
	ll mid=(L+R)>>1;
	if(pos<=mid)Change(x*2,L,mid,pos,val);
	else Change(x*2+1,mid+1,R,pos,val);
	w[x]=__gcd(w[x*2],w[x*2+1]);return;
}
ll AskP(ll x,ll L,ll R,ll pos,ll &val){
    
	if(w[x]%val==0)return n;
	if(L==R){
    val=__gcd(val,w[x]);return L;}
	ll mid=(L+R)>>1;
	if(pos>mid)return AskP(x*2+1,mid+1,R,pos,val);
	ll k=AskP(x*2,L,mid,pos,val);
	if(k==n)return AskP(x*2+1,mid+1,R,pos,val);
	return k;
}
ll AskS(ll x,ll L,ll R,ll pos,ll &val){
    
	if(w[x]%val==0)return 0;
	if(L==R){
    val=__gcd(val,w[x]);return L;}
	ll mid=(L+R)>>1;
	if(pos<=mid)return AskS(x*2,L,mid,pos,val);
	ll k=AskS(x*2+1,mid+1,R,pos,val);
	if(!k)return AskS(x*2,L,mid,pos,val);
	return k;
}
ll Ask(ll x,ll L,ll R,ll l,ll r){
    
	if(L==l&&R==r)return w[x];
	int mid=(L+R)>>1;
	if(r<=mid)return Ask(x*2,L,mid,l,r);
	if(l>mid)return Ask(x*2+1,mid+1,R,l,r);
	return __gcd(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r));
} 
signed main()
{
    
// freopen("game3_12.in","r",stdin);
	scanf("%lld%lld",&n,&q);ll d=0;n++;
	for(ll i=1;i<n;i++)
		scanf("%lld",&a[i]),Change(1,0,n,i,a[i]);
	Change(1,0,n,0,1);Change(1,0,n,n,1);
	while(q--){
    
		ll p,x;pre.clear();suf.clear();
		scanf("%lld%lld",&p,&x);
		Change(1,0,n,p,x);a[p]=x;
		ll val=a[1];x=1;
		while(x<n){
    
			pre.push_back(mp(x,val));
			x=AskP(1,0,n,x+1,val);
		}
		x=n-1;val=a[n-1];
		while(x){
    
			suf.push_back(mp(x-1,val));
			x=AskS(1,0,n,x-1,val);
		}
		ll p1=pre.size()-1,p2=suf.size()-1;
		ll L=-1,R=n,ans=0;
		while(1){
    
			if(p2<0||pre[p1].second<suf[p2].second){
    
				if(pre[p1].first<=L){
    
					ans+=pre[p1].second*(R-L-1);
					break;
				}
				ans+=pre[p1].second*(R-pre[p1].first);
				R=pre[p1].first;p1--;
			}
			else{
    
				if(suf[p2].first>=R){
    
					ans+=suf[p2].second*(R-L-1);
					break;
				}
				ans+=suf[p2].second*(suf[p2].first-L);
				L=suf[p2].first;p2--;
			}
		}
		printf("%lld\n",ans-Ask(1,0,n,1,n-1));
	}
	return 0;
}
//2 6 3