题目：http://www.lydsy.com/JudgeOnline/problem.php?id=4127

不算难的样子，才见过此类模型。

首先可以发现每次修改只增不减，那么这$O(n)$的负数最多只会有$n$次由负变正。

所以对于每一次由负变正我们暴力在线段树上维护，每一次由负变正在线段树上会经过$O(logn)$层。

效率$O(logn)$。

其他的维护一下区间负数的个数什么的就可以搞了。

一遍AC爽

1 #include 
      
         2 #include 
       
          3 #include 
        
           4   5 #define l(x) ch[x][0]  6 #define r(x) ch[x][1]  7 #define N 100010  8 #define LL long long  9 #define INF 0x3f3f3f3f3f3f3f3fLL 10  11 using namespace std; 12  13 struct edge{ 14     int x,to; 15 }E[N<<1]; 16  17 int n,m,totE; 18 int g[N]; 19  20 inline int Abs(int x){ 21     if(x<0) return -x; 22     return x; 23 } 24  25 inline void ade(int x,int y){ 26     E[++totE]=(edge){y,g[x]}; g[x]=totE; 27 } 28  29 namespace Segtree{ 30     int tot; 31     int ch[N<<1][2]; 32     int totf[N<<1],siz[N<<1]; 33     LL maxf[N<<1],sumv[N<<1],addv[N<<1]; 34  35     void push(int x){ 36         if(!l(x)||!addv[x]) return; 37         addv[l(x)]+=addv[x]; 38         sumv[l(x)]+=addv[x]*(LL)(siz[l(x)]-2*totf[l(x)]); 39         maxf[l(x)]+=addv[x]; 40         addv[r(x)]+=addv[x]; 41         sumv[r(x)]+=addv[x]*(LL)(siz[r(x)]-2*totf[r(x)]); 42         maxf[r(x)]+=addv[x]; 43         addv[x]=0; 44     } 45      46     void up(int x){ 47         if(!l(x)) return; 48         sumv[x]=sumv[l(x)]+sumv[r(x)]; 49         maxf[x]=max(maxf[l(x)],maxf[r(x)]); 50         totf[x]=totf[l(x)]+totf[r(x)]; 51     } 52      53     void change(int x,int l,int r,int ql,int qr,int qv){ 54         push(x); 55         if(ql<=l&&r<=qr&&maxf[x]+qv<0){ 56             addv[x]+=qv; 57             sumv[x]+=qv*(LL)(siz[x]-2*totf[x]); 58             maxf[x]+=qv; 59         } 60         else if(l==r){ 61             sumv[x]=qv-sumv[x]; 62             addv[x]=0; 63             maxf[x]=-INF; 64             totf[x]=0; 65         } 66         else{ 67             int mid=(l+r)>>1; 68             if(ql<=mid) change(l(x),l,mid,ql,qr,qv); 69             if(mid
         
          >1; 80         LL ans=0; 81         if(ql<=mid) ans+=ask(l(x),l,mid,ql,qr); 82         if(mid
          
           =0) maxf[x]= -INF; 94             else maxf[x]=src[l]; 95             totf[x]= (src[l]<0) ? 1:0; 96             return x; 97         } 98         int mid=(l+r)>>1; 99         l(x)=build(src,l,mid);100         r(x)=build(src,mid+1,r);101         up(x);102         return x;103     }104 }105 106 #define p E[i].x107 108 int tott;109 int L[N],a[N],fa[N],pos[N],c[N],d[N],siz[N],h[N],top[N];110 bool v[N];111 112 void dfs(int x){113     v[x]=1; siz[x]=1; h[x]=0;114     for(int i=g[x];i;i=E[i].to)115         if(!v[p]){116             fa[p]=x;117             d[p]=d[x]+1;118             dfs(p);119             siz[x]+=siz[p];120             if(siz[p]>siz[h[x]])121                 h[x]=p;122         }123 }124 125 void cut(int x,int ft){126     L[x]=++tott; c[tott]=a[x]; pos[tott]=x; top[x]=ft;127     if(h[x]) cut(h[x],ft);128     for(int i=g[x];i;i=E[i].to)129         if(p!=fa[x]&&p!=h[x])130             cut(p,p);131 }132 133 void change(int x,int y,int v){134     int f1=top[x],f2=top[y];135     while(f1!=f2){136         if(d[f1]
           
            L[y]) swap(x,y);141 Segtree::change(1,1,n,L[x],L[y],v);142 }143 144 LL ask(int x,int y){145 int f1=top[x],f2=top[y];146 LL ans=0;147 while(f1!=f2){148 if(d[f1]
            
             L[y]) swap(x,y);153 ans+=Segtree::ask(1,1,n,L[x],L[y]);154 return ans;155 }156 157 int main(){158 scanf("%d%d",&n,&m);159 for(int i=1;i<=n;i++){160 scanf("%d",&a[i]);161 }162 int cmd,x,y;163 for(int i=1;i