题意：

　　给定一个长度为 N序列，编号从1 到 N。要求支持下面几种操作：

　　1.给一个区间[L,R] 加上一个数x 

　　2.把一个区间[L,R] 里小于x 的数变成x 

　　3.把一个区间[L,R] 里大于x 的数变成x 

　　4.求区间[L,R] 的和

　　5.求区间[L,R] 的最大值

　　6.求区间[L,R] 的最小值

 

分析：

　　你听说过Segment Tree Beats么？

　　快去看一看吧。这题居然才只有六个操作，真的是重口难调啊。

　　思想还是不难的，这里就不粘课件了。

　　由于这题拥有着比较玄学的空间限制和比较玄学的数据范围，所以可能需要试探很多遍才能不MLE。

　　（如果你是指针线段树我也没啥可说的）

　　代码是我修改抄袭一位大神的，予以美化（好像更难读了），以便于非指针用户食用。

代码：

1 #include
      
         2 #define ll long long  3 using namespace std;  4 const int N=3.7e5+5,inf=1e9;  5 struct node{  6     int l,r,ls,rs,mnc,mxc;//标号为1代表最值  7     ll mn1,mn2,mx1,mx2;//，为2代表次值   8     ll lmn,lmx,lad,s;//c代表的是count数量，不是次  9 }t[N<<2];int cnt=0,rt,n,m,x; 10 char readchar(){ 11     static char buf[100000],*l=buf,*r=buf; 12     if(l==r) r=(l=buf)+fread(buf,1,100000,stdin); 13     if(l==r) return EOF;return *l++;} 14 int read(){ 15     int x=0,f=1;char ch=readchar(); 16     while(ch<'0'||ch>'9'){
    if(ch=='-') f=-f;ch=readchar();} 17     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=readchar();}; 18     return x*f; 19 } void pushup(int cur){ 20     int ls=t[cur].ls,rs=t[cur].rs; 21     t[cur].s=t[ls].s+t[rs].s; 22     if(t[ls].mn1
       
        t[rs].mn1) 27         t[cur].mn1=t[rs].mn1, 28         t[cur].mnc=t[rs].mnc, 29         t[cur].mn2=min(t[rs].mn2,t[ls].mn1); 30     else t[cur].mn1=t[ls].mn1, 31         t[cur].mnc=t[ls].mnc+t[rs].mnc, 32         t[cur].mn2=min(t[ls].mn2,t[rs].mn2); 33     if(t[ls].mx1>t[rs].mx1) 34         t[cur].mx1=t[ls].mx1, 35         t[cur].mxc=t[ls].mxc, 36         t[cur].mx2=max(t[ls].mx2,t[rs].mx1); 37     else if(t[ls].mx1
        
         =t[rs].mn1) 68         admn(rs,t[cur].lmn);t[cur].lmn=0; 69     } if(t[cur].lmx){ 70         if(t[ls].mx1>=t[rs].mx1) 71         admx(ls,t[cur].lmx); 72         if(t[ls].mx1<=t[rs].mx1) 73         admx(rs,t[cur].lmx);t[cur].lmx=0; 74     } return ; 75 } void build(int l,int r,int cur){ 76     t[cur].l=l,t[cur].r=r; 77     if(l==r){ t[cur].mxc=1; 78         t[cur].ls=t[cur].rs=-1;t[cur].mnc=1; 79         t[cur].lmn=t[cur].lmx=t[cur].lad=0; 80         t[cur].s=t[cur].mx1=t[cur].mn1=read(); 81         t[cur].mn2=inf;t[cur].mx2=-inf;return ; 82     } int mid=l+r>>1; 83     t[cur].ls=cnt++;t[cur].rs=cnt++; 84     build(l,mid,t[cur].ls); 85     build(mid+1,r,t[cur].rs); 86     pushup(cur);return ; 87 }  88 #define sum(x,y) x+y;  89 #define upd(fun,lm,req,tag)                     \ 90     void fun(int l,int r,int cur){              \ 91         if(lm) return ;                         \ 92         if(l<=t[cur].l&&t[cur].r<=r&&req)       \ 93         {tag;return ;} pushdown(cur);           \ 94         int mid=t[cur].l+t[cur].r>>1;           \ 95         if(l<=mid) fun(l,r,t[cur].ls);          \ 96         if(mid
         
          >1;           \105         if(r<=mid) return fun(l,r,ls);            \106         if(mid
          
           =x,t[cur].mn2>x,111 admn(cur,x-t[cur].mn1))112 upd(umx,t[cur].mx1<=x,t[cur].mx2