吉司机课件题。

区间min,区间最值，区间和。

如果用最大值和次大值能更新区间和那就更新打标记，否则暴力dfs。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define inf 0x3f3f3f3f  6 #define N 500005  7 #define LL long long  8 #define ls x<<1,l,mid  9 #define rs x<<1|1,mid+1,r 10 using namespace std; 11 int n,m; 12 int as[N]; 13 struct node 14 { 15     LL sum; 16     int mx,num,se; 17     int lazy; 18 }a[N*8]; 19 inline int read() 20 { 21     int p=0;char c=getchar(); 22     while(c<'0'||c>'9')c=getchar(); 23     while(c>='0'&&c<='9')p=p*10+c-'0',c=getchar(); 24     return p; 25 } 26 void push_up(int x) 27 { 28     int l=x<<1,r=x<<1|1; 29     a[x].mx=a[l].mx;a[x].num=a[l].num;a[x].se=a[l].se;a[x].sum=a[l].sum+a[r].sum; 30     if(a[r].mx==a[x].mx)a[x].num+=a[r].num,a[x].se=max(a[x].se,a[r].se); 31     else if(a[r].mx
         
          val) 45     { 46         a[l].sum-=1LL*a[l].num*(a[l].mx-val); 47         a[l].lazy=1;a[l].mx=val; 48     } 49     if(a[r].mx>val) 50     { 51         a[r].sum-=1LL*a[r].num*(a[r].mx-val); 52         a[r].lazy=1;a[r].mx=val; 53     } 54 } 55 void build(int x,int l,int r) 56 { 57     a[x].se=-1; 58     a[x].lazy=0; 59     if(l==r) 60     { 61         a[x].num=1; 62         a[x].mx=as[l]; 63         a[x].sum=as[l]; 64         return ; 65     } 66     int mid=(l+r)>>1; 67     build(ls); 68     build(rs); 69     push_up(x); 70 } 71 int qurmx(int x,int l,int r,int ll,int rr) 72 { 73     if(l>=ll&&r<=rr) 74     { 75         return a[x].mx; 76     } 77     if(a[x].lazy)push_down(x); 78     int mid=(l+r)>>1; 79     if(ll>mid)return qurmx(rs,ll,rr); 80     if(rr<=mid)return qurmx(ls,ll,rr); 81     return max(qurmx(ls,ll,rr),qurmx(rs,ll,rr)); 82 } 83 LL qursum(int x,int l,int r,int ll,int rr) 84 { 85     if(l>=ll&&r<=rr) 86     { 87         return a[x].sum; 88     } 89     if(a[x].lazy)push_down(x); 90     int mid=(l+r)>>1; 91     if(ll>mid)return qursum(rs,ll,rr); 92     if(rr<=mid)return qursum(ls,ll,rr); 93     return qursum(ls,ll,rr)+qursum(rs,ll,rr); 94 } 95 void gai(int x,int l,int r,int ll,int rr,int z) 96 { 97     if(z>=a[x].mx)return ; 98     if(l>=ll&&r<=rr) 99     {100         if(z>a[x].se)101         {102             a[x].lazy=1;103             a[x].sum-=1LL*a[x].num*(a[x].mx-z);104             a[x].mx=z;return ;105         }106     }107     if(a[x].lazy)push_down(x);108     int mid=(l+r)>>1;109     if(ll<=mid)gai(ls,ll,rr,z);110     if(rr>mid)gai(rs,ll,rr,z);111     push_up(x);112 }113 int main()114 {115     int cas;116     scanf("%d",&cas);117     while(cas--)118     {119         scanf("%d%d",&n,&m);120         for(int i=1;i<=n;i++)as[i]=read();121         build(1,1,n);int op,t1,t2,t3;122         for(int i=1;i<=m;i++)123         {124             op=read();125             if(op==0)126             {127                 t1=read();t2=read();t3=read();128                 gai(1,1,n,t1,t2,t3);129             }130             else if(op==1)131             {132                 t1=read();t2=read();133                 printf("%d\n",qurmx(1,1,n,t1,t2));134             }135             else136             {137                 t1=read();t2=read();138                 printf("%lld\n",qursum(1,1,n,t1,t2));139             }140         }141     }142     return 0;143 }