序列 [树状数组+离散化]
序列
题目描述
给定两个长度为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]