これは似たようなテクを使ったことがあったのでまぁ。
https://atcoder.jp/contests/abc282/tasks/abc282_h
問題
N要素の2つの非負整数列A,Bが与えられる。
1≦L≦R≦Nとなる(L,R)の対のうち、となるものは何通りか。
解法
あらかじめBの累積和を取っておく。
A[i]の小さい順に、「区間内の最小値がA[i]となるような区間」に関する数え上げを行う。
今X,YをA[X]≦A[i]となるi未満最大のX、A[Y]<A[i]となるi以上最小のYとする。X<L≦i≦R<YとするL,Rを取れば、minの部分はA[i]に確定する。
R-i<i-Lの場合、Rを総当たりしよう。Rを定めたとき、Bの累積和を二分探索することでLをどこまで小さくできるかを求めることができる。
その場合、それより大きなLでも問題の条件を満たすので、(i-L+1)だけ解に計上する。
i-L≦R-iの場合、反対にLを総当たりすればよい。
int N; ll S; ll A[252525],B[252525]; ll BS[252525]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; set<int> did={0,N+1}; vector<pair<ll,int>> V; FOR(i,N) { cin>>A[i+1]; V.push_back({A[i+1],i+1}); } FOR(i,N) { cin>>B[i+1]; BS[i+1]=BS[i]+B[i+1]; } ll ret=0; sort(ALL(V)); FORR2(v,i,V) { auto it=did.lower_bound(i); int R=*it; int L=*--it; did.insert(i); if(R-i<=i-L) { ll a=A[i]; for(x=i;x<R;x++) { a+=B[x]; if(a>S) break; int TL=i; for(y=20;y>=0;y--) { if(TL-(1<<y)<=L) continue; if(BS[x]-BS[TL-(1<<y)-1]+A[i]<=S) TL-=1<<y; } ret+=i-TL+1; } } else { ll a=A[i]; for(x=i;x>L;x--) { a+=B[x]; if(a>S) break; int TR=i; for(y=20;y>=0;y--) { if(TR+(1<<y)>=R) continue; if(a+BS[TR+(1<<y)]-BS[i]<=S) TR+=1<<y; } ret+=TR-i+1; } } } cout<<ret<<endl; }
まとめ
悪くはないんだけど、ちょっと遅かったな…。