AtCoder ARC #017 : D - ARCたんクッキー

ちょっとややこしいが落ち着いて解けば難しくない。
http://arc017.contest.atcoder.jp/tasks/arc017_4

問題

N要素の数列A[i]がある。
この数列に対し以下のM個のクエリを処理せよ。

1. L,Rが与えられるので、A[L]～A[R]の最大公約数を返す。
2. L,R,Tが与えられるので、A[L]～A[R]にTを加算する。

解法

１つ目のクエリではL==Rの時答えはA[L]となるので、最低A[x]を簡単に計算するデータ構造がいる。
よって、Bit Index TreeでA[x]の値を管理しよう。

問題はL＜Rの時の最大公約数計算である。
しかし、gcd(A[L],A[L+1],A[L+2],...,A[R-2],A[R-1],A[R])は、ユークリッドの互除法を考えるとgcd(A[L],A[L+1]-A[L],A[L+2]-A[L+1],...,A[R-1]-A[R-2],A[R]-A[R-1])と先頭のA[L]を除くと隣接要素の差分の最大公約数をとっても同じである。

よって、要素の差分に対して最大公約数を保持するようなSegment Treeをもう１つ作る。
２つ目のクエリに対してはBit Index TreeでA[x]にTを加えつつ、Segment TreeにおいてA[L]-A[L-1]にTを加え、A[R+1]-A[R-1]からTを引いてそれぞれの区間の最大公約数を更新していけばよい。

BITとSegTree共に参照・更新がO(logN)なので、全体でO(M logN)で処理できる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	BIT(){clear();};
	void clear() {ZERO(bit);};

	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){ return __gcd(abs(l),abs(r));};
	
	SegTree_1(){val.resize(NV*2); clear();};
	void clear() { int i; FOR(i,NV*2) val[i]=0;}
	
	V getval(int x,int y,int l,int r,int k) {
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	V getval(int x,int y) { return getval(x,y,0,NV,1);}
	void update(int entry, V v) {
		entry += NV;
		val[entry]+=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

BIT<int,19> bt;
SegTree_1<int,1<<19> st;

int N,M;
ll A[1000001];

void solve() {
	int f,i,j,k,l,r,x,y,t;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	bt.update(1,A[0]);
	FOR(i,N-1) bt.update(i+2,A[i+1]-A[i]);
	FOR(i,N-1) st.update(i+2,A[i+1]-A[i]);
	
	cin>>M;
	FOR(i,M) {
		cin>>t>>x>>y;
		if(t!=0) {
			bt.update(x,t);
			bt.update(y+1,-t);
			st.update(x,t);
			st.update(y+1,-t);
		}
		else {
			_P("%d\n",__gcd(bt.total(y),st.getval(x+1,y+1)));
		}
	}
}