对于这样一类问题：

区间取min，区间求和。

N<=100000

要求O(nlogn)级别的算法

 

直观体会一下，区间取min，还要维护区间和

增加的长度很不好求。。。。

 

然鹅，

从前有一个来自杭州天水幼儿园的julao叫九条可怜

他发明了一个线段树的写法，

攻克了这个难题。

 

说起来很简单：

线段树维护区间最大值，区间严格次大值，和区间最大值出现次数

修改的时候，如果c大于mx，直接return

如果c小于mx而大于cmx，根据最大值的出现次数可以直接修改sum（注意必须是严格大于cmx，否则不能维护好严格次大值）

如果c小于等于cmx，那么暴力递归左右儿子，最终会用前两个更新，回溯来pushup一下

复杂度？

前两个O(1)就回溯了，不管。

第三个操作貌似有些暴力？

由于只有取max，所以

假如开始有O(N)个不同的值，那么每进行一次第三次操作，至少mx，和cmx要变得一样。值域减少1

那么，第三次操作最多进行O(n)次，每次均摊O(logn)

所以复杂度O(nlogn)

 

例题（以及一些具体操作）：

bzoj4695. 最假女选手

区间还要加？值域会改变，，，可以证明（就是说我不会证）复杂度是O(nlog^2n)

维护区间最大值，次大值，最大值出现次数，最小值同理。以及区间和，区间加标记

下放：

先下放区间加标记，现在儿子的情况大致和父亲一样了

区别在于，之前区间取min可能把最大值砍掉一些，但是没有在儿子中更新。

由于仅最大值小了一些，所以如果父亲的最大值在儿子的最大值和次大值之间，那么暴力再让儿子对父亲的最大值取个min（直接返回的，这个也是O(1)的）

第二种情况的更新时候：

可能造成最大值和最小值相同的情况，那么必然就是全部都相等了。特判一下，把次大值-inf，最大值inf（其实这个没有必要）

或者可能只有值域只有两个，那么次大值或者次小值也要尝试更新一下。其他值域的时候不影响。（这个必须有）

 

代码比较长：

#include
     
      #define reg register int#define il inline#define mid ((l+r)>>1)#define ls t[x].lson#define rs t[x].rson#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=6e5+5;const int inf=0x3f3f3f3f;int n,m;int a[N];struct node{    int mx,cmx,tmx;    int mi,cmi,tmi;    ll sum;    ll ad;    int lson,rson;}t[2*N];int tot;void pushup(int x){    t[x].sum=t[ls].sum+t[rs].sum;    if(t[ls].mx>t[rs].mx){        t[x].mx=t[ls].mx,t[x].tmx=t[ls].tmx;t[x].cmx=max(t[ls].cmx,t[rs].mx);    }else if(t[ls].mx
      
       t[rs].mi){        t[x].mi=t[rs].mi,t[x].tmi=t[rs].tmi;t[x].cmi=min(t[rs].cmi,t[ls].mi);    }else{        t[x].mi=t[ls].mi;t[x].tmi=t[ls].tmi+t[rs].tmi;t[x].cmi=min(t[rs].cmi,t[ls].cmi);    }}void addmax(int x,int l,int r,int c){
   //qu max    t[x].sum+=(ll)t[x].tmi*(c-t[x].mi);    t[x].mi=c;    t[x].mx=max(t[x].mx,c);    if(t[x].mi==t[x].mx){        t[x].sum=((ll)r-l+1)*c;t[x].tmi=t[x].tmx=r-l+1;t[x].cmi=inf;t[x].cmx=-inf;    }else t[x].cmx=max(t[x].cmx,c);}void addmin(int x,int l,int r,int c){    t[x].sum+=(ll)t[x].tmx*(c-t[x].mx);    t[x].mx=c;    t[x].mi=min(t[x].mi,c);    if(t[x].mi==t[x].mx){        t[x].sum=((ll)r-l+1)*c;t[x].tmi=t[x].tmx=r-l+1;t[x].cmi=inf;t[x].cmx=-inf;    }else t[x].cmi=min(t[x].cmi,c);}void build(int x,int l,int r){    if(l==r){        t[x].mx=t[x].mi=a[l];        t[x].cmx=-inf;t[x].cmi=inf;        t[x].tmx=t[x].tmi=1;        t[x].sum=a[l];return;    }    ls=++tot;rs=++tot;    build(ls,l,mid);build(rs,mid+1,r);    pushup(x);}void getsum(int x,int l,int r,int c){    t[x].ad+=c;t[x].sum+=(r-l+1)*c;    t[x].mi+=c;t[x].cmi+=c;    t[x].mx+=c;t[x].cmx+=c;}void pushdown(int x,int l,int r){    if(t[x].ad){        getsum(ls,l,mid,t[x].ad);        getsum(rs,mid+1,r,t[x].ad);        t[x].ad=0;    }    if(t[ls].mx>t[x].mx&&t[ls].cmx
       
        t[x].mx&&t[rs].cmx
        
         t[x].mi) addmax(ls,l,mid,t[x].mi);    if(t[rs].mi
         
          t[x].mi) addmax(rs,mid+1,r,t[x].mi);}void chanmx(int x,int l,int r,int L,int R,int c){    //cout<
          
           <<" "<
           
            <<" "<
            
             <<" "<
             
              <<" "<
              
               <<" "<
               
                <<" "<
                
                 <
                 
                  =c) return; if(t[x].cmi>c) { addmax(x,l,r,c);return; } pushdown(x,l,r); chanmx(ls,l,mid,L,R,c); chanmx(rs,mid+1,r,L,R,c); pushup(x); return; } pushdown(x,l,r); if(L<=mid) chanmx(ls,l,mid,L,R,c); if(mid
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

不亏是九老师自己出的题