众所周知，线段树是一个神奇的数据结构，它的神奇之处在于有时你以为你已经是在暴力了，然而其实你的做法却非常的优(一般在$O(n\log n) -O(n \log n\log n) $之间)，orz jiry_2在16年集训队论文里主要论述了这些玄学，我照着论文口胡两句(持续施工)
给出一个长度为$n$的数组$A$，接下来有$m$次操作，操作有如下$3$种:
$1.$给出$l,r,x$，对所有的$i \in [l,r]$，把$A_i$变为$\min(A_i,x)$
$2.$给出$l,r$，求$\sum_{i=l}^rA_i$
$3.$给出$l,r$，求$\max_{i=l}^r A_i$
主要论述一种路人皆知的做法以及复杂度的证明。
对于每个线段树节点，维护一个对应区间的最大值以及最大值的个数以及次大值的个数。
然后在更新的时候，如果$x$大于等于区间最大值$fi$，则不会对区间造成任何影响。
如果$x\in(se,fi]$,这个更新很方便吧，直接把最大值给换成$x$然后维护$cnt_{fi}$即可。
如果$x<se$，暴力向下更新。
若要说这玩意的复杂度是$O((n+m) \log n)$的，想必大家都目(zao)瞪(jiu)口(zhi)呆(dao)了。
我说一个比较通俗的证明:
可以把最大值视为标记，如果一个节点的最大值和他爹的最大值相同，那么这个点就没有标记值。
下面是一个例子:(左边是最大值，右边是标记值)
这个标记具有一些特别的性质:每个点的真实权值=从这个点往上遇到的第一个有标记的节点的标记值。以及你维护的节点的$se$，就是子节点标记的最大值。
显然第一遍build完线段树，标记共有$n$个
然后我们看更新:
if $x\geq fi$,不会有任何影响。
else if $x \in (se,fi]$,更新了$fi$就退出了，也不会有啥事。
else 激动人心的暴力更新来了。
这个暴力更新的本质，正如jiry_2在论文中所说，是为了满足标记随深度递减的性质，在自述中回收掉值大于它的标记。
观察这个标记回收，在回收的过程中，至少减少了一个标记
又一个标记至多存在$O(\log n)$个，那么回收一个标记的复杂度为$O(\log n)$，回收$n$个的复杂度为$O(n \log n)个$
怎么回事，那么我这样的复杂度不是变成了$O((n+m)\log n)$了，怎么和吉利的$O(m \log n)$不一样。。
算了反正同阶，不管他。。
那么复杂度就得证了。
代码里用了一个我也不晓得是啥的读入方式(大概是一口气把东西读进来然后需要读东西的时候在数组里读)。。不用就会T
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
const int M=1e6+5;
typedef long long ll;
char *ch,buf[40*1024000+5];
inline void rd(int &a){
for(++ch;*ch<=32;++ch);
for(a=0;47<*ch;++ch)a=a*10+(*ch^48);
}
int n,m,A[M];
inline void Min(int &a,int b){
if(a>b)a=b;
}
struct Segment_Tree{
struct node{
int flag,fi,se,cnt_fi;
ll sum;
}tree[M<<2];
inline void up(int &p){
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
bool f=tree[p<<1].fi<tree[p<<1|1].fi;
tree[p].fi=tree[p<<1|f].fi;
tree[p].cnt_fi=tree[p<<1|f].cnt_fi;
if(tree[p].fi==tree[p<<1|f^1].fi)tree[p].cnt_fi+=tree[p<<1|f^1].cnt_fi;
if(tree[p].fi!=tree[p<<1|f^1].fi)tree[p].se=max(tree[p<<1|f].se,tree[p<<1|f^1].fi);
else tree[p].se=max(tree[p<<1].se,tree[p<<1|1].se);
}
inline void down(int &p){
for(int i=0;i<2;++i)
if(tree[p].fi<tree[p<<1|i].fi){
tree[p<<1|i].sum-=(ll)(tree[p<<1|i].fi-tree[p].fi)*tree[p<<1|i].cnt_fi;
tree[p<<1|i].fi=tree[p].fi;
}
}
inline void build(int l=1,int r=n,int p=1){
tree[p]=(node){0,0,0,0,0};
if(l==r){
tree[p].sum=tree[p].fi=A[l];
tree[p].cnt_fi=1;
return;
}
int mid=l+r>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
up(p);
}
inline void update(int l,int r,int x,int L=1,int R=n,int p=1){
down(p);
if(l==L&r==R){
if(tree[p].fi<=x)return;
if(tree[p].se<=x){
tree[p].sum-=(ll)(tree[p].fi-x)*tree[p].cnt_fi;
tree[p].fi=x;return;
}
}
int mid=L+R>>1;
if(r<=mid)update(l,r,x,L,mid,p<<1);
else if(l>mid)update(l,r,x,mid+1,R,p<<1|1);
else update(l,mid,x,L,mid,p<<1),update(mid+1,r,x,mid+1,R,p<<1|1);
up(p);
}
inline ll query_sum(int l,int r,int L=1,int R=n,int p=1){
if(l==L&r==R)return tree[p].sum;
down(p);
int mid=L+R>>1;
if(r<=mid)return query_sum(l,r,L,mid,p<<1);
if(l>mid)return query_sum(l,r,mid+1,R,p<<1|1);
return query_sum(l,mid,L,mid,p<<1)+query_sum(mid+1,r,mid+1,R,p<<1|1);
}
inline int query_mx(int l,int r,int L=1,int R=n,int p=1){
if(l==L&r==R)return tree[p].fi;
down(p);
int mid=L+R>>1;
if(r<=mid)return query_mx(l,r,L,mid,p<<1);
if(l>mid)return query_mx(l,r,mid+1,R,p<<1|1);
return max(query_mx(l,mid,L,mid,p<<1),query_mx(mid+1,r,mid+1,R,p<<1|1));
}
}sgt;
inline void gao(){
rd(n),rd(m);
for(int i=1;i<=n;++i)
rd(A[i]);
sgt.build();
for(int opt,l,r,x;m--;){
rd(opt),rd(l),rd(r);
switch(opt){
case(0):rd(x);sgt.update(l,r,x);break;
case(1):printf("%d\n",sgt.query_mx(l,r));break;
case(2):printf("%lld\n",sgt.query_sum(l,r));break;
}
}
}
int main(){
ch=buf-1;
fread(buf,1,1000*35*1024,stdin);
int _;
for(rd(_);_--;)gao();
return 0;
}
在上一题的基础上加入区间加减。
看了jiry_2的证明我不明觉厉。。
看了半天智商不够的我只领悟了一个地方:哦，原来复杂度变成了$O(m\log n \log n)$
看不懂所以只好自己瞎比扯一下皮。
证明:
同样的我们沿用上题的标记机制。
如果有了区间加减会发生什么呢?
无非是本来标记已经被删除了的点的标记又冒出来了
但是这个区间是同加同减的。
换而言之，对于线段树上一个节点对于的区间，标记只会增加$1$
一个区间至多被分成$\log n$个区间
也就是说在一次区间加减的过程中，标记至多增加$\log n$个。
那么暴力回收的复杂度就是$O(n \log n \log n)$了
没地方交的题所以没有代码。
给出一个长度为$n$的数列$A$，以及$m$次操作，操作有如下3种:
$1.$对于所有$i \in [l,r]$，将$A_i$变成$\min(A_i,x)$ $2.$对于所有$i \in [l,r]$，将$A_i$变成$\max(A_i,x)$ $3.$求$\sum_{i=l}^r A_i$
这次打两个标记。
复杂度证明:
同样的，加入了区间取最大值会改变标记的个数。
但是同样的，这里的相对性由于已经有了最大值的限制，只会变小不会变大。
也就是说一个节点对应的区间的标记值不会增加
那么一个区间取$\max$至多被划分成$\log n$个区间，单次至多增加$O(\log n)$个标记。
暴力回收的复杂度为$O(n\log n \log n)$，不会退化
没地方交的题同样没代码。。
以上是论文里最简单(虽然我啥也看不懂)的部分，先在此小结。