51nod 1065 最小正子段和(树状数组+离散)

51nod 1065

【分析】首先，求的是子串和，想到前缀和，然后求的是子串和>0时候的最小和；就是sum[i]-sum[j] > 0(j < i)下的min{sum[i]-sum[j]};

而这就是求sum[i]>sum[j]时sum[j]的最大值，那么离散一下所有sum，从左往右扫描，对于每个sum[i]找出<sum[i]时的最大值即可。

【AC CODE】125ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int MAXN = 50000+10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int a[MAXN];
LL sum[MAXN];

LL mx[MAXN],cnt;
inline int lowbit(int x){return x&-x;}
void insert(int x, LL v)
{
	while(x <= cnt)
	{
		mx[x] = max(mx[x],v);
		x += lowbit(x);
	}
}
LL query(int x)
{
	LL ans = -4485090715960753727;
	while(x > 0)
	{
		ans = max(ans,mx[x]);
		x -= lowbit(x);
	}
	return ans;
}
LL sot[MAXN];
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	scanf("%d", &n);
	clc(mx,-0x3f);
	repe(i,1,n) scanf("%d", &a[i]);
	repe(i,1,n) sum[i] = sum[i-1]+a[i],sot[i] = sum[i];
	sort(sot,sot+n);
	cnt = unique(sot,sot+n)-sot;
	LL ans = INF;
	//if(a[1] > 0) ans = a[1];
	insert(lower_bound(sot,sot+cnt,0)-sot+1,0);
	repe(i,1,n)
	{
		int x = lower_bound(sot,sot+cnt,sum[i])-sot+1;
		ans = min(ans,sum[i]-query(x-1));
		insert(x,sum[i]);
	}
	printf("%lld\n", ans);
	return 0;
}