Codeforces Round 546
E
题目HERE
题目大意
数组a[n], 其中2<=n<=100'000,-1'000'000'000<=a[i]<=1'000'000'000
a[i+1]-a[i] >= k[i] ,其中-1'000'000<=k[i]<=1'000'000
q个操作1<=q<=100'000
操作类型1，对a[i] 增加x，其中0<=x<=1'000'000,如果操作后无法满足上面与k的关系，则调整a[i+1]=a[i]+k[i] 直到所有 的值都满足
操作类型2，求sum of a[l->r]
解法
一眼就是个线段树，但是比以往遇到的线段树，要难维护一些，注意一下需要维护的状态
limiaomiao的解法
[l->r]实际的 差: der[l->r]的差前缀和的和 :sum[l->r] = (der[l])+(der[l]+der[l+1])+...+(der[l]+...+der[r])
build tree
der[o]= der[o<<1] + der[o<<1 | 1] 记录的是a[r]-a[l]的实际差值
sum[o]= sum[o<<1] + sum[o<<1 | 1] + der[o<<1] * length of (o<<1 | 1)
add val
对a[i]增加x的操作
实际是对 a[i-1]和a[i]的差 增加，以及 对a[i]和a[i+1]的差 的减少x
这样，线段树上操作，[这样感觉会被卡，但看limiaomiao的代码 有个神奇操作，加了一个set来记录，哪些的差值和k不同] 这样每次改变值，最多能产生1个 新的和k不同的差，那么每次的时间消耗=1+消耗的不同于k的值
所以总时间 = 操作数+ 总消耗 <= 操作数+ 初始不同的个数+过程中产生的不同的个数，是线性关系
询问
ans_sum[l->r]
=a[l]+...+a[r]
= a[l]*(r-l+1)+ ((der[l])+(der[l]+der[l+1])+...+(der[l]+...+der[r]))
= getval(a[l])×(r-l+1)+query_sum(l->r)
我这里的思路
注意到实际维护的是a[i+1]-a[i]-k[i] >= 0
那么线段树，可以是在数组b[i]=a[i+1]-a[i]-k[i]上面建立
b[i]所以要全非负
build tree
der[o]= der[o<<1] + der[o<<1 | 1] 记录的是a[l->r]的差值再减去这一段k的差值保证非负
sum[o]= sum[o<<1] + sum[o<<1 | 1] + der[o<<1] * length of (o<<1 | 1)
add val
同样 对a[i]增加x的操作
实际是对 a[i-1]和a[i]的差 增加，以及 对a[i]和a[i+1]的差 的减少x
注意到这样的话，增加x的部分就可以先lazy掉，
在减少的部分，如果 der[l->r] < x 那么这一段整个der都是0，可以lazy掉，保证了每次的log级别的操作
除此以外，每次可能访问的时候，把lazy的部分向下分发一下
询问
ans_sum[l->r]
=a[l]+...+a[r]
= a[l]*(r-l+1)+ ((der[l]+k[l])+(der[l]+k[l]+der[l+1]+k[l+1])+...+(der[l]+k[l]+...+der[r]+k[r]))
= getval(a[l])×(r-l+1)+query_sum(l->r)+sum_der_k(l->r)
总结
相比之下 我这样写，线段树的lazytag的多两个lazytag,而且 对于k也要维护一个sum的线段树,更难写