这题目很有意思，让我学会了树状数组的差分，更加深刻理解了树状数组
树状数组的差分写法
void add(int x,int k)
{
for (int i = x;i <= n;i += lowbit(i)) c[i] += k;
} int sum(int x)
{
int ans = ;
for (int i = x;i > ;i -= lowbit(i)) ans += c[i];
return ans;
} {
add(l,x);
add(r+,-x);
int zhi=sum(l)//就是a[l]的数值，前缀和。
}
题意：
很简单，输入n m
给n个a[i]，代表每栋楼要造的高度
接下来m个操作
输入op
当op等于1的时候输入l,r,val
区间l，r之间增加val高度
当op等于2的时候输入l，r
求区间l，r，最小的工作时长（这个我语文不好，举例吧 1 3 2需要3个工作时长 1 3 2 5需要6个工作时长，1 3 2 5 -> 0 2 1 4 -> 0 1 0 3 -> 0 0 0 3 -> 0 0 0 2 -> 0 0 0 1 -> 0 0 0 0）
思路：
差分树状数组
a[i]原本的高度 b[i]=a[i]-a[i-1]（前缀和） c[i]=b[i]>0?b[i]:0（后者比前者小，需要多出的工作时长）
所以答案就是 a[l]+(c[i]求和（l<i<r）)
增加的val高度，a[l]用一个前缀和树状数组 add（val，l）add（-val，r+1）
维护c[i]的树状数组特殊判断（tql这里的思考判断，做题的时候就是这里没处理好，于是代码写不出来）
其实就是把每个建筑的递增高峰写出来，如果前者比后者大，后者那个位置就是0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<stdio.h>
#include<map>
#include<set>
#define ll long long
#define lowbit(x) x&-x
using namespace std;
const int maxn=1e5+;
int n,m,a[maxn],b[maxn];
ll cnt[maxn],cn[maxn];
void add1(int zhi,int x){
for(int i=x;i<=n;i+=lowbit(i)){
cn[i]+=(ll)zhi;
}
}
void add2(int zhi,int x){
for(int i=x;i<=n;i+=lowbit(i)){
cnt[i]+=(ll)zhi;
}
}
ll geshu1(int x){
if(x==){return ;}
ll sum=;
for(int i=x;i>;i-=lowbit(i)){
sum+=cn[i];
}
return sum;
}
ll geshu2(int x){
if(x==){return ;}
ll sum=;
for(int i=x;i>;i-=lowbit(i)){
sum+=cnt[i];
}
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
cnt[i]=,cn[i]=;
}
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i]-a[i-];int tt=(b[i]>?b[i]:);
add1(b[i],i);
add2(tt,i);
}
for(int i=;i<=m;i++){
int op;
scanf("%d",&op);
if(op==){
int l,r,val;
scanf("%d%d%d",&l,&r,&val);
add1(val,l);add1(-val,r+);//差分
if(b[l]<){
int tt=-b[l];
if(tt<val){
add2(val-tt,l);
}
}
else{
add2(val,l);
}
b[l]+=val;
if(b[r+]>=){
int tt=min(b[r+],val);
add2(-tt,r+);
}
b[r+]-=val;
}
else{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",geshu2(r)-geshu2(l)+geshu1(l));
}
}
}
return ;
}
看了扩展
区间修改，单点输出
单点修改，区间输出
到区间修改和输出
tql（看了Top_Spirit博客）
数组cnt[n] 用来维护a[i]
a[1]+a[2]+...+a[n]= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])
= n*c[1] + (n-1)*c[2] +... +c[n]
= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n])
再维护一个数组cnt2[n]，cnt2[i] = (i-1)*c[i]
a[1]+a[2]+...+a[n]=n*geshu1(cnt,n) - geshu2(cnt2,n)
add1( l , val);
add1(r + , -val);
add2( l , (l - ) * val);
add2 (r + , r* (-z));
