题解：P17746 「RSOI-1C」序列 / sequence
AI_god
·
·
题解
题解是写给自己看的，可能有点看不懂。
记录每个下标可以往后贡献的值，对于每个位置：
- 之前可用贡献总和 $\le a_i$。
那么这个位置需要补充 $\text{sum}-a_i$（$\text{sum}$ 见代码），并且记录这个差值为其可以往后贡献的值。
```
ll sum=query(L,i-1);
if(sum<=a[i]){
add(i,a[i]-sum);ans+=(a[i]-sum);
}
```
- 之前可用贡献总和 $>a_i$。
那么只能保留 $a_i$ 个贡献（这个位置至多加 $a_i$ 次），找到位置 $L$ 使得从 $L$ 开始的贡献刚好达到 $a_i$ 并且修改使得贡献刚好等于 $a_i$（这样就是选择了一段连续地区间 $L\sim i-1$，也就是最右边的区间，这样其产生的贡献可以最持久的贡献到后面）。
```
else{
while(L<i&&query(L,i-1)>=a[i]){
L++;
}L--;
add(L,a[i]-query(L,i-1));
}
```
树状数组/线段树维护。
## 完整代码：
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1000005;
ll n,k;
ll t1[N],t2[N],a[N];
ll w[N],tag[N],L=1,ans=0,zl=0;
void add(ll x,ll y){
if(x)for(int i=x;i<=n;i+=(i&(-1*i)))w[i]+=y;
}
ll query(ll l,ll r){
ll s2=0,s1=0;
if(r!=0)for(int i=r;i;i-=(i&(-1*i)))s2+=w[i];
if(l!=0)for(int i=l-1;i;i-=(i&(-1*i)))s1+=w[i];
return s2-s1;
}
int main(){
scanf("%lld %lld",&n,&k);
for(int i=1;i<=n;i++){scanf("%lld",&t1[i]);}
for(int i=1;i<=n;i++){scanf("%lld",&t2[i]);}
for(int i=1;i<=n;i++){
a[i]=t2[i]-t1[i];
if(a[i]<0){cout<<"-1\n";return 0;}
}
for(int i=1;i<=n;i++){
L=max(L,i-k+1);
ll sum=query(L,i-1);
if(sum<=a[i]){
add(i,a[i]-sum);ans+=(a[i]-sum);
}else{
while(L<i&&query(L,i-1)>=a[i]){
L++;
}L--;
add(L,a[i]-query(L,i-1));
}
}
cout<<ans<<endl;
return 0;
}
```