Codeforces #1068 : Div2. F. Isla's Memory Thresholds

平方分割はいつも細かいバケツサイズの調整に手間取る…。
https://codeforces.com/contest/2173/problem/F

問題

減少列Aが与えられる。
以下のクエリにそれぞれ答えよ。

• 部分列A[L...R]と整数値Xが与えられる。
• 変数Y=0とし、A[L]～A[R]を順にYに足しこんでいく。その際、YがX以上になったらYを0に戻すとする。
• Yを0に戻した回数と、最終的なYの値を答えよ。

解法

Aは降順なので、Yを0に戻す頻度はだんだん減っていく。
各クエリのXをあらかじめ操作しておき、Y=0を戻す頻度が1～√Nとなるindexを列挙しておく。
これにより、Y=0に戻す頻度が√N以下である区間は、√Nで処理できる。
あとはY=0に戻すたびにindexを√N以上勧められるので、高々√N回で済む。

int T,N,Q;
int A[202020];
ll S[202020];
int L[202020],R[202020],X[202020];
const int DI=400;
int dp[DI+2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) {
			cin>>A[i];
			S[i+1]=S[i]+A[i];
		}
		vector<ll> Xs;
		FOR(i,Q) {
			cin>>L[i]>>R[i]>>X[i];
			L[i]--;
			Xs.push_back(X[i]);
		}
		sort(ALL(Xs));
		Xs.erase(unique(ALL(Xs)),Xs.end());
		for(int l=1;l<=DI;l++) {
			FOR(x,Q) dp[l][x]=-1;
			x=0;
			for(j=N-l;j>=0;j--){
				for(;x<Xs.size()&&Xs[x]<=S[j+l]-S[j];x++) dp[l][x]=j;
			}
		}
		FOR(i,Q) {
			int CL=L[i],CR=R[i],CX=X[i];
			int id=lower_bound(ALL(Xs),X[i])-Xs.begin();
			ll num=0,sum=0;
			//長さDIまで
			for(j=1;j<=DI;j++) if(dp[j][id]>=CL) {
				x=min(CR-CL,dp[j][id]-CL+j)/j;
				num+=x;
				CL+=x*j;
			}
			while(1) {
				if(S[CR]-S[CL]<CX) {
					cout<<num<<" "<<S[CR]-S[CL]<<"\n";
					break;
				}
				CL=lower_bound(S+CL,S+CR,S[CL]+CX)-S;
				num++;
			}
		}
		
	}
}

まとめ

ちょっと変則的な平方分割？