思路

看到题发现做个前缀和之后只需要支持单点删除和查询某个值的排名。因此平衡树做完了。

不难想到先给 $D$ 数组做一个前缀和，然后我们的答案就是 $T_i - qzhD_i\le 0$ 的数的个数。我们考虑我们如果从 $i$ 个实验开始做起，那么我们的所有 $qzhD$ 的值都会减去一个 $qzhD_i$。我们肯定是不希望去进行修改操作的，因此我们把 $qzhD_i$ 在判断的式子中移到右边去，变成了 $T - qzhD\le -qzhD_i$ 的个数，我们可以用平衡树快速查询。因此，我们只需要把所有的 $T_i - qzhD_i$ 全部先丢进平衡树里面，然后枚举一下从哪一个实验开始做起，每次把上一个实验的值在平衡树里删除后查询一下小于等于 $-qzhD_i$ 的个数跟 $ans$ 取个 max 即可。

代码

#include<bits/stdc++.h>
#define int long long
#define n 500000 + 39
using namespace std;
int qzh[n];
struct Node{
	int l,r,key,val,len;
}a[n];
int tot=0,rot;	
void push_up(int p){
	a[p].len=a[a[p].l].len+a[a[p].r].len+1;
}
//-----------------------------------------合并 
int merge(int rot1,int rot2){
	if(rot1==0){
		return rot2;
	}
	else if(rot2==0){
		return rot1;
	}
	if(a[rot1].key<a[rot2].key){
		a[rot1].r=merge(a[rot1].r,rot2);
		push_up(rot1);
		return rot1;
	}
	else{
		a[rot2].l=merge(rot1,a[rot2].l);
		push_up(rot2);
		return rot2;
	}
}
//-----------------------------------------按权值拆 
void val_split(int now,int k,int &rot1,int &rot2){
	if(now==0){
		rot1=0;
		rot2=0;
		return;
	}
	else if(a[now].val<=k){
		rot1=now;
		val_split(a[rot1].r,k,a[rot1].r,rot2);
	}
	else{
		rot2=now;
		val_split(a[rot2].l,k,rot1,a[rot2].l);
	}
	push_up(now);
}
//-----------------------------------------按排名拆 
void k_split(int now,int k,int &rot1,int &rot2){
	if(now==0){
		rot1=0;
		rot2=0;
		return;
	}
	push_up(now);
	if(a[a[now].l].len<k){
		rot1=now;
		k_split(a[rot1].r,k-a[a[rot1].l].len-1,a[rot1].r,rot2);
	}
	else{
		rot2=now;
		k_split(a[rot2].l,k,rot1,a[rot2].l);
	}
	push_up(now);	
}
//-------------------------------------新建节点 
void New_Node(int val){
	a[++tot].key=rand()%114514+1;
	a[tot].l=0;
	a[tot].r=0;
	int rot1,rot2,now=tot;
	a[tot].len=1;
	a[tot].val=val;
	val_split(rot,val,rot1,rot2);
	rot=merge(merge(rot1,now),rot2);
}
//-------------------------------------删除 
void Erase(int val){
	int rot1,rot2,rot3,rot4;
	val_split(rot,val-1,rot1,rot2);
	k_split(rot2,1,rot3,rot4);
	rot=merge(rot1,rot4);
}
//-------------------------------------查找 
int Find_k(int val){
	int rot1,rot2;
	val_split(rot,val-1,rot1,rot2);	
	int x = a[rot1].len + 1; 
	rot=merge(rot1,rot2);
	return x;
}
void Find_val(int k){
	int rot1,rot2,rot3,rot4;
	k_split(rot,k-1,rot1,rot2);
	k_split(rot2,1,rot3,rot4);
	rot=merge(rot1,merge(rot3,rot4));
}
int reactions(signed N, std::vector<signed> D, std::vector<long long> T){
	srand(time(0));
	int ans = 0;
	for(int i = 1; i <= N; i ++){
		qzh[i] = qzh[i - 1] + D[i - 1];
		New_Node(T[i - 1] - qzh[i]);//把节点加进去
	}
	ans = Find_k(1) - 1;
	for(int i = 1; i <= N; i ++){
		Erase(T[i - 1] - qzh[i]);//删除不做的实验
		ans = max(ans, Find_k(0 - qzh[i] + 1) - 1);//答案取max
	}
	return ans;
}
//signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0), cout.tie(0);
//	int N;
//	vector<int> D, T;
//	cin >> N;
//	for(int i = 1; i <= N; i ++){
//		int w; 
//		cin >> w;
//		D.push_back(w);
//	}
//	for(int i = 1; i <= N; i ++){
//		int w;
//		cin >> w;
//		T.push_back(w);
//	}
//	cout << reactions(N, D, T);
//	return 0;
//}

AC 记录。

解题思路

根据题意，不难写出一个暴力程序。

int reactions(int N,vector<int> D,vector<long long> T)
{
    int ans=0;
    for(int s=0;s<N;s++)
    {
        long long sum=0,cnt=0;
        for(int i=s;i<N;i++)
        {
            sum+=D[i];
            if(sum>=T[i]) cnt++;
        }
       ans=max(ans,int(cnt));
    }
    return ans;
}

很显然，这个程序会超时。

先使用前缀和将程序的求和部分改写。

#include<bits/stdc++.h>
using namespace std;
long long sum[500010];
int reactions(int N,vector<int> D,vector<long long> T)
{
    int ans=0;
    //由于vector下标从0开始，所以这个前缀和比较奇怪
    for(int i=0;i<N;i++) sum[i+1]=sum[i]+D[i];
    for(int s=0;s<N;s++)
    {
        int cnt=0;
        for(int i=s;i<N;i++) if(sum[i+1]-sum[s]>=T[i]) cnt++;
       ans=max(ans,cnt);
    }
    return ans;
}

我们可以从代码中提取出一个不等式。

发现它左边的下标有一个 $i$ 和 $s-1$，很不好算，所以将这个不等式变形。

现在，我们将问题转化为了求所有的满足 $i\in[s,N)$ 且 $sum_i-T_i\ge sum_{s-1}$ 的 $i$ 的个数，显然可以用树状数组或平衡树来维护。因为树状数组要离散化，所以本题解选择平衡树解决。

AC 代码

#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
ll sum[500010];
//pbds的平衡树会去重，为了防止重复元素，使用pair存储{每个元素的值，插入id}保证每个元素的唯一性
tree<pair<ll,ll>,null_type,greater<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update> tr;
int reactions(int N,vector<int> D,vector<ll> T)
{
    int ans=0;
    for(int i=0;i<N;i++) sum[i+1]=sum[i]+D[i];
    for(int i=0;i<N;i++) tr.insert({sum[i+1]-T[i],i});//提前将所有sum_i-T_i插入
    for(int s=0;s<N;s++)
    {
        int cnt=tr.order_of_key({sum[s],-1e9});//查找sum_{s-1}的排名，其实就是查找比它大的数的个数
        ans=max(ans,cnt);
        tr.erase({sum[s+1]-T[s],s});//维护区间，将小于s的i删去
    }
    return ans;
}