序列 [树状数组+离散化]


	序列 [树状数组+离散化]
[编程语言教程]

序列

题目描述

给定两个长度为n的序列 (a, b) 。你需要选择一个区间([l,r]),使得 (a_l+…+a_rgeqslant 0)且 (b_l+…+b_rgeqslant 0)。最大化你选择的区间长度。

输入格式

第一行一个整数 (n),第二行 (n) 个整数 (a_1 o a_n),第三行 (n) 个整数 (b_1 o b_n)。

输出格式

一行一个整数表示(max(r-l+1))。保证至少有一个区间满足条件。

样例

样例输入

5
2 -4 1 2 -2
-2 3 1 -3 1

样例输出

1

数据范围与提示

对于 (20\%) 的数据,(nleqslant 5000)。

对于 (60\%) 的数据,(nleqslant 10^5)。

对于 (100\%) 的数据,(1leqslant nleqslant 10^6,|a_i|, |b_i|leqslant 10^9)。 数据有一定梯度。

分析

看到题目就能得到三个柿子,也就是个三维偏序:

[suma_r-suma_lgeqslant 0sumb_r-sumb_lgeqslant 0-lgeqslant 0]

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 序列 [树状数组+离散化]