AtCoder ABC #255 (エイシングプログラミングコンテスト2022) : Ex - Range Harvest Query

こっちの方が簡単だった。
https://atcoder.jp/contests/abc255/tasks/abc255_h

問題

N個の木があり、いずれも実の数は0個である。
1日ごとに、i番目の木にはi個の実がなる。

ここで、以下のクエリがQ個与えられるので準備処理せよ。なお、各クエリの操作結果は、以降にクエリにも影響する。

• D[i]日目に、L[i]番目～R[i]番目の木になっている実をすべて取り除く。その際取り除いた実の総数を答えよ。

解法

ある木の区間に対し、最後に実を取り除いた日がいつかを、mapを使って管理しよう。
最後に実を取り除いた日から現在の日付までの日数がわかれば、その木の区間で得られる実の数はO(1)で計算できる。

クエリ1回ごとにこのmapが操作される回数は均しでO(1)で済むので、map操作にO(logQ)かかるとしても全クエリ合計でO(QlogQ)で済む。

ll N,Q;
ll D[202020],L[202020],R[202020];
const ll mo=998244353;

__int128 hoge(__int128 L, __int128 R) {
	__int128 ret=(L+R-1)*(R-L)/2%mo;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	
	map<ll,ll> ev;
	ev[0]=ev[1LL<<60]=0;
	
	FOR(i,Q) {
		cin>>D[i]>>L[i]>>R[i];
		
		R[i]++;
		auto it=ev.lower_bound(L[i]+1);
		it--;
		ev[L[i]]=it->second;
		it=ev.lower_bound(R[i]+1);
		it--;
		ev[R[i]]=it->second;
		
		__int128 ret=0;
		while(1) {
			it=ev.lower_bound(L[i]);
			ll cur=it->first;
			ll d=it->second;
			if(cur>=R[i]) break;
			ll nex=next(it)->first;
			ev.erase(it);
			(ret+=hoge(cur,nex)%mo*(D[i]-d))%=mo;
		}
		ev[L[i]]=D[i];
		cout<<(ll)ret<<endl;
		
	}
	
}

まとめ

最初、全クエリの実の合計だけ取る問題と勘違いして、全然違うアプローチのコードを書いてしまった。