Codeforces #250 Div1 D. The Child and Sequence

苦手かつあまり好きでないクエリ問題…。
http://codeforces.com/contest/438/problem/D

問題

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

1. L,Rに対しA[L]～A[R]の和を出力する。
2. L,R,xに対しL ≤ i ≤ RとなるiにおいてA[i] = A[i] % xにする。
3. K,xに対しA[K]=xにする。

解法

2種類の値、すなわち要素群の和と、要素群の最大値を持つSegTreeを作る。
1番のクエリは定石通り和を出力する。
2番のクエリは、最大値がx以上である限り要素を探索し、mod xの計算をしていく。
3番のクエリは要素群の和と最大値を定石通り更新するだけ。

1番と3番のクエリの計算量はO(logN)なので何も問題ないが、問題は2番のクエリ。へたすれば毎回O(N)かかりそう。
しかしこれはmodの特性より解決できる。
ある値にmodを取って値が小さくなった場合、元の値の半分以下になる。
よって各値は最大で(log A[i])回程度しかmodを取って値が小さくなることはなく、M回の毎クエリで値が小さくなることはない。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	vector<int> val2;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val.resize(NV*2); val2.resize(NV*2);clear();};
	void clear() { int i; FOR(i,NV*2) val[i]=val2[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 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 update2(int x,int y,int l,int r,int k,int v) {
		if(r<=x || y<=l) return;
		if(val2[k]<v) return;
		if(l+1==r) {
			val[k]%=v;
			val2[k]=val[k];
			return;
		}
		update2(x,y,l,(l+r)/2,k*2,v);
		update2(x,y,(l+r)/2,r,k*2+1,v);
		val[k]=val[k*2]+val[k*2+1];
		val2[k]=comp(val2[k*2],val2[k*2+1]);
	}
	void update2(int x,int y,int v) { update2(x,y,0,NV,1,v);}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=val2[entry]=v;
		while(entry>1) entry>>=1, val[entry]=val[entry*2]+val[entry*2+1], val2[entry]=comp(val2[entry*2],val2[entry*2+1]);
	}
};


SegTree_1<ll,1<<17> seg;
int N,M;

void solve() {
	int f,i,j,k,l,r,x,y;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		seg.update(i+1,x);
	}
	
	while(M--) {
		cin>>i;
		if(i==1) {
			cin>>l>>r;
			cout << seg.getval(l,r+1) << endl;
		}
		else if(i==2) {
			cin>>l>>r>>x;
			seg.update2(l,r+1,x);
		}
		else if(i==3) {
			cin>>x>>y;
			seg.update(x,y);
		}
	}
}

まとめ

modの特性はともかく、2種類の値を更新していくSegTreeがそもそも初めてだった。
このテクは覚えておかねば。