抽象问题,关于st表第二维开成2都能过这件事
查看原帖
抽象问题,关于st表第二维开成2都能过这件事
895690
gghack_Nythix楼主2024/8/27 11:06

rt

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[2000005],sum[2000005],st[2000005][2];
int ans;
#define query(l,r) min(st[l][(int)(floor)(log2(r-l+1))],st[r-(1<<(int)(floor)(log2(r-l+1)))+1][(int)(floor)(log2(r-l+1))])
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;++i) cin >> a[i],a[i + n] = a[i];
	for(int i = 1;i <= 2 * n;++i) sum[i] = sum[i - 1] + a[i],st[i][0] = sum[i];
	for(int j=1;j<=log2(2*n);++j)for(int i=1;i+(1<<(j-1))-1<=2*n;++i)st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	for(int l = 1;l <= n;++l) {
		int r = l + n - 1;
		int minn = query(l,r);
		if(minn >= sum[l - 1])++ans;
	}
	return cout << ans << '\n',0;
}
2024/8/27 11:06
加载中...