【XSY4041】搬磚（線段樹）

題面

搬磚

題解

題意為求最大的 p p p 使得 h 1 ≡ h 2 ≡ ⋯ ≡ h n ( m o d p ) h_1\equiv h_2\equiv \cdots\equiv h_n\pmod p h1​≡h2​≡⋯≡hn​(modp)。

即 h 2 − h 1 ≡ h 3 − h 2 ≡ ⋯ ≡ h n − h n − 1 ≡ 0 ( m o d p ) h_2-h_1\equiv h_3-h_2\equiv \cdots\equiv h_n-h_{n-1}\equiv 0\pmod p h2​−h1​≡h3​−h2​≡⋯≡hn​−hn−1​≡0(modp)。

那麼我們可以得到 p ∣ gcd ⁡ ( h 2 − h 1 , h 3 − h 2 , ⋯   , h n − h n − 1 ) p|\gcd(h_2-h_1,h_3-h_2,\cdots,h_n-h_{n-1}) p∣gcd(h2​−h1​,h3​−h2​,⋯,hn​−hn−1​)。

令 c i = h i + 1 − h i c_i=h_{i+1}-h_i ci​=hi+1​−hi​，那麼最大的 p p p 就是 gcd ⁡ ( c 1 , c 2 , ⋯   , c n − 1 ) \gcd(c_1,c_2,\cdots,c_{n-1}) gcd(c1​,c2​,⋯,cn−1​)。

那麼我們要做的就是動态維護差分下的全局 gcd ⁡ \gcd gcd。

考慮修改操作，對于操作一 L , R , a , b , c L,R,a,b,c L,R,a,b,c 來說：（其中 x ∈ [ L , R ) x\in [L,R) x∈[L,R)，注意 c x c_x cx​ 和 c c c 的區分）

c x = h x + 1 − h x = [ a ( x + 1 ) 2 + b ( x + 1 ) + c ] − [ a x 2 + b x + c ] = a ( 2 x + 1 ) + b = 2 a x + a + b \begin{aligned} c_x&=h_{x+1}-h_x=\left[a(x+1)^2+b(x+1)+c\right]-\left[ax^2+bx+c\right]\\ &=a(2x+1)+b=2ax+a+b \end{aligned} cx​​=hx+1​−hx​=[a(x+1)2+b(x+1)+c]−[ax2+bx+c]=a(2x+1)+b=2ax+a+b​

令 k = 2 a k=2a k=2a， m = a + b m=a+b m=a+b，由 gcd ⁡ ( a , b ) = gcd ⁡ ( a , b − a ) \gcd(a,b)=\gcd(a,b-a) gcd(a,b)=gcd(a,b−a) 可知對于任意的 L ≤ l < r < R L\leq l<r< R L≤l<r<R，有：

gcd ⁡ ( c l , c l + 1 , ⋯   , c r ) = gcd ⁡ ( k l + m , k ( l + 1 ) + m , ⋯   , k ( r − 2 ) + m , k ( r − 1 ) + m , k r + m ) = gcd ⁡ ( k l + m , k ( l + 1 ) + m , ⋯   , k ( r − 2 ) + m , k ( r − 1 ) + m , k ) = gcd ⁡ ( k l + m , k , k , ⋯   , k ) = gcd ⁡ ( k l + m , k ) = gcd ⁡ ( m , k ) \begin{aligned} \gcd(c_{l},c_{l+1},\cdots,c_{r})&=\gcd(kl+m,k(l+1)+m,\cdots,k(r-2)+m,k(r-1)+m,kr+m)\\ &=\gcd(kl+m,k(l+1)+m,\cdots,k(r-2)+m,k(r-1)+m,k)\\ &=\gcd(kl+m,k,k,\cdots,k)\\ &=\gcd(kl+m,k)\\ &=\gcd(m,k)\\ \end{aligned} gcd(cl​,cl+1​,⋯,cr​)​=gcd(kl+m,k(l+1)+m,⋯,k(r−2)+m,k(r−1)+m,kr+m)=gcd(kl+m,k(l+1)+m,⋯,k(r−2)+m,k(r−1)+m,k)=gcd(kl+m,k,k,⋯,k)=gcd(kl+m,k)=gcd(m,k)​

那麼我們用兩棵線段樹，一棵 T 1 T_1 T1​ 維護 h i h_i hi​，另一棵 T 2 T_2 T2​ 維護 gcd ⁡ ( c i ) \gcd(c_i) gcd(ci​)，然後操作一就相當于在 T 1 T_1 T1​ 上區間二次函數重置、在 T 2 T_2 T2​ 上區間重置和單點修改。

而操作二就是來蒙人的……注意到 a = b = 0 a=b=0 a=b=0，除了端點外 c i c_i ci​ 不變，那麼我們隻需要在 T 1 T_1 T1​ 上區間加、在 T 2 T_2 T2​ 上單點修改。

時間複雜度 O ( n log ⁡ n log ⁡ w ) O(n\log n\log w) O(nlognlogw)，其中 n , q n,q n,q 同階， w w w 為值域最大值。

#include<bits/stdc++.h>

#define N 200010
#define ll __int128

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

inline void write(ll x,char c)
{
	static int a[55];
	int cnt=0;
	while(x)
	{
		a[++cnt]=x%10;
		x/=10;
	}
	for(int i=cnt;i>=1;i--)
		putchar(a[i]+'0');
	putchar(c);
}

ll Abs(ll x)
{
	return x<0?-x:x;
}

ll gcd(ll a,ll b)
{
	if(!a||!b) return a+b;
	return b?gcd(b,a%b):a;
}

struct data
{
	int a,b,c;
	data(){};
	data(int aa,int bb,int cc){a=aa,b=bb,c=cc;}
};

int n,q,h[N];

namespace T1
{
	data lazy[N<<2];
	bool tag[N<<2];
	ll lazadd[N<<2];
	void downn(int k,data v)
	{
		lazy[k]=v;
		lazadd[k]=0;
		tag[k]=1;
	}
	void down(int k)
	{
		if(tag[k])
		{
			downn(k<<1,lazy[k]);
			downn(k<<1|1,lazy[k]);
			tag[k]=0;
		}
		if(lazadd[k])
		{
			lazadd[k<<1]+=lazadd[k];
			lazadd[k<<1|1]+=lazadd[k];
			lazadd[k]=0;
		}
	}
	void build(int k,int l,int r)
	{
		if(l==r)
		{
			h[l]=lazadd[k]=read();
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
	}
	void update(int k,int l,int r,int ql,int qr,data v)
	{
		if(ql<=l&&r<=qr)
		{
			downn(k,v);
			return;
		}
		down(k);
		int mid=(l+r)>>1;
		if(ql<=mid) update(k<<1,l,mid,ql,qr,v);
		if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,v);
	}
	void change(int k,int l,int r,int ql,int qr,int v)
	{
		if(ql<=l&&r<=qr)
		{
			lazadd[k]+=v;
			return;
		}
		down(k);
		int mid=(l+r)>>1;
		if(ql<=mid) change(k<<1,l,mid,ql,qr,v);
		if(qr>mid) change(k<<1|1,mid+1,r,ql,qr,v);
	}
	ll query(int k,int l,int r,int x)
	{
		if(l==r)
		{
			ll ans=0;
			if(tag[k]) ans=(ll)lazy[k].a*l*l+(ll)lazy[k].b*l+lazy[k].c;
			ans+=lazadd[k];
			return ans;
		}
		down(k);
		int mid=(l+r)>>1;
		if(x<=mid) return query(k<<1,l,mid,x);
		return query(k<<1|1,mid+1,r,x);
	}
}

namespace T2
{
	int leaf[N<<2];
	ll g[N<<2],lazy[N<<2];
	bool tag[N<<2];
	void up(int k)
	{
		g[k]=gcd(g[k<<1],g[k<<1|1]);
	}
	void build(int k,int l,int r)
	{
		if(l==r)
		{
			leaf[k]=l;
			g[l]=Abs(h[l+1]-h[l]);
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		up(k);
	}
	void downn(int k,ll v)
	{
		if(!leaf[k])
		{
			g[k]=lazy[k]=v;
			tag[k]=1;
		}
	}
	void getval(int k)
	{
		g[k]=Abs(T1::query(1,1,n,leaf[k]+1)-T1::query(1,1,n,leaf[k]));
	}
	void down(int k)
	{
		if(tag[k])
		{
			downn(k<<1,lazy[k]);
			downn(k<<1|1,lazy[k]);
			tag[k]=0;
		}
		if(leaf[k<<1]) getval(k<<1);
		if(leaf[k<<1|1]) getval(k<<1|1);
	}
	void update(int k,int l,int r,int ql,int qr,ll v)
	{
		if(ql<=l&&r<=qr)
		{
			downn(k,v);
			return;
		}
		down(k);
		int mid=(l+r)>>1;
		if(ql<=mid) update(k<<1,l,mid,ql,qr,v);
		if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,v);
		up(k);
	}
	void change(int k,int l,int r,int x)
	{
		if(l==r) return;
		down(k);
		int mid=(l+r)>>1;
		if(x<=mid) change(k<<1,l,mid,x);
		else change(k<<1|1,mid+1,r,x);
		up(k);
	}
}

int main()
{
	n=read(),q=read();
	T1::build(1,1,n);
	T2::build(1,1,n-1);
	while(q--)
	{
		int opt=read(),l=read(),r=read(),a=read(),b=read(),c=read();
		if(opt==1)
		{
			T1::update(1,1,n,l,r,data(a,b,c));
			if(1<=l-1) T2::change(1,1,n-1,l-1);
			if(r<=n-1) T2::change(1,1,n-1,r);
			if(l==r-1) T2::change(1,1,n-1,r-1);
			else if(l<r-1) T2::update(1,1,n-1,l,r-1,gcd(a+b,2*a));
		}
		if(opt==2)
		{
			T1::change(1,1,n,l,r,c);
			if(1<=l-1) T2::change(1,1,n-1,l-1);
			if(r<=n-1) T2::change(1,1,n-1,r);
		}
		int ans=T2::g[1];
		if(!ans) assert(0),ans=T1::query(1,1,n,1);
		write(ans,'\n');
	}
	return 0;
}
/*
5 3
2 2 4 8 12
1 1 3 0 0 4
2 3 5 0 0 8
1 1 5 4 2 4
*/
//不知道為什麼95pts過不去……