Gorgeous sequence

区间最值

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;

const int N=1000010;
struct node{
  int mx,mx1,l,r,cnt;                               //区间内最大值，区间内第2大值，左区间，右区间，区间内的最大值的个数
  long long sum;
  void sol(int x){
    if(x>=mx) return; //mx1 < x < mx
    sum-=(mx-x)*1ll*cnt;
    mx=x;
  }
}t[N*4];
int a[N],op,x,y,z,n,m,T;

void push_up(int k){
  t[k].cnt=0;
  t[k].sum=t[k*2].sum+t[k*2+1].sum;                //求和
  t[k].mx=max(t[k*2].mx,t[k*2+1].mx);              //区间最大值
  t[k].mx1=max(t[k*2].mx1,t[k*2+1].mx1);           //最大值
  if(t[k*2].mx==t[k].mx) t[k].cnt+=t[k*2].cnt;     //与子节点相同cnt+=1
  else t[k].mx1=max(t[k].mx1,t[k*2].mx);           //于字节点不相同更新mx1
  if(t[k*2+1].mx==t[k].mx) t[k].cnt+=t[k*2+1].cnt;
  else t[k].mx1=max(t[k].mx1,t[k*2+1].mx);
}
void push_down(int k){
  t[k*2].sol(t[k].mx);                             //左儿子更新sum
  t[k*2+1].sol(t[k].mx);                           //右儿子更新sum
}
void built(int k,int l,int r){
  t[k].l=l; t[k].r=r;                              //左右区间
  if(l==r){                                        //叶节点
    t[k].mx=t[k].sum=a[l];
    t[k].mx1=-1; t[k].cnt=1;
    return;
  }
  int mid=(l+r)>>1;
  built(k*2,l,mid);
  built(k*2+1,mid+1,r);
  push_up(k);
}
void modify(int k,int l,int r,int x){              //编号，左区间，右区间，替换值
  if(t[k].mx<=x) return;                           //节点小于等于插入值就返回
  if(t[k].l==l && t[k].r==r && t[k].mx1<x){        //全覆盖并且大于第2最值
    t[k].sol(x);                                   //更新sum
    return;
  }
  push_down(k);
  int mid=(t[k].l+t[k].r)>>1;
  if(l<=mid) modify(k*2,l,min(r,mid),x);
  if(r>mid) modify(k*2+1,max(l,mid+1),r,x);
  push_up(k);
}
int getmax(int k,int l,int r){
  if(t[k].l==l&&t[k].r==r) return t[k].mx;        //覆盖区间返回最大值
  push_down(k);
  int mid=(t[k].l+t[k].r)>>1;
  if(r<=mid) return getmax(k*2,l,r);              //剪枝：判断是否包含区间
  else if(l>mid) return getmax(k*2+1,l,r);
  return max(getmax(k*2,l,mid),getmax(k*2+1,mid+1,r));     //返回最大值
}
long long getsum(int k,int l,int r){              //类似getmax
  if(t[k].l==l&&t[k].r==r) return t[k].sum;
  push_down(k);
  int mid=(t[k].l+t[k].r)>>1;
  if(r<=mid) return getsum(k*2,l,r);
  else if(l>mid) return getsum(k*2+1,l,r);
  return getsum(k*2,l,mid)+getsum(k*2+1,mid+1,r);
}
int main(){
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&m);                          //数列长度，操作次数
    for(int i=1;i<=n;i++) scanf("%d",a+i);        //储存数列
    built(1,1,n);                                 //建树
    for(int i=1;i<=m;i++){
      scanf("%d%d%d",&op,&x,&y);
      if(op==0) {
        scanf("%d",&z);                           //与数列比较取最小值
        modify(1,x,y,z);
      }
      else if(op==1) printf("%d\n",getmax(1,x,y));
      else printf("%lld\n",getsum(1,x,y));
    }
  }
  return 0;
}

笔记：mx，mx1和cnt的标记操作方式很棒，修改的数值在mx与mx1之间就不需要再向下递归子节点，直接修改当前节点的sum数值