《Segment tree Beats!》，反正我不会

1 #include
     
        2 #define pa pair
      
         3 #define CLR(a,x) memset(a,x,sizeof(a))  4 using namespace std;  5 typedef long long ll;  6 const int maxn=4e5+10;  7 const ll inf=1e15+1;  8   9 inline ll rd(){ 10     ll x=0;char c=getchar();int neg=1; 11     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();} 12     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 13     return x*neg; 14 } 15  16 ll a[maxn]; 17 int N,M; 18 ll sum[maxn<<2],mn[maxn<<2][2],se[maxn<<2],laz[maxn<<2]; 19  20 inline void update(int p){ 21     sum[p]=sum[p<<1]+sum[p<<1|1]; 22     if(mn[p<<1][0]==mn[p<<1|1][0]){ 23         mn[p][0]=mn[p<<1][0],mn[p][1]=mn[p<<1][1]+mn[p<<1|1][1]; 24         se[p]=min(se[p<<1],se[p<<1|1]); 25     } 26     else if(mn[p<<1][0]
       
        <<1|1][0]){ 27         mn[p][0]=mn[p<<1][0],mn[p][1]=mn[p<<1][1]; 28         se[p]=min(se[p<<1],mn[p<<1|1][0]); 29     } 30     else if(mn[p<<1][0]>mn[p<<1|1][0]){ 31         mn[p][0]=mn[p<<1|1][0],mn[p][1]=mn[p<<1|1][1]; 32         se[p]=min(se[p<<1|1],mn[p<<1][0]); 33     } 34 } 35  36 void pushdown(int p){ 37     if(!laz[p]) return; 38     ll x=laz[p];laz[p]=0; 39     if(x<=mn[p][0]) return; 40     laz[p<<1]=max(x,laz[p<<1]); 41     laz[p<<1|1]=max(x,laz[p<<1|1]); 42     if(x
        
         >1; 60         if(x<=m) change(p<<1,l,m,x,y,z); 61         else pushdown(p<<1); 62         if(y>=m+1) change(p<<1|1,m+1,r,x,y,z); 63         else pushdown(p<<1|1); 64         update(p); 65     } 66 } 67  68 void build(int p,int l,int r){ 69     if(l==r){ 70         mn[p][0]=sum[p]=a[l]; 71         mn[p][1]=1,se[p]=inf; 72     }else{ 73         int m=l+r>>1; 74         build(p<<1,l,m);build(p<<1|1,m+1,r); 75         update(p); 76     } 77 } 78  79 ll query(int p,int l,int r,int x,int y){ 80     pushdown(p); 81     if(x<=l&&r<=y) return sum[p]; 82     int m=l+r>>1;ll re=0; 83     if(x<=m) re=query(p<<1,l,m,x,y); 84     if(y>=m+1) re+=query(p<<1|1,m+1,r,x,y); 85     return re; 86 } 87  88 int main(){ 89     //freopen("","r",stdin); 90     int i; 91     N=rd(),M=rd(); 92     for(i=1;i<=N;i++) 93         a[i]=rd(); 94     build(1,1,N); 95     for(i=1;i<=M;i++){ 96         ll a=rd(),b=rd(),c=rd(); 97         if(!a) printf("%lld\n",query(1,1,N,b,c)); 98         else change(1,1,N,b,c,a); 99     }100     return 0;101 }