yukicoder : No.865 24時間降水量

865と866はだいぶ難易度差があると思うけどなぁ。
https://yukicoder.me/problems/no/865

問題

整数列Aが与えられる。
Aの1要素を更新するクエリが計Q回与えられるので、そのつど連続する24要素の和の最大値を求めよ。

解法

B[i]=sum(A[i...(i+23)])とする。
Aを1個更新するとBが24個更新されるので、適宜最大値を答えればよい。

int N;
int A[202020];
ll S[202020];
ll ma;
int Q,T,V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		FOR(j,24) {
			S[i+j]+=A[i];
			ma=max(ma,S[i+j]);
		}
	}
	cin>>Q;
	while(Q--) {
		cin>>T>>V;
		T--;
		int d=V-A[T];
		A[T]=V;
		FOR(j,24) {
			S[T+j]+=d;
			ma=max(ma,S[T+j]);
		}
		cout<<ma<<endl;
	}
	
}

まとめ

★2.5でもよさそう。