[ABC282Ex] Min + Sum
__stick
·
·
题解
题意
给出序列 a,b，求出满足：
\sum_{i=l}^rb_i+\min_{i=l}^r a_i\le s
的 (l,r) 数量，其中 1\le l\le r\le n。
思路
算是比较套路的题了，区间问题想一下分治总之没有错。
我们对序列分治，然后处理出来分治中点到左右端点的 a 的前缀最小值，b 的前缀和。
然后当前分治区间内的问题就变成了：
\min(mmin_i,mmin_j)+sum_i+sum_j\le s,i\in[l,mid],j\in[mid+1,r]
的 (i,j) 个数。
其中 mmin 和 sum 就表示从分治中点到位置 i 的前缀最小值和前缀和（当然，对于左半区间其实是后缀）。
我们盯一下上面的柿子，发现只需要去掉 \min 就会非常好做。
由于 b_i\ge0 所以 sum 其实是单调的，而 mmin 肯定是单调的，我们枚举 i ，二分出来 mmin_j\ge mmin_i 的 j 的位置，然后对于小于当前位置的 j ，mmin_j\ge mmin_i 一定成立。所以柿子就是：
mmin_i+sum_i+sum_j\le s,j\in[mid+1,p]
$i$ 此时已经确定了，二分一下 $j$ 就行了。
这里追求效率可以将第一次二分改为双指针扫描。
## code
```cpp
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
#define X first
#define Y second
int mod;
const int MAXN=2e5+10;
int n;ll s;
ll a[MAXN];
int b[MAXN];
ll mmin[MAXN],sum[MAXN];
ll ans=0;
void solve(int l,int r)
{
if(l==r)return ans+=a[l]+b[r]<=s,void();
int mid=(l+r)>>1;
solve(l,mid),solve(mid+1,r);
mmin[mid+1]=a[mid+1],sum[mid+1]=b[mid+1];
for(int i=mid+2;i<=r;i++)mmin[i]=min(mmin[i-1],a[i]);
for(int i=mid+2;i<=r;i++)sum[i]=sum[i-1]+b[i];
mmin[mid]=a[mid],sum[mid]=b[mid];
for(int i=mid-1;i>=l;i--)mmin[i]=min(mmin[i+1],a[i]);
for(int i=mid-1;i>=l;i--)sum[i]=sum[i+1]+b[i];
vector<ll>L,R;
for(int i=mid+1;i<=r;i++) R.push_back(sum[i]);
for(int i=mid;i>=l;i--) L.push_back(sum[i]);
int i=l,j=r;
while(i<=mid||j>mid)
{
if(j<=mid||mmin[i]<=mmin[j]&&i<=mid)
{
int p=upper_bound(R.begin(),R.begin()+j-mid,s-mmin[i]-sum[i])-R.begin();
ans+=p;
i++;
}
else
{
int p=upper_bound(L.begin(),L.begin()+mid-i+1,s-mmin[j]-sum[j])-L.begin();
ans+=p;
j--;
}
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>s;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
solve(1,n);cout<<ans<<'\n';
return 0;
}
```