yukicoder : No.876 Range Compress Query

まぁ今回は全体的に★増えるよね。
https://yukicoder.me/problems/no/876

問題

N要素の数列に対し以下のクエリに順次答えよ。

• 指定された区間[L,R]にXずつ加算する。
• 指定された区間[L,R]において、連続する同じ値を圧縮すると何要素になるか

解法

2つBITを用いて解いた。
1つめは、要素の値を管理するものである。
これで区間に対し同じ値を加算する処理がO(logN)で済む。

もう一つは、各要素が、次の要素と異なるかどうかを0/1で持つBITで、区間和を求めれば2つ目のクエリにO(logN)で求められる。

前者のクエリの結果、2つ目のBITは区間の境界をまたぐ高々2要素しか変化しないことに注意してBITを更新していこう。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> sum,num;

int N,Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>x;
		sum.add(i+1,x);
		sum.add(i+2,-x);
	}
	FOR(i,N-1) {
		if(sum(i+1)!=sum(i+2)) num.add(i+1,1);
	}
	
	FOR(i,Q) {
		int T,L,R;
		cin>>T>>L>>R;
		if(T==1) {
			cin>>x;
			if(sum(L-1)!=sum(L)) num.add(L-1,-1);
			if(sum(R)!=sum(R+1)) num.add(R,-1);
			sum.add(L,x);
			sum.add(R+1,-x);
			if(sum(L-1)!=sum(L)) num.add(L-1,1);
			if(sum(R)!=sum(R+1)) num.add(R,1);
		}
		else {
			cout<<1+num(R-1)-num(L-1)<<endl;
		}
	}
	
}

まとめ

あれ、これBITで解けるなーと思いながら解いてた。