kojingharangの日記

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

01:06 |

• N 個の数字と M 個の操作が与えられるので実行しろ。操作は範囲[L, R]の位置の数字たちに T を足す or 範囲[L, R]の位置の数字たちのgcdを印字する。
• 1≦N, M≦100,000

• 部分点 足す操作の時 L=R のやつができたら 30 点

• Segment tree をそのまま使って 30 点ゲット

• あとで
• gcd(a, b) = gcd(a, b-a) なので
• gcd(a, b, c, d) = gcd(a, gcd(b, gcd(c, d)))
• = gcd(a, gcd(b, gcd(c, d-c)))
• = gcd(a, gcd(gcd(b, c), d-c)))
• = gcd(a, gcd(gcd(b, c-b), d-c)))
• = gcd(gcd(gcd(a, b), c-b), d-c)))
• = gcd(gcd(gcd(a, b-a), c-b), d-c)))
• = gcd(a, b-a, c-b, d-c) ... もやもや

• となるので差(b-a, c-b, ...)と先頭の値 a がわかってれば良いようだ

• accepted
• (SegTree の遅延評価とかはまだ分かってない)

int main() {
	ios::sync_with_stdio(false);
	ll N, M, v, T, L, R;
	while(cin>>N) {
		SegTree<Gcd> st(N+1);
		SegTree<Add> cum(N+1);
		VI cur(N), diff(N+1);
		REP(i, N) {
			cin>>v;
			cur[i] = v;
		}
		diff[0]=cur[0];
		cum.update(0, diff[0]);
		RANGE(i, 1, N) {
			diff[i]=cur[i]-cur[i-1];
			cum.update(i, diff[i]);
			st.update(i, diff[i]);
		}
		cin>>M;
		REP(i, M) {
			cin>>T>>L>>R;
			L--; R--;
			if(T==0) {
				ll head = cum.query(0, L+1);
				ll v = st.query(L+1, R+1);
				cout<<Gcd::op(head, v)<<endl;
			} else {
				diff[L] += T;
				diff[R+1] -= T;
				st.update(L, diff[L]);
				st.update(R+1, diff[R+1]);
				cum.update(L, diff[L]);
				cum.update(R+1, diff[R+1]);
			}
		}
	}
	
	return 0;
}

ツイートする