题目传送门

前言

赛时感觉 6 道题唯一可以做出的题，但是赛后感觉除了三个黑题，其他也可以做一下的。看来是有场切蓝题的能力的 awa。

题解部分

考虑一个区间 $[l,r]$ 要满足什么性质才可以打出无限次：

• 打完一轮之后不能亏费。

• 最低的情况也需要保持 $\ge 0$。

对于第一种情况显然很好做，记录一个前缀和即可。对于第二种情况我们考虑如何快速的找到一个区间中最低的情况（找到谷）。对于 $a_i\ge b_i$ 的情况，全部选了肯定可以更低。选了这些之后，我们还可以再选择一个 $a_i$，或者在刚刚选择过的 $(a,b)$ 中，扔掉一个 $b$，就能达到最低点了。为了方便描述，前者记为 $d_i$（如果不选，则 $d_i=0$），后者记为 $p_i$，而区间 $[l,r]$ 的最低点 $pos=\displaystyle\sum_{i=l}^r d_i+\min_{i=l}^r p_i$。

时间复杂度为 $O(n^2)$，还需要优化。

可以发现，当 $r\to r+1$ 的时候，$pos$ 只会单调不增。那么就可以用双指针。这个时候就还有性质 1，用一个数据结构记录 $s$（前缀和）的权值，然后找到那些 $s_i\ge s_{l-1}$ 即可。左端点右移的时候 $\min$ 也要重新计算一次，也可以使用一个数据结构。时间复杂度为 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define ll long long
ll inline read()
{
    ll num=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='0')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){num=(num<<3)+(num<<1)+(ch^48);ch=getchar();}
    return num*f;
}
int n;ll E,ans;
ll a[N],b[N],d[N],s[N],p[N],sd[N];
struct STable
{
    ll st[22][N];
    void build()
    {
        for(int i=1;i<=n;i++)st[0][i]=p[i];
        for(int i=1;(1<<i)<=n;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
    }
    ll ask(int l,int r)
    {
        int t=__lg(r-l+1);
        return min(st[t][l],st[t][r-(1<<t)+1]);
    }
}ST;
#define lb (x&-x)
struct BIT
{
    int t[N];
    void add(int x,int v){while(x<=n+1)t[x]+=v,x+=lb;}
    int ask(int x){int res=0;while(x)res+=t[x],x-=lb;return res;}
}T;
ll c[N];
void discret(ll A[N])
{
    for(int i=0;i<=n;i++)c[i]=A[i];
    sort(c,c+1+n);int l=unique(c,c+1+n)-c-1;
    for(int i=0;i<=n;i++)A[i]=lower_bound(c,c+1+l,A[i])-c+1;
}
int main(){
    n=read();E=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)
    {
        d[i]=min(0ll,b[i]-a[i]);
        s[i]=s[i-1]+b[i]-a[i];
        p[i]=-a[i]-d[i];
        sd[i]=sd[i-1]+d[i];
    }
    discret(s);ST.build();
    for(int L=1,R=1;L<=n;L++)
    {
        ll sum=sd[R]-sd[L-1],mn=ST.ask(L,R);
        while(R<=n)
        {
            if(sum+mn+E>=0)T.add(s[R++],1),sum+=d[R],mn=min(mn,p[R]);
            else break;
        }
        ans+=R-L-T.ask(s[L-1]-1);
        if(L==R)R++;else T.add(s[L],-1);
    }
    printf("%lld",ans);
    return 0;
}

My Stupid Mistake

赛时 $s_0$ 要离散化但是没做，发现了。双指针 $L>R$ 没有发现，导致 SubTask 4 获得 RE 而 SubTask 5 没炸，还以为被评测机针对了。

赛后再码一遍（没有原来代码了）有如下错误：

• const int N=2e5+5; 超好习惯。

• ST 表写挂了。

• int ans; 不开 long long 见祖宗。最简单的问题却总是在我发完帖才发现的。

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define int long long
const int N=1e6+10;
int a[N],b[N],s[N],lsh[N];int n,e;
struct node{int l,r,md,mu,s1;}tr[N<<2];
void pushup(int p)
{
	node n1=tr[lc(p)],n2=tr[rc(p)];
	if(n1.md==-1)tr[p].md=n2.md;
	else if(n2.md==-1)tr[p].md=n1.md;
	else tr[p].md=(b[n1.md]>b[n2.md])?n1.md:n2.md;
	if(n1.mu==-1)tr[p].mu=n2.mu;
	else if(n2.mu==-1)tr[p].mu=n1.mu;
	else tr[p].mu=(a[n1.mu]>a[n2.mu]?n1.mu:n2.mu);
	tr[p].s1=tr[lc(p)].s1+tr[rc(p)].s1;
}
void bt(int p,int l,int r)
{
	tr[p]={l,r,-1,-1,0};
	if(l==r)
	{
		if(a[l]>b[l])tr[p].s1=a[l]-b[l],tr[p].md=l;
		else tr[p].mu=l;
		return;
	}
	int mid=(l+r)>>1;
	bt(lc(p),l,mid);bt(rc(p),mid+1,r);
	pushup(p);
}
int query1(int p,int l,int r)//getmd
{
	if(tr[p].r<l||tr[p].l>r)return -1;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].md;
	int n1=query1(lc(p),l,r),n2=query1(rc(p),l,r);
	if(n1==-1)return n2;
	if(n2==-1)return n1;
	return b[n1]>b[n2]?n1:n2;
}
int query2(int p,int l,int r)//getmu
{
	if(tr[p].r<l||tr[p].l>r)return -1;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].mu;
	int n1=query2(lc(p),l,r),n2=query2(rc(p),l,r);
	if(n1==-1)return n2;
	if(n2==-1)return n1;
	return a[n1]>a[n2]?n1:n2;
}
int query3(int p,int l,int r)//gets1
{
	if(tr[p].r<l||tr[p].l>r)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].s1;
	return query3(lc(p),l,r)+query3(rc(p),l,r);
}
bool check(int l,int r)
{
	int get1=query1(1,l,r),get2=query2(1,l,r),get3=query3(1,l,r);
	int sum=max(b[get1],a[get2])+get3;
	if(sum>e)return 1;
	return 0;
}
struct node1{int x,v;};
vector<node1>G[N];
int c[N];
void add(int x){for(;x<=n;x+=x&-x)c[x]++;}
int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
signed main()
{
	cin>>n>>e;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=n;i;i--)s[i]=s[i+1]-a[i]+b[i],lsh[i]=s[i];
	sort(lsh+1,lsh+n+2);int k=unique(lsh+1,lsh+n+2)-lsh-1;
	for(int i=1;i<=n+1;i++)s[i]=lower_bound(lsh+1,lsh+k+1,s[i])-lsh;
	bt(1,1,n);
	int ans=0;
	for(int l=1,r=1;r<=n;r++)
	{
		while(l<=r&&check(l,r))l++;
		int x=s[r+1];
		if(l<r)
		{
			G[l-1].push_back({x,-1});
			G[r].push_back({x,1});
		}
		if(l==r&&a[l]-b[l]<=0)
		{
			G[l-1].push_back({x,-1});
			G[r].push_back({x,1});
		}
	}
	for(int i=1;i<=n;i++)
	{
		add(s[i]);
		for(auto j:G[i])
		{
			ans+=j.v*(i-get(j.x-1));
		}
	}
	cout<<ans;
	return 0;
}