yukicoder : No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに

ようやく2100台か。
https://yukicoder.me/problems/no/2101

問題

整数列AとTが与えられる。
D日目の昼には、D≧T[i]かつA[i]＞0であるA[i]がデクリメントされる。

以下のクエリに順次答えよ。

• D,L,Rの3値が与えられる。D日目夜における、A[L]...A[R]の総和を求めよ。

解法

T[i]および各クエリのDをソートし、時間順に処理しよう。
2つBITをもって以下を管理する。

• A[i]の区間和を取るBIT
• 現在減少中であるiの区間和を取るBIT

時間順に操作し、T[i]日目及びT[i]+A[i]目に到達するたびに両BITを更新しつつ、各クエリについて両BITの値と現在日付を用いてAの総和を計算していこう。

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> AX,B;

int N;
ll A[202020],T[202020];
int Q;
ll D[202020],L[202020],R[202020],ret[202020];

vector<pair<int,int>> ev;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>T[i];
		B.add(i,A[i]);
		if(A[i]) {
			ev.push_back({T[i],i});
			ev.push_back({T[i]+A[i],i});
		}
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>D[i]>>L[i]>>R[i];
		L[i]--,R[i]--;
		ev.push_back({D[i],N+i});
	}
	sort(ALL(ev));
	FORR2(t,i,ev) {
		if(i<N) {
			if(t==T[i]) {
				B.add(i,T[i]-1);
				AX.add(i,-1);
			}
			else {
				B.add(i,-A[i]-T[i]+1);
				AX.add(i,1);
			}
		}
		else {
			i-=N;
			ret[i]=t*(AX(R[i])-AX(L[i]-1))+B(R[i])-B(L[i]-1);
		}
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

これは典型なので余り迷わなかった。