[jry线段树]小结

线段树能维护一些具有加减性质的题目。但是对于取min，取max之类的操作很难做。
jry提供了一个nlog^2(实际上跑起来是nlog)级别的算法，segment tree beats。
这个算法的复杂度证明比较困难可以去2016集训队论文里面看。
以取min作为例子，他的算法的核心是对于当前区间的最大值ma和严格次大值se作讨论，如果ma < min显然这个区间可以跳过，如果ma>min>se，那么他只对ma产生影响，求和的话就是顺便记录ma的数量就能维护区间和了，并且为这个区间打上标记。否则的话没有办法更新这个区间，我们继续dfs左右区间。
如果我们又要支持加的操作的话，可能标记下放的顺序可能会造成一点问题。我们考虑先下放add的标记，再下放min的标记。我们发现实际上这个做法实际上是通过对区间中的数分类来使得区间取min的操作变成区间对最大值的减法操作。那么加法标记我们就正常打就行了，对于一个取min操作，实际上就是看一下左右区间哪个的max等于当前区间的max。然后把min标记传下去就可以了(实际上你直接看成把一个减法标记下传或许更好理解)。

一份用来判断区间内是否完全递减的segment tree beats板子。

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline int read()
{
    char c;
    bool pd=0;
    while((c=getchar())>'9'||c<'0')
    if(c=='-') pd=1;
    int res=c-'0';
    while((c=getchar())>='0'&&c<='9')
    res=(res<<3)+(res<<1)+c-'0';
    return pd?-res:res;
}
const int N=110000;
const int M=410000;
const int inf=1e9;
struct cc
{
    int max,sec,min,flag;
}a[M];
int tag1[M],tag2[M];
inline void updata(int k)
{
    a[k].min=min(a[k<<1].min,a[k<<1|1].min);
    a[k].max=max(a[k<<1].max,a[k<<1|1].max);
    if(a[k<<1].max==a[k<<1|1].max) a[k].sec=max(a[k<<1].sec,a[k<<1|1].sec);
    else if(a[k<<1].max>a[k<<1|1].max) a[k].sec=max(a[k<<1].sec,a[k<<1|1].max);
    else a[k].sec=max(a[k<<1].max,a[k<<1|1].sec);
    a[k].flag=a[k<<1].flag&&a[k<<1|1].flag&&(a[k<<1].min>=a[k<<1|1].max);
}
inline void tag_down(int k)
{
    if(tag1[k])
    {
        a[k<<1].max+=tag1[k];
        a[k<<1].min+=tag1[k];
        tag1[k<<1]+=tag1[k];
        if(a[k<<1].sec!=-inf) a[k<<1].sec+=tag1[k]; 
        a[k<<1|1].max+=tag1[k];
        a[k<<1|1].min+=tag1[k];
        tag1[k<<1|1]+=tag1[k];
        if(a[k<<1|1].sec!=-inf) a[k<<1|1].sec+=tag1[k]; 
        tag1[k]=0;
    }
    if(tag2[k])
    {
        if(a[k].max+tag2[k]==a[k<<1].max)
        {
            if(a[k<<1].min==a[k<<1].max) a[k<<1].min-=tag2[k];
            a[k<<1].max-=tag2[k];
            tag2[k<<1]+=tag2[k]; 
        }
        if(a[k].max+tag2[k]==a[k<<1|1].max)
        {
            if(a[k<<1|1].min==a[k<<1|1].max) a[k<<1|1].min-=tag2[k];
            a[k<<1|1].max-=tag2[k];
            tag2[k<<1|1]+=tag2[k]; 
        }
        tag2[k]=0;
    }
}
inline void setmin(int k,int l,int r,int L,int R,int v)
{
    int mid=l+r>>1;
    if(L<=l&&r<=R)
    {
        if(a[k].max<v) return;
        if(a[k].sec<v)
        {
            tag2[k]+=a[k].max-v;
            if(a[k].min==a[k].max) a[k].min=v;
            a[k].max=v;
//          printf("%d %d\n",k,v);
        }
        else
        {
            tag_down(k);
            setmin(k<<1,l,mid,L,R,v);
            setmin(k<<1|1,mid+1,r,L,R,v);
            updata(k);
        }
        return;
    }
    tag_down(k);
    if(mid>=L) setmin(k<<1,l,mid,L,R,v);
    if(mid< R) setmin(k<<1|1,mid+1,r,L,R,v);
    updata(k);
}
inline void add(int k,int l,int r,int L,int R,int v)
{
    if(L<=l&&r<=R)
    {
        a[k].max+=v;
        a[k].min+=v;
        if(a[k].sec!=-inf) a[k].sec+=v;
        tag1[k]+=v;
//      printf("%d %d\n",k,v); 
        return;
    }
    tag_down(k);
    int mid=l+r>>1;
    if(mid>=L) add(k<<1,l,mid,L,R,v);
    if(mid< R) add(k<<1|1,mid+1,r,L,R,v);
    updata(k);
}
inline cc query(int k,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return a[k];
    int mid=l+r>>1;
    tag_down(k);
    if(R<=mid) return query(k<<1,l,mid,L,R);
    if(L> mid) return query(k<<1|1,mid+1,r,L,R);
    cc a1=query(k<<1,l,mid,L,R);
    cc a2=query(k<<1|1,mid+1,r,L,R);
    return (cc){max(a1.max,a2.max),0,min(a1.min,a2.min),a1.flag&&a2.flag&&(a1.min>=a2.max)}; 
}
int b[N];
inline void build(int k,int l,int r)
{
    if(l==r)
    {
        a[k].max=a[k].min=b[l];
        a[k].flag=1;
        a[k].sec=-inf;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r); 
    updata(k);
}
int n,m;
int main()
{
//  freopen("c.in","r",stdin);
//  freopen("c.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;++i) b[i]=read();
    int size=1;
    while(size<n) size<<=1;
    build(1,1,size);
    int t,l,r,x;
    while(m--)
    {
        t=read();
        l=read();
        r=read();
        if(t==1) add(1,1,size,l,r,read());
        if(t==2) setmin(1,1,size,l,r,read());
        if(t==3)
        {
            cc ans;
            ans=query(1,1,size,l,r);
            if(ans.flag) printf("1\n");
            else printf("%d\n",r-l+1);
        }
    }
}

因为刚入门，之后做题的时候再updata