金題大戰Vol.0 B、序列

題目描述

給定兩個長度為 \(n\) 的序列\(a\), \(b\)。

你需要選擇一個區間\([l,r]\)，使得\(a_l+…+a_r>=0\)且\(b_l+…+b_r>=0\)。最大化你選擇的區間長度。

輸入格式

第一行一個整數\(n\)，第二行\(n\)個整數\(a_1-a_n\)，第三行n個整數\(b_1-b_n\)。

輸出格式

一行一個整數表示\(max(r-l+1)\)。保證至少有一個區間滿足條件。

樣例

樣例輸入

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

樣例輸出

1

數據範圍與提示

對於\(20\%\) 的數據，\(n<=5000\)。

對於\(60\%\) 的數據，\(n<=10^5\)。

對於\(100\%\) 的數據，\(1<=n<=10^6，|ai|, |bi|<=10^9\)。數據有一定梯度。

分析

乍看上去這一道題似乎不太好處理，要同時滿足下標、\(a\)、\(b\)三個條件

突破點就在於怎麼把限制條件一維一維地刪去

首先我們把題目中給出的數組轉化成前綴和的形式

即 \(suma[r]>=suma[l],sumb[r]>=sumb[l]\)

我們將 \(suma\) 從小到大排一下序

這樣我們每一次從左到右遍歷，就相當於消去了一維

我們只考慮 \(sumb\) 和坐標的關係即可

這種關係我們可以用樹狀數組去維護，即把 \(sumb\) 的值作為樹狀數組的下標，把原先的編號作為樹狀數組的權值

這樣在每次遇到一個點時，我們在樹狀數組中查詢 \(sumb\) 比它小的最小的下標

同時更新下標為 \(sumb\) 的節點的值為當前點的編號

\(sumb\) 比較大，並且有負數，因此考慮離散化

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int a[maxn],b[maxn],n,cnt,tr[maxn];
ll suma[maxn],sumb[maxn];
struct asd{
	int wz;
	ll jla,jlb;
}jl[maxn];
bool cmp(asd aa,asd bb){
	return aa.jla<bb.jla;
}
int lb(int xx){
	return xx&-xx;
}
void ad(int wz,int val){
	for(int i=wz;i<=n;i+=lb(i)){
		tr[i]=min(tr[i],val);
	}
}
int cx(int wz){
	int ans=0x3f3f3f3f;
	for(int i=wz;i>0;i-=lb(i)){
		ans=min(ans,tr[i]);
	}
	return ans;
}
int main(){
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	int ans=1,bef,wz;
	memset(tr,0x3f,sizeof(tr));
	n=read();
	for(register int i=1;i<=n;i++){
		a[i]=read();
		suma[i]=suma[i-1]+(ll)a[i];
	}
	for(register int i=1;i<=n;i++){
		b[i]=read();
		sumb[i]=sumb[i-1]+(ll)b[i];
	}
	for(register int i=1;i<=n;i++){
		jl[i].jla=suma[i];
		jl[i].jlb=sumb[i];
		if(jl[i].jla>=0 && jl[i].jlb>=0){
			ans=max(ans,i);
		}
		jl[i].wz=i;
	}
	sort(jl+1,jl+1+n,cmp);
	sort(sumb+1,sumb+1+n);
	cnt=unique(sumb+1,sumb+1+n)-sumb-1;
	for(int i=1;i<=n;i++){
		wz=lower_bound(sumb+1,sumb+cnt+1,jl[i].jlb)-sumb;
		bef=cx(wz);
		if(bef>=jl[i].wz){
			ad(wz,jl[i].wz);
			continue;
		}
		ans=max(ans,jl[i].wz-bef);
		ad(wz,jl[i].wz);
	}
	printf("%d\n",ans);
	return 0;
}

Tags: 基礎--前綴和數據結構--樹狀數組