树状数组 TLE#4 求助
查看原帖
树状数组 TLE#4 求助
821939
zhi_hui_kan_ti_jie楼主2023/7/16 11:00
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 10;
int n;
int arr[maxn],ori[maxn];
int tarr[maxn];
inline int lowbit(int x){ return x&(-x); }
inline int max(int a, int b){ return a > b ? a : b; }
void add(int x, int v)
{
	for (int i = x; i <= n; i += lowbit(x))
		tarr[i] = max(tarr[i],v);
}
int ask(int x)
{
	int ret = -1e18;
	for (int i = x; i >= 1; i -= lowbit(x))
		ret = max(tarr[i], ret);
	return ret;
}
int f[maxn];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	memset(tarr, 0x83, sizeof(tarr));
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i]; arr[i] += arr[i - 1];
		ori[i] = arr[i];
	}
	sort(ori + 1, ori + 1 + n);
	for (int i = 1; i <= n; i++)
	{
		arr[i] = lower_bound(ori + 1, ori + 1 + n, arr[i]) - ori;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		f[i] = max(ask(arr[i])+i,ori[arr[i]]>=0?i:0);
		ans = max(ans, f[i]);
		add(arr[i], f[i] - i);
	}
	cout << ans;
	return 0;
}
2023/7/16 11:00
加载中...