yukicoder : No.1234 典型RMQ

今回はだいぶ前に作られた問題を回収する回だった？
https://yukicoder.me/problems/no/1234

問題

整数列に対し、以下のクエリを順次対応せよ。

• 指定された区間内の全要素にCを加算する
• 指定された区間内の最小値を答える

解法

よくある区間更新と区間クエリのSegTree。

static ll const def=1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};

int N,Q;
ll A;
SegTree_3<ll,1<<20> st;
int K,L,R,C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A;
		st.update(i,i+1,A);
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>K>>L>>R>>C;
		L--;
		if(K==1) {
			st.update(L,R,C);
		}
		else {
			cout<<st.getval(L,R)<<endl;
		}
	}
	
}

まとめ

こういうクエリ系の問題、クエリタイプによって入力数が異なるのは面倒なので、無視する値があってもいいので数が一致してるのは助かる。