链接： :井底之蛙
题意：
n面墙按逆时针顺序编号 ，有两种操作
- 每次把从 a - b （逆时针）编号的墙的高度减少 h ，如果当前高度小于 h 则变成 0 ；
- 求 L- R 剩余墙的高度之和 。
思路：
- 一开始想的维护一个最大值和最小值，在更新区间时 ，如果当前最小值大于 h , 就用 lazy 标记更新区间 。如果 最大值小于 h ， 把当前区间的值变为 0 。如果最大值为 0 ，直接返回。虽然这样会降低一些复杂度，但还是会 T .对于一些极限数据 如
0 , 1e9 ,0 ,1e9 ,0 1e9每次对区间内的数 - 1，每次更新都会访问所有的节点，然后就 T 了 。 - 所以可以再维护一下，区间内 大于 0 的数的个数，把它当成区间长度，这样下次更新这个区间的时候就不会把 0 也给减少了 ， 同时如果这个这个区间全部变为 0 了，可以把最小值设置成 INF, 区间长度设置为 0 ， 这样可以使它满足 最小值 大于 h ,不会继续向下递归，同时区间长度为 0 也不会产生贡献 .
- 主要的操作就是维护了区间内大于 0 的数的个数 ， 直接不管等于0 的位置 ，降低了复杂度。
代码：
#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=4e6+7;
ll n,q,op;
ll sum[maxn],ma[maxn],mi[maxn],la[maxn],siz[maxn];
void pushup(ll rt){
sum[rt] = sum [rt<<1] + sum[rt << 1 | 1];ma[rt] = max(ma[rt<<1],ma[rt<<1|1]);mi[rt] = min(mi[rt<<1],mi[rt<<1|1]);siz[rt] = siz[rt<<1] + siz[rt<<1|1];
}
void pushdown(ll l , ll r ,ll rt){
ll mid = ( l + r ) / 2;if(la[rt] == 0) return ;la[rt << 1] += la[rt];la[rt << 1 | 1] += la[rt];sum[rt << 1] -= la[rt] * siz[rt<<1];sum[rt << 1 | 1] -= la[rt] * siz[rt<<1|1];ma[rt<<1] -= la[rt];mi[rt<<1] -= la[rt];ma[rt<<1|1] -= la[rt];mi[rt<<1|1] -= la[rt];la[rt] = 0;
}
void build(ll l,ll r,ll rt){
if(l == r) {
scanf("%lld",&sum[rt]);ma[rt] = mi[rt] = sum[rt];siz[rt] = (sum[rt] > 0);return ;}ll mid = (l + r) / 2;build(l , mid , rt <<1);build(mid + 1,r,rt<<1|1);pushup(rt);
}
void update(int L , int R ,ll h ,ll l,ll r,ll rt){
if(sum[rt] == 0) return ;if(ma[rt] <= h && L <= l && R >= r){
sum[rt] = ma[rt] = siz[rt] = 0;mi[rt] = 1e9;return ;}if(L <= l && R >= r && mi[rt] >= h){
sum[rt] -= siz[rt] * h;ma[rt] -= h;mi[rt] -= h;la[rt] += h;return ;}pushdown(l,r,rt);int mid = (l + r) / 2;if(L <= mid) update(L,R,h,l,mid,rt << 1);if(R > mid) update(L,R,h,mid + 1,r,rt<<1|1);pushup(rt);
}
ll query(int L, int R, int l, int r, int rt){
if(sum[rt] == 0) return 0;if(L <= l && R >= r){
return sum[rt];}pushdown(l,r,rt);int mid = (l + r) / 2;ll s = 0;if(L <= mid) s += query(L,R,l,mid,rt<<1);if(R > mid) s += query(L,R,mid+1,r,rt<<1|1);return s;}
int main(){
scanf("%lld%lld",&n,&q);build(1,n,1);while(q--){
ll l,r;ll h;scanf("%lld",&op);if(op == 1){
scanf("%lld%lld",&l,&r);printf ("%lld\n",query(l,r,1,n,1));}if(op == 2){
scanf("%lld%lld%lld",&l,&r,&h);if(r >= l) update(l,r,h,1,n,1);else{
update(l,n,h,1,n,1);update(1,r,h,1,n,1);}}}
}