AtCoder ABC #256 (東京海上日動プログラミングコンテスト2022) : Ex - I like Query Problem

どうにか解けてよかった。
https://atcoder.jp/contests/abc256/tasks/abc256_h

問題

整数列Aが与えられる。
以下のクエリに順次答えよ。

• 正整数L,R,xが与えられる。Aの区間[L,R]に対し、各要素をxで割って余りを切り捨てた値に上書きする。
• 正整数L,R,xが与えられる。Aの区間[L,R]に対し、各要素をxで上書きする。
• 正整数L,R,xが与えられる。Aの区間[L,R]の各要素の総和を答えよ。

解法

上2つのクエリを繰り返すと、同じ値が連続する区間ばかりになる。
2つ目のクエリは当然区間[L,R]の内容が一致するし、前者もlog(max(A))回行えば全部0になる。

各要素の値は以下ではmapで持ち、同じ値が連続する区間を1つのmapのkey-valueペアで表現することで、前者2つのクエリを処理しよう。
総和に関しては、区間加算・区間総和を求めるSegTreeまたはBITを用いることとする。

int N,Q;
template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		if(entry<0) return 0;
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
	int lower_bound(V val) { //単調増加の時のみ使える
		V v0=0,v1=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) {
			if((ent+(1<<i)-1)*(v0+bit[0][ent+(1<<i)-1])+(v1+bit[1][ent+(1<<i)-1])<val) {
				v0+=bit[0][ent+(1<<i)-1];
				v1+=bit[1][ent+(1<<i)-1];
				ent+=(1<<i);
			}
		}
		return ent;
	}
};
BIT_r<ll,23> bt;
map<int,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	M[0]=0;
	M[N+1]=0;
	FOR(i,N) {
		cin>>x;
		bt.add(i+1,i+1,x);
		M[i+1]=x;
	}
	while(Q--) {
		int L,R;
		cin>>i>>L>>R;
		
		if(i==1||i==2) {
			R++;
			int v;
			cin>>v;
			auto it=M.lower_bound(L+1);
			it--;
			M[L]=it->second;
			it=M.lower_bound(R+1);
			it--;
			M[R]=it->second;
			if(i==1) {
				int nex=L;
				while(nex<R) {
					auto it=M.lower_bound(nex);
					x=it->first;
					y=next(it)->first;
					r=it->second;
					bt.add(x,y-1,-r);
					r/=v;
					if(r) {
						M[x]=r;
						bt.add(x,y-1,r);
					}
					else {
						if(prev(it)->second) {
							M[x]=0;
						}
						else {
							M.erase(x);
						}
					}
					nex=y;
				}
			}
			else {
				int nex=L;
				while(nex<R) {
					auto it=M.lower_bound(nex);
					x=it->first;
					y=next(it)->first;
					r=it->second;
					bt.add(x,y-1,-r);
					nex=y;
					M.erase(it);
				}
				M[L]=v;
				bt.add(L,R-1,v);
			}
		}
		else if(i==3) {
			cout<<bt.total(R)-bt.total(L-1)<<endl;
		}
		
	}
}

まとめ

setやmapで区間を管理する問題、段々慣れてきて書く速度上がってきた。