Loj#576-「LibreOJ NOI Round #2」签到游戏【线段树】

题目链接:https://loj.ac/p/576

给出一个长度为 n n n的序列 a a a，还有一个未知序列 b b b，你每次可以花费 gcd ⁡ i = l r a i gcd_{i=l}^r a_i gcdi=lr​ai​的代价得到 ∑ i = l r b i sum_{i=l}^rb_i ∑i=lr​bi​的值。

每次修改 a a a中的一个数，求得到 b b b中所有数字需要花费的最小权值。

1 ≤ n , q ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 9 1leq n,qleq 10^5,1leq a_ileq 10^9 1≤n,q≤105,1≤ai​≤109

因为有一个信息上的问题，有限的信息对应的结果肯定不能超过信息的数量。所以我们需要知道 n n n个数字那么我们就至少需要询问 n n n次。

然后考虑 s i = ∑ j = 1 i b j s_i=sum_{j=1}^i b_j si​=∑j=1i​bj​，那么我们每次得到的将是一个 s r − s l − 1 s_r-s_{l-1} sr​−sl−1​，我们可以通过一个 [ l , r ] [l,r] [l,r]和 [ l ′ , r ] [l',r] [l′,r]的询问得到 [ l , l ′ − 1 ] [l,l'-1] [l,l′−1]（反过来同理）。也就是一些端点相互连接相互覆盖的区间我们可以把它们转换为端点相同但是没有相互覆盖的区间。

然后我们目标是所有端点都得在里面，加上相互连接这个限制，看上去就很像最小生成树。相当于有点 [ 0 , n ] [0,n] [0,n]，我们连接 l , r l,r l,r的代价是 gcd ⁡ i = l + 1 r a i gcd_{i=l+1}^ra_i gcdi=l+1r​ai​，求最小生成树。

然后显然的我们肯定是找一个 k k k，然后 0 ∼ k 0sim k 0∼k向 n n n连边， k + 1 ∼ n k+1sim n k+1∼n向 0 0 0连边，主要是找到这个 k k k，这个 k k k就是第一个满足 gcd ⁡ i = 1 k a i ≤ gcd ⁡ i = k n a i gcd_{i=1}^k a_ileq gcd_{i=k}^n a_i gcdi=1k​ai​≤gcdi=kn​ai​的位置。

然后因为前后缀 g c d gcd gcd都最多变化 log ⁡ log log次，我们可以考虑求出这些位置。

考虑在线段树上二分出这些位置，看上去是 log ⁡ 3 log^3 log3的，实际上假设 L ∼ m i d Lsim mid L∼mid中没有答案，那么此时这个前缀的 g c d gcd gcd依旧等于 v a l val val，所以不需要管前面的东西，到一个位置的时候判这个区间的值是不是 v a l val val的倍数就好了。

时间复杂度： O ( n log ⁡ 2 n ) O(nlog^2 n) O(nlog2n)

#include
#include
#include
#include
#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 > 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
		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
			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
				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("%lldn",ans-Ask(1,0,n,1,n-1));
	}
	return 0;
}
//2 6 3