[CSP-S模拟测试]:序列（二分答案+树状数组）

题目传送门（内部题98）

输入格式

　　第一行一个整数$n$，第二行$n$个整数$a_1\sim a_n$，第三行$n$个整数$b_1\sim b_n$。

输出格式

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

样例

样例输入：

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

样例输出：

数据范围与提示

　　对于$20\%$的数据，$n\leqslant 5,000$。
　　对于$60\%$的数据，$n\leqslant 10^5$。
　　对于$100\%$的数据，$1\leqslant n\leqslant 5\times 10^5,|ai|,|bi|\leqslant 10^9$。
　　数据有一定梯度。

题解

又没有打正解。

先来看一个性质，设$s$为一个序列的前缀和，那么如果$i<j$且$s[j]\geqslant s[i]$，那么这一段的加和大于$0$。

于是我们可以二分枚举长度，然后用$b$的前缀和数组为下标构建树状数组维护$a$的前缀和数组的最小值即可。

时间复杂度：$\Theta(n\log^2 n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

unordered_map<long long,int>mp;

int n;

int a[500001],b[500001],tr[1000001],cnt;

long long sa[500001],sb[500001],sta[1000001];

int ans;

int lowbit(int x){return x&-x;}

void add(int x,int w){for(int i=x;i<=sta[0];i+=lowbit(i))tr[i]=min(tr[i],w);}

int ask(int x){int res=0x3f3f3f3f;for(int i=x;i;i-=lowbit(i))res=min(res,tr[i]);return res;}

bool judge(int x)

{

	memset(tr,0x3f,sizeof(tr));

	for(int i=x;i<=n;i++)

	{

		add(sb[i-x],sa[i-x]);

		if(ask(sb[i])<=sa[i])return 1;

	}

	return 0;

}

int main()

{

	scanf("%d",&n);sta[++sta[0]]=0;

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		sa[i]=sa[i-1]+a[i];

		sta[++sta[0]]=sa[i];

	}

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&b[i]);

		sb[i]=sb[i-1]+b[i];

		sta[++sta[0]]=sb[i];

	}

	sort(sta+1,sta+sta[0]+1);

	for(int i=1;i<=sta[0];i++)if(sta[i]!=sta[i-1])mp[sta[i]]=++cnt;

	for(int i=0;i<=n;i++){sa[i]=mp[sa[i]];sb[i]=mp[sb[i]];}

	int lft=1,rht=n,res=1;

	while(lft<=rht)

	{

		int mid=(lft+rht)>>1;

		if(judge(mid)){res=mid;lft=mid+1;}

		else rht=mid-1;

	}

	printf("%d",res);

	return 0;

}

rp++

巴特西