Segment Tree Beats 学习笔记

模板题：
hdu5306
维护最大值，最大值个数，次大值，区间和即可。
区间更新k的时候，若当且节点最大值小于k则直接返回，k小于最大值且大于次大值时则可以直接更新区间和和最大值，否则继续递归左右儿子，注意要把信息更新到当前节点的所有祖先节点。
节点信息向下传递的时候，祖先的历史最小值显然大于等于当前的次小值，所以只要祖先的历史最小值小于当前节点的最大值，就要把当前节点更新一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
LL t[N<<2];
int mx[N<<2],cm[N<<2],cnm[N<<2],n,a[N];
void push_up(int o,int l,int r){
  t[o]=t[ls]+t[rs];
  if(mx[ls]>mx[rs]){
    mx[o]=mx[ls];
    cnm[o]=cnm[ls];
    cm[o]=max(cm[ls],mx[rs]);
  }else if(mx[ls]<mx[rs]){
    mx[o]=mx[rs];
    cnm[o]=cnm[rs];
    cm[o]=max(cm[rs],mx[ls]);
  }else{
    mx[o]=mx[rs];
    cnm[o]=cnm[ls]+cnm[rs];
    cm[o]=max(cm[ls],cm[rs]);
  }
}
void build(int o,int l,int r){
  if(l==r){
    t[o]=mx[o]=a[l];
    cnm[o]=1;
    cm[o]=-1;
    return ;
  }
  build(ls,l,mid);
  build(rs,mid+1,r);
  push_up(o,l,r);
}
void turn_min(int o,int l,int r,int d){
  t[o]-=1ll*cnm[o]*(mx[o]-d);
  mx[o]=d;
}
void push_down(int o,int l,int r){
  if(mx[o]<mx[ls]&&mx[o]>cm[ls])turn_min(ls,l,mid,mx[o]);
  if(mx[o]<mx[rs]&&mx[o]>cm[rs])turn_min(rs,mid+1,r,mx[o]);
}
void up(int o,int l,int r,int x,int y,int d){
  if(mx[o]<=d)return ;
  if(l>=x&&r<=y){
    if(cm[o]<d){
      turn_min(o,l,r,d);
      return ;
    }
  }
  push_down(o,l,r);
  if(x<=mid)up(ls,l,mid,x,y,d);
  if(y>mid)up(rs,mid+1,r,x,y,d);
  push_up(o,l,r);
}
int _;
LL get_sum(int o,int l,int r,int x,int y){
  if(l>=x&&r<=y)return t[o];
  LL ans=0;
  push_down(o,l,r);
  if(x<=mid)ans+=get_sum(ls,l,mid,x,y);
  if(y>mid)ans+=get_sum(rs,mid+1,r,x,y);
  return ans;
}
int get_max(int o,int l,int r,int x,int y){
  if(l>=x&&r<=y)return mx[o];
  int ans=0;
  push_down(o,l,r);
  if(x<=mid)ans=max(ans,get_max(ls,l,mid,x,y));
  if(y>mid)ans=max(ans,get_max(rs,mid+1,r,x,y));
  return ans;
}
int main() {
  for(scanf("%d",&_);_;_--){
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,1,n);
    for(;q;q--){
      int o,l,r;
      scanf("%d%d%d",&o,&l,&r);
      if(o==0){
        int k;
        scanf("%d",&k);
        up(1,1,n,l,r,k);
      }else if(o==1){
        printf("%d\n",get_max(1,1,n,l,r));
      }else{
        printf("%lld\n",get_sum(1,1,n,l,r));
      }
    }
  }
  return 0;
}

bzoj4695
6个操作。
需要注意的是，如果最小值和最大值相等的话，就把次小值和次大值都重置一下，变成inf,-inf。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,a[N],q;
inline int read(){
  int f=1,x=0;char ch;
  do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
  do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
  return f*x;
}
int mx[N<<2],mn[N<<2];//最大 最小
int laz[N<<2];//区间加
int cn[N<<2],cm[N<<2];//次大 次小
int cmx[N<<2],cmn[N<<2];//最大值个数 最小值个数
LL t[N<<2];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
void push_up(int o,int l,int  r){
  t[o]=t[ls]+t[rs];
  if(mx[ls]>mx[rs]){
    mx[o]=mx[ls];
    cmx[o]=cmx[ls];
    cm[o]=max(cm[ls],mx[rs]);
  }else if(mx[ls]<mx[rs]){
    mx[o]=mx[rs];
    cmx[o]=cmx[rs];
    cm[o]=max(cm[rs],mx[ls]);
  }else{
    mx[o]=mx[rs];
    cmx[o]=cmx[ls]+cmx[rs];
    cm[o]=max(cm[ls],cm[rs]);
  }
  if(mn[ls]<mn[rs]){
    mn[o]=mn[ls];
    cmn[o]=cmn[ls];
    cn[o]=min(cn[ls],mn[rs]);
  }else if(mn[ls]>mn[rs]){
    mn[o]=mn[rs];
    cmn[o]=cmn[rs];
    cn[o]=min(cn[rs],mn[ls]);
  }else{
    mn[o]=mn[rs];
    cmn[o]=cmn[ls]+cmn[rs];
    cn[o]=min(cn[ls],cn[rs]);
  }
  return ;
}
void build(int o,int l,int r){
  if(l==r){
    mx[o]=mn[o]=a[l];
    laz[o]=0;
    cm[o]=-1e9;cn[o]=1e9;
    cmx[o]=cmn[o]=1;
    t[o]=a[l];
    return ;
  }
  build(ls,l,mid);
  build(rs,mid+1,r);
  push_up(o,l,r);
}
void push_tag(int o,int l,int r,LL d){
  laz[o]+=d;t[o]+=1ll*d*(r-l+1);
  mx[o]+=d;mn[o]+=d;
  cn[o]+=d;cm[o]+=d;
  return ;
}
void turn_max(int o,int l,int r,int d){
  t[o]+=1ll*cmn[o]*(d-mn[o]);
  mn[o]=d;mx[o]=max(d,mx[o]);
  if(mn[o]==mx[o]){
    t[o]=1ll*(r-l+1)*d;
    cmn[o]=cmx[o]=r-l+1;
    cm[o]=-1e9;cn[o]=1e9;
  }else cm[o]=max(cm[o],d);
}
void turn_min(int  o,int l,int r,int d){
  t[o]-=1ll*cmx[o]*(mx[o]-d);
  mx[o]=d;mn[o]=min(mn[o],d);
  if(mn[o]==mx[o]){
    t[o]=1ll*(r-l+1)*d;
    cmn[o]=cmx[o]=r-l+1;
    cm[o]=-1e9;cn[o]=1e9;
  }else{
    cn[o]=min(cn[o],d);
  }
}
void push_down(int o,int l,int r){
  if(laz[o]){
    push_tag(ls,l,mid,laz[o]);
    push_tag(rs,mid+1,r,laz[o]);
    laz[o]=0;
  }
  if(mx[ls]>mx[o])turn_min(ls,l,mid,mx[o]);
  if(mx[rs]>mx[o])turn_min(rs,mid+1,r,mx[o]);
  if(mn[ls]<mn[o])turn_max(ls,l,mid,mn[o]);
  if(mn[rs]<mn[o])turn_max(rs,mid+1,r,mn[o]);
}
void add(int o,int l,int r,int x,int y,LL d){
  if(l>=x&&r<=y){
    push_tag(o,l,r,d);
    return ;
  }
  push_down(o,l,r);
  if(x<=mid)add(ls,l,mid,x,y,d);
  if(y>mid)add(rs,mid+1,r,x,y,d);
  push_up(o,l,r);
}
void bemax(int o,int l,int r,int x,int y,LL d){
  if(d<=mn[o])return ;
  if(l>=x&&r<=y){
      if(d<cn[o]){
        turn_max(o,l,r,d);
        return ;
      }
  }
  push_down(o,l,r);
  if(x<=mid)bemax(ls,l,mid,x,y,d);
  if(y>mid)bemax(rs,mid+1,r,x,y,d);
  push_up(o,l,r);
}
void bemin(int o,int l,int r,int x,int y,LL d){
  if(mx[o]<=d)return ;
  if(l>=x&&r<=y){
    if(cm[o]<d){
      turn_min(o,l,r,d);
      return ;
    }
  }
  push_down(o,l,r);
  if(x<=mid)bemin(ls,l,mid,x,y,d);
  if(y>mid)bemin(rs,mid+1,r,x,y,d);
  push_up(o,l,r);
}
LL getsum(int o,int l,int r,int x,int y){
  if(l>=x&&r<=y)return t[o];
  LL ans=0;
  push_down(o,l,r);
  if(x<=mid)ans+=getsum(ls,l,mid,x,y);
  if(y>mid)ans+=getsum(rs,mid+1,r,x,y);
  return ans;
}
int getmax(int o,int l,int r,int x,int y){
  if(l>=x&&r<=y)return mx[o];
  int ans=-1e9;
  push_down(o,l,r);
  if(x<=mid)ans=max(getmax(ls,l,mid,x,y),ans);
  if(y>mid)ans=max(getmax(rs,mid+1,r,x,y),ans);
  return ans;
}
int getmin(int o,int l,int r,int x,int y){
  if(l>=x&&r<=y)return mn[o];
  int ans=1e9;
  push_down(o,l,r);
  if(x<=mid)ans=min(getmin(ls,l,mid,x,y),ans);
  if(y>mid)ans=min(getmin(rs,mid+1,r,x,y),ans);
  return ans;
}
int main() {
  n=read();
  for(int i=1;i<=n;i++)a[i]=read();
  build(1,1,n);
  q=read();
  for(int i=1;i<=q;i++){
    int o,l,r,x;
    o=read();l=read();r=read();
    if(o==1){
      x=read();
      add(1,1,n,l,r,x);
    }else if(o==2){
      x=read();
      bemax(1,1,n,l,r,x);
    }else if(o==3){
      x=read();
      bemin(1,1,n,l,r,x);
    }else if(o==4){
      printf("%lld\n",getsum(1,1,n,l,r));
    }else if(o==5){
      printf("%d\n",getmax(1,1,n,l,r));
    }else {
      printf("%d\n",getmin(1,1,n,l,r));
    }
  }
  return 0;
}