对于这样一类问题：
区间取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. 最假女选手
【bzoj4695】最假女选手
区间还要加？值域会改变，，，可以证明（就是说我不会证）复杂度是O(nlog^2n)
维护区间最大值，次大值，最大值出现次数，最小值同理。以及区间和，区间加标记
下放：
先下放区间加标记，现在儿子的情况大致和父亲一样了
区别在于，之前区间取min可能把最大值砍掉一些，但是没有在儿子中更新。
由于仅最大值小了一些，所以如果父亲的最大值在儿子的最大值和次大值之间，那么暴力再让儿子对父亲的最大值取个min（直接返回的，这个也是O(1)的）
第二种情况的更新时候：
可能造成最大值和最小值相同的情况，那么必然就是全部都相等了。特判一下，把次大值-inf，最大值inf（其实这个没有必要）
或者可能只有值域只有两个，那么次大值或者次小值也要尝试更新一下。其他值域的时候不影响。（这个必须有）
代码比较长：
#include<bits/stdc++.h>
#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=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=6e5+;
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[*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].mx){
t[x].mx=t[rs].mx,t[x].tmx=t[rs].tmx;t[x].cmx=max(t[rs].cmx,t[ls].mx);
}else{
t[x].mx=t[ls].mx;t[x].tmx=t[ls].tmx+t[rs].tmx;t[x].cmx=max(t[rs].cmx,t[ls].cmx);
}
if(t[ls].mi<t[rs].mi){
t[x].mi=t[ls].mi,t[x].tmi=t[ls].tmi;t[x].cmi=min(t[ls].cmi,t[rs].mi);
}else if(t[ls].mi>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+)*c;t[x].tmi=t[x].tmx=r-l+;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+)*c;t[x].tmi=t[x].tmx=r-l+;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=;
t[x].sum=a[l];return;
}
ls=++tot;rs=++tot;
build(ls,l,mid);build(rs,mid+,r);
pushup(x);
}
void getsum(int x,int l,int r,int c){
t[x].ad+=c;t[x].sum+=(r-l+)*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+,r,t[x].ad);
t[x].ad=;
}
if(t[ls].mx>t[x].mx&&t[ls].cmx<t[x].mx) addmin(ls,l,mid,t[x].mx);
if(t[rs].mx>t[x].mx&&t[rs].cmx<t[x].mx) addmin(rs,mid+,r,t[x].mx);
if(t[ls].mi<t[x].mi&&t[ls].cmi>t[x].mi) addmax(ls,l,mid,t[x].mi);
if(t[rs].mi<t[x].mi&&t[rs].cmi>t[x].mi) addmax(rs,mid+,r,t[x].mi);
}
void chanmx(int x,int l,int r,int L,int R,int c){
//cout<<x<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<c<<" "<<t[x].cmi<<endl;
if(L<=l&&r<=R){
if(t[x].mi>=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+,r,L,R,c);
pushup(x);
return;
}
pushdown(x,l,r);
if(L<=mid) chanmx(ls,l,mid,L,R,c);
if(mid<R) chanmx(rs,mid+,r,L,R,c);
pushup(x);
}
void chanmi(int x,int l,int r,int L,int R,int c){
if(L<=l&&r<=R){
if(t[x].mx<=c) return;
if(t[x].cmx<c) {
addmin(x,l,r,c);return;
}
pushdown(x,l,r);
chanmi(ls,l,mid,L,R,c);
chanmi(rs,mid+,r,L,R,c);
pushup(x);
return;
}
pushdown(x,l,r);
if(L<=mid) chanmi(ls,l,mid,L,R,c);
if(mid<R) chanmi(rs,mid+,r,L,R,c);
pushup(x);
}
void add(int x,int l,int r,int L,int R,int c){
if(L<=l&&r<=R){
getsum(x,l,r,c);
return;
}
pushdown(x,l,r);
if(L<=mid) add(ls,l,mid,L,R,c);
if(mid<R) add(rs,mid+,r,L,R,c);
pushup(x);
}
int qmax(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return t[x].mx;
}
pushdown(x,l,r);int ret=-inf;
if(L<=mid) ret=max(ret,qmax(ls,l,mid,L,R));
if(mid<R) ret=max(ret,qmax(rs,mid+,r,L,R));
return ret;
}
int qmin(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return t[x].mi;
}
pushdown(x,l,r);int ret=inf;
if(L<=mid) ret=min(ret,qmin(ls,l,mid,L,R));
if(mid<R) ret=min(ret,qmin(rs,mid+,r,L,R));
return ret;
}
ll qsum(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return t[x].sum;
}
pushdown(x,l,r);ll ret=;
if(L<=mid) ret+=qsum(ls,l,mid,L,R);
if(mid<R) ret+=qsum(rs,mid+,r,L,R);
return ret;
}
int main(){
rd(n);
for(reg i=;i<=n;++i){
rd(a[i]);
}
rd(m);
++tot;
build(,,n);
//cout<<" tot "<<tot<<endl;
int op,l,r,x;
int o=;
while(m--){
++o;
// cout<<" oooo "<<o<<endl;
rd(op);
switch(op){
case :rd(l);rd(r);rd(x);add(,,n,l,r,x);break;
case :rd(l);rd(r);rd(x);chanmx(,,n,l,r,x);break;
case :rd(l);rd(r);rd(x);chanmi(,,n,l,r,x);break;
case :rd(l);rd(r);printf("%lld\n",qsum(,,n,l,r));break;
case :rd(l);rd(r);printf("%d\n",qmax(,,n,l,r));break;
case :rd(l);rd(r);printf("%d\n",qmin(,,n,l,r));break;
}
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2018/12/27 9:57:30
*/
不亏是九老师自己出的题