序列
题目描述
给定两个长度为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 0\
sumb_r-sumb_lgeqslant 0\
r-lgeqslant 0]
但是三个不等式是非常难以维护的，所以我们考虑简化一下这三个式子。
我们可以首先让一个条件满足，我们先按 (suma) 的大小升序排序，这样第一个式子就绝对满足了，我们只需要考虑剩下的二维偏序问题。
因为 (sumb) 的范围肯定要比 (long long) 还大，所以我们需要离散化来进行存储。因为我们需要满足在 (sumb) 的条件满足的情况下，找到当前这个位置向左拓展的最小的左边界，这个区间的长度就是答案。
根据上边所说的，我们就可以使用树状数组来维护每个 (sumb) 的最小左端点，用 (sumb) 当作下标（离散化之后的），用当前这个值的位置来更新值，在查询的时候查询这个位置即可，答案就是当前值的位置减去查询到的左端点，取 (max) 即可。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
ll suma[maxn],sumb[maxn];
struct Node{
ll a,b,id;
}jl[maxn];
ll n;
inline ll read(){
ll s = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
return s*f;
}
int t[maxn];
int lowbit(int x){
return x & -x;
}
void modify(int x,int val){//修改最小值
while(x <= n){
t[x] = min(t[x],val);
x += lowbit(x);
}
}
int query(int x){//查询最小左端点
int res = 0x3f3f3f3f;
while(x){
res = min(res,t[x]);
x -= lowbit(x);
}
return res;
}
bool cmp(Node x,Node y){//按suma排序
return x.a < y.a;
}
int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
memset(t,0x3f,sizeof(t));//因为要维护最小的左端点，所以初始化极大值
n = read();
for(register int i = 1;i <= n;++i){
ll x = read();
jl[i].id = i;
suma[i] = suma[i-1] + x;
jl[i].a = suma[i];
}
for(register int i = 1;i <= n;++i){
ll x = read();
sumb[i] = sumb[i-1] + x;
jl[i].b = sumb[i];
}
int ans = 1;
for(register int i = 1;i <= n;++i){
if(sumb[i] >= 0 && suma[i] >= 0){//先提前处理一下，不然会挂
ans = max(ans,i);
}
}
sort(jl+1,jl+n+1,cmp);//按suma排序，去掉一个限制条件
//以下两行离散化
sort(sumb+1,sumb+n+1);
int q = unique(sumb+1,sumb+n+1)-sumb-1;
for(int i=1;i<=n;++i){
int pos = lower_bound(sumb+1,sumb+q+1,jl[i].b) - sumb;//找到这个sumb的位置（也就是离散化后的值）
modify(pos,jl[i].id);//修改
ans = max((ll)ans,jl[i].id - query(pos));//查询并更新答案
}
printf("%d
",ans);
return 0;
}