线段树
即使是最基础的线段树也有很多应用，比如什么优化dp啦，标记的神奇维护啦……
需要思路灵活一点，把题目条件抽象成更为简单的形式
扫描线
求矩形面积并，周长，二维数点等等
线段树作用即把静态O(n^2)变为动态O(nlogn).
想象过程，就是在一张图上，一条线从上到下扫描。所以线段树本质维护的是矩形的长，而宽又是从上到下排序过的，所以每次乘上差值即可。
常用手法比如把点的问题转化为矩形，可以求最大面积交/并
注意这个线段树写法和别的不太一样，有时需要离散化或动态开点。而且记录询问的数组开2倍。线段树必须开16倍空间，读入add就是二倍，线段树4倍，在pushup不可避免访问叶子节点的儿子，再有2倍。这里线段树是存的端点。
其实线段树可以直接存线段作为一个节点，这样在建树上需要考虑的东西更少，更不容易出错。
扫描线
#include<bits/stdc++.h>
#define ll long long
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
const int maxn=100015;
struct node{
ll x,yl,yr;
int fl;
}p[maxn<<1];
struct tree{
ll l,r,sum;
}t[maxn<<4];
int n,tg[maxn<<4];
ll s[maxn<<1],ans;
bool cmp(node a,node b){
return a.x<b.x;
}
void pushup(int id){
if(tg[id]>0) t[id].sum=t[id].r-t[id].l;//注意，这里代表是否矩形完全覆盖该位置
else t[id].sum=t[lid].sum+t[rid].sum;
}
void build(int id,int l,int r){
t[id].l=s[l];//离散化，t[id]的l/r不是普遍意义
t[id].r=s[r];
if(r-l==1){
t[id].sum=0;
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);//维护的是面积，所以是按照矩形的边计算，mid相同
build(rid,mid,r);
//又，我这个离谱扫描线写法。。。其实也可以让线段树的每个点不是存节点，而是存一条边，它对于l,r,mid的处理就和普通线段树一样了
pushup(id);
}
void add(int id,ll yl,ll yr,int fl){
if(t[id].l==yl&&t[id].r==yr){
tg[id]+=fl;
pushup(id);
return;
}//这种写法实际上mid=t[lid].r=t[rid].l
if(yl<t[lid].r) add(lid,yl,min(t[lid].r,yr),fl);
if(yr>t[rid].l) add(rid,max(t[rid].l,yl),yr,fl);
pushup(id);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
ll xl,yl,xr,yr;
scanf("%lld%lld%lld%lld",&xl,&yl,&xr,&yr);
p[i]=(node){xl,yl,yr,1};
p[i+n]=(node){xr,yl,yr,-1};
s[i]=yl,s[i+n]=yr;
}
sort(s+1,s+n*2+1);
sort(p+1,p+n*2+1,cmp);
build(1,1,2*n);
add(1,p[1].yl,p[1].yr,p[1].fl);
for(int i=2;i<=2*n;i++){
ans+=(p[i].x-p[i-1].x)*t[1].sum;
//printf("%d ",i);
add(1,p[i].yl,p[i].yr,p[i].fl);
}
printf("%lld",ans);
return 0;
}
主席树
可持久化权值线段树，经典应用是区间k大值
前置知识：权值线段树，动态开点线段树等
可以简单理解为对动态开点线段树做前缀和。新建的点连成的树和过去的树共用一部分节点。每次查询的时候用区间右减去区间左前一个的树，就得到了当前区间的树（和前缀和用法一样）。
主席树[luogu3834]
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,mx=1e9;
int n,m,rt[maxn],cnt;
struct node{
int lc,rc,siz;
}t[maxn<<5];
void add(int &x,int y,int l,int r,int val){
x=++cnt,t[x]=t[y],t[x].siz++;
if(l==r) return ;
int mid=(l+r)>>1;
if(val<=mid) add(t[x].lc,t[y].lc,l,mid,val);
else add(t[x].rc,t[y].rc,mid+1,r,val);
}
int query(int x,int y,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1,tmp=t[t[y].lc].siz-t[t[x].lc].siz;
if(tmp<k) return query(t[x].rc,t[y].rc,mid+1,r,k-tmp);
else return query(t[x].lc,t[y].lc,l,mid,k);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
add(rt[i],rt[i-1],0,mx,x);
}
while(m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",query(rt[l-1],rt[r],0,mx,k));
}
return 0;
}
线段树优化建图
一看到点和区间或区间和区间连边的问题，大概率就是线段树优化建图了。
其基本思想就是自上而下连一个“出树”，自下而上连一个“入树”，对于其叶子节点（1-n）相互一一连边。然后按照题目要求从入树的节点/区间，连向出树的节点/区间。
一般建完图跑最短路的情况较多。
边数是(n+m)logn级别的，所以一般来说最短路跑出来是 \(O(nlog^2n)\) 的。
注意数组大小和空间限制！
[SNOI2017] 炸弹
//线段树优化建边+tarjan缩点+注意dp形式
//为什么re？？
//有必要这样卡吗？
#include<bits/stdc++.h>
#define ll long long
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
const ll mod=1e9+7;
const int maxn=5e5+5;
int cnt,h[maxn<<2],g[maxn<<2];
struct edge{
int to,nxt;
}e[maxn*25],e1[maxn*25];
void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=h[u];
h[u]=cnt;
}
int cnt1,h1[maxn<<2],g1[maxn<<2];
void add1(int u,int v){
e1[++cnt1].to=v;
e1[cnt1].nxt=h1[u];
h1[u]=cnt1;
}
int n,nx,k,num;
ll xx[maxn<<2],rr[maxn<<2],low[maxn<<2],dfn[maxn<<2],ins[maxn<<2],d[maxn<<2],la[maxn<<2],ra[maxn<<2];
struct node{
ll l,r;
}t[maxn<<2];
void build(int id,int l,int r){
t[id].l=l;
t[id].r=r;
nx=max(nx,id);
if(l==r){
g[l]=id;
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
add(id,lid);
add(id,rid);
}
void xadd(int id,int lx,int rx,int l,int r,int q){
if(l<=lx&&rx<=r){
if(id!=q) add(q,id);//防止自环！！！！
return ;
}
int mid=(lx+rx)>>1;
if(l<=mid) xadd(lid,lx,mid,l,r,q);
if(r>mid) xadd(rid,mid+1,rx,l,r,q);
}
stack<ll>s;
void tarjan(int x){
low[x]=dfn[x]=++num;
s.push(x);
ins[x]=1;
for(int i=h[x];i;i=e[i].nxt){
int y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
k++;
int tmp=0;
while(tmp!=x){
tmp=s.top();
s.pop();
ins[tmp]=0;
d[tmp]=k;
la[k]=min(la[k],t[tmp].l);
ra[k]=max(ra[k],t[tmp].r);
}
}
}
bool vis[maxn<<2];
void dfs(int x){
vis[x]=1;
for(int i=h1[x];i;i=e1[i].nxt){
int y=e1[i].to;
if(!vis[y]) dfs(y);
la[x]=min(la[x],la[y]);
ra[x]=max(ra[x],ra[y]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&xx[i],&rr[i]);
}
build(1,1,n);
xx[n+1]=0x3f3f3f3f3f3f3f3f;//便于查找位置
for(int i=1;i<=n;i++){
if(!rr[i]) continue;
int tl=lower_bound(xx+1,xx+n+1,xx[i]-rr[i])-xx;
int tr=upper_bound(xx+1,xx+n+1,xx[i]+rr[i])-xx-1;
xadd(1,1,n,tl,tr,g[i]);
}
memset(la,0x3f,sizeof(la));
tarjan(1);
for(int i=1;i<=nx;i++){//注意这里是build后的
for(int j=h[i];j;j=e[j].nxt){
int y=e[j].to;
if(d[i]!=d[y]){
add1(d[i],d[y]);
}
}
}
for(int i=1;i<=k;i++){
if(!vis[i]){
dfs(i);
}
}
ll ans=0;
for(int i=1;i<=n;i++){
ans=(ans+(ll)i*(ra[d[g[i]]]-la[d[g[i]]]+1)%mod)%mod;
}
printf("%lld",ans);
return 0;
}
线段树合并
新建/不新建节点
还可以回收节点！
线段树分裂
有点像FHQ-treap的 split函数（分裂？
比如权值线段树以k为界分裂 split(x,y,k)，即分裂x，给y
val[lc[x]]<k，左子树不用修改，直接 split(rc[x],rc[y],k-v)
val[lc[x]]=k，左子树正好包含前k个，于是将右子树给y，rc[y]=rc[x],rc[x]=0
val[lc[x]]>k，右子树全大于k，直接给y，递归左子树，split(lc[x],lc[y],k)
每次只会递归一边，单次时间复杂度O(logn)
线段树分裂/合并板子
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
int n,m,cnt,rt[maxn<<2],crt=1;
ll a[maxn];
struct node{
int lc,rc; ll v;
}t[maxn<<5];
ll read(){
char ch=getchar(); ll x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
void write(ll x){
if(x>9) write(x/10);
putchar('0'+x%10);
}
//int newnode(){
// return dcnt?p[dcnt--]:++cnt;//关于回收点，不写也是对的
//}
//void del(int x){
// p[++dcnt]=x;
// t[x].lc=t[x].rc=t[x].v=0;
//}
void add(int &x,int l,int r,int pos,ll val){
if(!x) x=++cnt;
if(l==r){
t[x].v+=val; return ;
}
int mid=(l+r)>>1;
if(pos<=mid) add(t[x].lc,l,mid,pos,val);
else add(t[x].rc,mid+1,r,pos,val);
t[x].v=t[t[x].lc].v+t[t[x].rc].v;
}
ll query(int x,int l,int r,int vl,int vr){
if(!x||vl>r||vr<l) return 0;
if(vl<=l&&r<=vr) return t[x].v;
int mid=(l+r)>>1; ll res=0;
if(vl<=mid) res=query(t[x].lc,l,mid,vl,vr);
if(vr>mid) res+=query(t[x].rc,mid+1,r,vl,vr);
return res;
}
int kth(int x,int l,int r,ll val){
if(l==r) return l;
int mid=(l+r)>>1;
if(t[t[x].lc].v>=val) return kth(t[x].lc,l,mid,val);
else return kth(t[x].rc,mid+1,r,val-t[t[x].lc].v);
}
int merge(int x,int y){
if(!x||!y) return x+y;
t[x].v+=t[y].v;
t[x].lc=merge(t[x].lc,t[y].lc);
t[x].rc=merge(t[x].rc,t[y].rc);
// del(y);
return x;
}
void split(int x,int &y,ll k){
if(!x) return ;
y=++cnt;
ll val=t[t[x].lc].v;
if(k>val) split(t[x].rc,t[y].rc,k-val);
else swap(t[x].rc,t[y].rc);//k<=val
if(k<val) split(t[x].lc,t[y].lc,k);
t[y].v=t[x].v-k,t[x].v=k;//存的是个数
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
add(rt[1],1,n,i,a[i]);
}
for(int i=1;i<=m;i++){
int opt=read(),x=read(),y=read(); ll z;
if(opt==0){
z=read();
ll q1=query(rt[x],1,n,1,z),q2=query(rt[x],1,n,y,z);int tmp=0;
crt++,split(rt[x],rt[crt],q1-q2),split(rt[crt],tmp,q2);//注意split还是要先跑出数量来分裂，主要是可能没有等于k的点，难以处理分裂
rt[x]=merge(rt[x],tmp);
}
else if(opt==1){
rt[x]=merge(rt[x],rt[y]);
}
else if(opt==2){
z=read();
add(rt[x],1,n,z,y);
}
else if(opt==3){
z=read(); write(query(rt[x],1,n,y,z)),putchar('\n');
}
else{
if(t[rt[x]].v<1ll*y) printf("-1\n");
else write(kth(rt[x],1,n,y)),putchar('\n');
}
}
return 0;
}
线段树分治
离线算法，我们对时间（询问）建立一颗线段树，树的节点存的信息是“覆盖了这个区间的操作”。一般是 \(O(nlog^2n)\) 左右的。
实现上每遍历到一个节点就去add，出了某个节点需要del，用一个可撤销并查集维护。
Q: 为什么要建线段树呢？遍历到l的时候加入，到r的时候删除不好吗？
A：可撤销并查集必须保证插入和删除的顺序完全相同，是一个栈。如果不建线段树根本无法使用可撤销并查集。
注意，可撤销并查集只能按秩合并/启发式合并，不能路径压缩！（按秩合并更快，但不好写
使用情景：每个操作影响范围是一个区间，多组操作后询问。（还经常实用扩展域并查集！）
Pastoral Oddities
//非常非常巧妙，首先发现性质，只有偶数连通块
//其次注意到kruskal单调不增的性质，某个边一旦被淘汰就不会再被选中
//还是从小到大去做，注意从后向前去选择，因为答案单调
//半在线线段树分治
#include<bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
const int maxn=5e5+5;
int n,m,k,q,ans[maxn],s[maxn<<3],top,cnt,num;
struct node{
int x,y,id,z;
}e[maxn<<1];
int f[maxn<<1],siz[maxn<<1];
bool cmp(node a,node b){
return a.z<b.z;
}
int find(int x){
return (f[x]==x)?x:find(f[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y) return ;
if(siz[x]>siz[y]) swap(x,y);
cnt-=(siz[x]&1)+(siz[y]&1);
siz[y]+=siz[x],f[x]=y;
s[++top]=x;
cnt+=(siz[y]&1);
}
void del(int now){
while(top>now){
int x=s[top--],y=f[x];
cnt-=(siz[y]&1);
siz[y]-=siz[x];
cnt+=(siz[x]&1)+(siz[y]&1);
f[x]=x;
}
}
vector<int>v[maxn<<3];
void upd(int id,int l,int r,int vl,int vr,int pos){
if(vl>vr) return ;
if(vl<=l&&r<=vr){
v[id].push_back(pos);
return ;
}
int mid=(l+r)>>1;
if(vl<=mid) upd(lid,l,mid,vl,vr,pos);
if(vr>mid) upd(rid,mid+1,r,vl,vr,pos);
}
void sol(int id,int l,int r){
int ttop=top;
for(auto i:v[id]){
merge(e[i].x,e[i].y);
}
if(l==r){
while(cnt&&num<m){
num++;
if(e[num].id<=l){
upd(1,1,m,e[num].id,l-1,num);
merge(e[num].x,e[num].y);
}
}
if(cnt==0) ans[l]=e[num].z;
else ans[l]=-1;
del(ttop);
return ;
}
int mid=(l+r)>>1;
sol(rid,mid+1,r),sol(lid,l,mid);
del(ttop);
}
int read(){
char ch=getchar(); int x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
e[i].x=read(),e[i].y=read(),e[i].z=read();
e[i].id=i;
}
for(int i=1;i<=n;i++) f[i]=i,siz[i]=1;
cnt=n;
sort(e+1,e+m+1,cmp);
sol(1,1,m);
for(int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
线段树二分
简而言之就是直接在线段树上跑二分，就和单点插入时那个寻找mid和pos关系比较像（包括类似于就是权值线段树查询k小值的写法
if(true) return sol(rid,mid+1,r,p);
else return sol(lid,l,mid,p);
优点是不用单独写二分，少一个log的复杂度，即总复杂度为O((n+q)logn)
树套树
主席树本来是不支持修改的。
但考虑，主席树其实就是对很多树链做了前缀和。那么对于单点修改（要求的修改操作），区间查询（原本主席树支持的），不就是用树状数组维护吗？！
所以就诞生了树套树中树状数组套主席树的写法。（当然你也可以套平衡树）
至于复杂度，树状数组的单点修改区间查询都是logn的，那么总时间复杂度 \(O(nlog^2n)\)
树套树
//树状数组套主席树
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5,mx=1e8;
int n,m,p1[maxn<<5],p2[maxn<<5],tp1[maxn<<5],tp2[maxn<<5],num1,num2;
int rt[maxn<<2],a[maxn<<2];
inline int lowbit(int x){
return x&(-x);
}
inline int read(){
char ch=getchar(); int x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar('0'+x%10);
}
struct seg{
int cnt=0;
struct node{
int v,lc,rc;
}t[maxn<<10];
inline void add(int &x,int l,int r,int pos,int val){
if(!x) x=++cnt; t[x].v+=val;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) add(t[x].lc,l,mid,pos,val);
else add(t[x].rc,mid+1,r,pos,val);
}
//p2-p1
inline int query(int p1[],int p2[],int l,int r,int pos){
if(l==r) return 0;//可爱的边界条件……这里注意，为了方便后面查询前后继，不要算上等于
int mid=(l+r)>>1;
if(pos<=mid){
for(int i=1;i<=num1;i++) p1[i]=t[p1[i]].lc;
for(int i=1;i<=num2;i++) p2[i]=t[p2[i]].lc;
return query(p1,p2,l,mid,pos);
} else{
int tmp=0;
for(int i=1;i<=num1;i++) tmp-=t[t[p1[i]].lc].v,p1[i]=t[p1[i]].rc;
for(int i=1;i<=num2;i++) tmp+=t[t[p2[i]].lc].v,p2[i]=t[p2[i]].rc;
return tmp+query(p1,p2,mid+1,r,pos);
}
}
inline int kth(int p1[],int p2[],int l,int r,int k){
if(l==r) return l;
int tmp=0;
for(int i=1;i<=num1;i++) tmp-=t[t[p1[i]].lc].v;
for(int i=1;i<=num2;i++) tmp+=t[t[p2[i]].lc].v;
int mid=(l+r)>>1;
if(k>tmp){
for(int i=1;i<=num1;i++) p1[i]=t[p1[i]].rc;
for(int i=1;i<=num2;i++) p2[i]=t[p2[i]].rc;
return kth(p1,p2,mid+1,r,k-tmp);
} else{
for(int i=1;i<=num1;i++) p1[i]=t[p1[i]].lc;
for(int i=1;i<=num2;i++) p2[i]=t[p2[i]].lc;
return kth(p1,p2,l,mid,k);
}
}
}T;
inline void add(int x,int val){
int i=x;
while(x<=n){
T.add(rt[x],0,mx,a[i],-1);
x+=lowbit(x);
}
a[i]=val,x=i;
while(x<=n){
T.add(rt[x],0,mx,a[i],1);
x+=lowbit(x);
}
}
inline void query(int x,int y,int k,int fl){
num1=num2=0,x--;
int len=y-x;
while(x){
num1++,p1[num1]=tp1[num1]=rt[x];
x-=lowbit(x);
}
while(y){
num2++,p2[num2]=tp2[num2]=rt[y];
y-=lowbit(y);
}
if(fl==1) write(T.query(p1,p2,0,mx,k)+1);
else if(fl==2) write(T.kth(p1,p2,0,mx,k));
else{
if(fl==4){
if(k==0) write(-2147483647);
else{
x=T.query(p1,p2,0,mx,k);
write((x==0)?-2147483647:T.kth(tp1,tp2,0,mx,x));
}
}
else{
if(k==mx) write(2147483647);
else{
x=T.query(p1,p2,0,mx,k+1);
write((x==len)?2147483647:T.kth(tp1,tp2,0,mx,x+1));
}
}
}
putchar('\n');
}
int main(){
// system("fc 1.out ans.out");
// freopen("1.in","r",stdin);
// freopen("ans.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
for(int j=i;j<=n;j+=lowbit(j))
T.add(rt[j],0,mx,a[i],1);//这个add好像必须这样写，因为要新建点！
}
while(m--){
int opt=read(),l=read(),r=read(),k;
if(opt==3) add(l,r);
else{
k=read();
query(l,r,k,opt);
}
}
return 0;
}
吉司机线段树 Seg-beats
经典问题是，给定一个序列，支持区间取min/max和区间求和。时间复杂度O((n+q)logn)
以维护区间取min为例，线段树每个节点维护mx(区间最大值),cnt(区间最大值的出现次数),cmx(区间严格次大值),sum(区间和).
做区间取min时，递归到某个节点p
- \(x \geq mx_p\) ，则这次修改不影响节点p，直接return
2）\(x \leq cmx_p\)，则直接暴力往p的左右子节点递归
3）\(cmx_p < x < mx_p\)，则这次修改对 \(sum_p\) 的贡献为 \(-cnt_p*(mx_p-x)\)，\(mx_p=x\)
复杂度分析：需要用到势能分析。
设线段树T上，“一类点”为其最大值等于父亲的最大值的点，二类点为其最大值小于父亲的最大值的点。
设一棵线段树的势能函数\(Φ(T)\)为二类点的数量，则\(Φ(T) \leq n\)
每次区间取min的操作更新下来，会有若干二类点变成一类点，而变一个二类点的花费是O(logn)的（一条路径顺下来），一类点受到更改是O(1)的
那么均摊下来，总复杂度不超过\(O(nlogn)\)
注意，吉司机线段树也可以维护区间加，多带一个加法标记即可，但复杂度要多一个log，复杂度分析类似
历史最值线段树
实际上就是多维护了一个标记，hadd表示历史上最大的addtag，每次先下传历史最大add再下传覆盖/修改等标记。
[模板]线段树3（吉司机线段树+历史最值）
#include<bits/stdc++.h>
#define ll long long
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
const int maxn=5e5+5;
const ll inf=-(1ll<<61);
int n,m;
ll a[maxn];
struct node{
int l,r,cnt;
ll ad,had,cad,hcad;//hadd没更新之前的最大tag，最大值和次大值分开维护
ll mx,cmx,hmx,sum;
}t[maxn<<2];
void upd(int id,ll ad,ll had,ll cad,ll hcad){
t[id].sum+=ad*t[id].cnt+cad*(t[id].r-t[id].l+1-t[id].cnt);
t[id].hmx=max(t[id].hmx,t[id].mx+had);//注意上就是先下传之前的maxadd
t[id].mx+=ad;
if(t[id].cmx!=inf) t[id].cmx+=cad;
t[id].had=max(t[id].had,t[id].ad+had);
t[id].hcad=max(t[id].hcad,t[id].cad+hcad);
t[id].ad+=ad,t[id].cad+=cad;
}
void pushdown(int id){
ll tmp=max(t[lid].mx,t[rid].mx);//傻了。。这才是要pushdown去更新的max，因为当前节点的max已经被更改，所以只看下面的最大值
if(tmp==t[lid].mx) upd(lid,t[id].ad,t[id].had,t[id].cad,t[id].hcad);
else upd(lid,t[id].cad,t[id].hcad,t[id].cad,t[id].hcad);
if(tmp==t[rid].mx) upd(rid,t[id].ad,t[id].had,t[id].cad,t[id].hcad);
else upd(rid,t[id].cad,t[id].hcad,t[id].cad,t[id].hcad);
t[id].ad=t[id].had=t[id].cad=t[id].hcad=0;
}
void pushup(int id){
if(t[lid].mx>t[rid].mx){
t[id].mx=t[lid].mx,t[id].cnt=t[lid].cnt;
t[id].cmx=max(t[lid].cmx,t[rid].mx);
}
else if(t[lid].mx<t[rid].mx){
t[id].mx=t[rid].mx,t[id].cnt=t[rid].cnt;
t[id].cmx=max(t[lid].mx,t[rid].cmx);
}
else{
t[id].mx=t[lid].mx,t[id].cnt=t[lid].cnt+t[rid].cnt;
t[id].cmx=max(t[lid].cmx,t[rid].cmx);
}
t[id].hmx=max(t[lid].hmx,t[rid].hmx);
t[id].sum=t[lid].sum+t[rid].sum;
}
void build(int id,int l,int r){
t[id].l=l,t[id].r=r;
if(l==r){
t[id].mx=t[id].hmx=t[id].sum=a[l];
t[id].cnt=1,t[id].cmx=inf;
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid),build(rid,mid+1,r);
pushup(id);
}
void add(int id,int l,int r,int vl,int vr,ll val){
if(vl<=l&&r<=vr){
upd(id,val,val,val,val);
return ;
}
int mid=(l+r)>>1; pushdown(id);
if(vl<=mid) add(lid,l,mid,vl,vr,val);
if(vr>mid) add(rid,mid+1,r,vl,vr,val);
pushup(id);
}
void change(int id,int l,int r,int vl,int vr,ll val){
if(val>=t[id].mx) return ;
if(vl<=l&&r<=vr&&t[id].cmx<val){
t[id].sum-=1ll*t[id].cnt*(t[id].mx-val);
t[id].ad-=t[id].mx-val,t[id].mx=val;
return ;
}
int mid=(l+r)>>1; pushdown(id);
if(vl<=mid) change(lid,l,mid,vl,vr,val);
if(vr>mid) change(rid,mid+1,r,vl,vr,val);
pushup(id);
}
ll query(int id,int l,int r,int vl,int vr){
if(vl<=l&&r<=vr) return t[id].sum;
int mid=(l+r)>>1; ll res=0;
pushdown(id);
if(vl<=mid) res=query(lid,l,mid,vl,vr);
if(vr>mid) res+=query(rid,mid+1,r,vl,vr);
return res;
}
ll querym(int id,int l,int r,int vl,int vr){
if(vl<=l&&r<=vr) return t[id].mx;
int mid=(l+r)>>1; ll res=inf;
pushdown(id);
if(vl<=mid) res=querym(lid,l,mid,vl,vr);
if(vr>mid) res=max(res,querym(rid,mid+1,r,vl,vr));
return res;
}
ll queryh(int id,int l,int r,int vl,int vr){
if(vl<=l&&r<=vr) return t[id].hmx;
int mid=(l+r)>>1; ll res=inf;
pushdown(id);
if(vl<=mid) res=queryh(lid,l,mid,vl,vr);
if(vr>mid) res=max(res,queryh(rid,mid+1,r,vl,vr));
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++){
int op,l,r; ll k;
scanf("%d%d%d",&op,&l,&r);
if(op==1) scanf("%lld",&k),add(1,1,n,l,r,k);
else if(op==2) scanf("%lld",&k),change(1,1,n,l,r,k);
else if(op==3) printf("%lld\n",query(1,1,n,l,r));
else if(op==4) printf("%lld\n",querym(1,1,n,l,r));
else printf("%lld\n",queryh(1,1,n,l,r));
}
return 0;
}
李超线段树
最经典应用就是维护一个二维平面直角坐标系，支持动态插入线段（理解为有值域的一次函数 \(y=kx+b\) ），询问已插入线段与直线 \(x=x_0\) 交点的纵坐标最值。
即当 \(x=x_0\) ，求 \(max\) 或 \(min\) { \(k_ix+b_i\) }
对于普通求法的 \(O(n)\) 遍历，如何优化时间复杂度呢？其实就是找一种方法减少有效集合大小，而李超线段树就是如此。
单次查询是 \(O(logn)\) 的，修改是 \(O(log^2n)\) 的。
现在我们需要插入一条线段 f，在这条线段完整覆盖的线段树节点代表的区间中，某些区间的最优线段可能发生改变。
考虑某个被新线段 f 完整覆盖的区间，若该区间无最优线段，则该线段可以直接成为最优线段。
否则，设该区间的中点为 mid，我们拿新线段 f 在中点处的值与原最优线段 g 在中点处的值作比较。
如果新线段 f 更优，则将 f 和 g 交换。
那么现在考虑在中点处 f 不如 g 优的情况：
若在左端点处 f 更优，那么f 和 g 必然在左半区间中产生了交点，递归到左儿子中进行插入；
若在右端点处 f 更优，那么 f 和 g 必然在右半区间中产生了交点，递归到右儿子中进行插入。
若在左右端点处 g 都更优，那么 f 不可能成为答案，不需要继续下传。
这个方法的优势就在于不需要讨论斜率的正负，十分方便。
李超线段树[模板] [HEOI2013]Segment
#include<bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1|1)
#define pdi pair<double,int>
using namespace std;
const double eps=1e-9;//精度问题
const int maxn=1e5+5,mod1=39989,mod2=1000000000;
int n,cnt,ans,t[maxn<<1];
struct node{
double k,b;
}p[maxn];
int cmp(double x,double y){
if(x-y>eps) return 1;
if(y-x>eps) return -1;
return 0;
}
double f(int id,int x){
return p[id].b+p[id].k*x;
}
void add(int x,int y,int xx,int yy){
cnt++;
if(x==xx) p[cnt].k=0,p[cnt].b=max(y,yy);//特判直线斜率不存在的情况！
else p[cnt].k=1.0*(yy-y)/(xx-x),p[cnt].b=y-p[cnt].k*x;
}
void upd(int id,int l,int r,int u){//对线段完全覆盖到的区间进行修改
int &v=t[id],mid=(l+r)>>1;
int tmp=cmp(f(u,mid),f(v,mid));
if(tmp==1||(!tmp&&u<v)) swap(u,v);//交换新旧线段，这里是取地址的
int tl=cmp(f(u,l),f(v,l)),tr=cmp(f(u,r),f(v,r));
if(tl==1||(!tl&&u<v)) upd(lid,l,mid,u);
if(tr==1||(!tr&&u<v)) upd(rid,mid+1,r,u);
}
void change(int id,int l,int r,int vl,int vr,int u){
if(vl<=l&&r<=vr){
upd(id,l,r,u);
return ;
}
int mid=(l+r)>>1;//线段树的查询
if(vl<=mid) change(lid,l,mid,vl,vr,u);
if(mid<vr) change(rid,mid+1,r,vl,vr,u);
}
pdi pmax(pdi x,pdi y){
if(cmp(x.first,y.first)==-1) return y;
else if(cmp(x.first,y.first)==1) return x;
else return x.second<y.second?x:y;
}
pdi query(int id,int l,int r,int pos){
if(r<pos||pos<l) return {0,0};//一种比较方便的写法
double res=f(t[id],pos);
if(l==r) return {res,t[id]};
int mid=(l+r)>>1;
return pmax({res,t[id]},pmax(query(lid,l,mid,pos),query(rid,mid+1,r,pos)));
}
int main(){
scanf("%d",&n);
while(n--){
int op;
scanf("%d",&op);
if(op==1){
int x,y,xx,yy;
scanf("%d%d%d%d",&x,&y,&xx,&yy);
x=(x+ans-1+mod1)%mod1+1;
xx=(xx+ans-1+mod1)%mod1+1;
y=(y+ans-1+mod2)%mod2+1;
yy=(yy+ans-1+mod2)%mod2+1;
if(x>xx) swap(x,xx),swap(y,yy);
add(x,y,xx,yy);
change(1,1,mod1,x,xx,cnt);
}
else{
int x;
scanf("%d",&x);
x=(x+ans-1+mod1)%mod1+1;
ans=query(1,1,mod1,x).second;
printf("%d\n",ans);
}
}
return 0;
}
珂朵莉树
珂朵莉树(老司机树)，一种暴力数据结构，做一些区间修改区间查询的问题，对随机数据比较有效
对一个序列，进行一个区间推平操作（如把一个区间内变为同一个数），然后我们把每段插入到set中自动排序
对于其他操作，还是比较暴力的（对于每个段进行操作）……复杂度在随机数据下大概是O(nlog^2n)
柯朵莉树/老司机树(odt)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,maxn=1e5+5;
int n,m,seed,vmax,a[maxn];
struct node{
int l,r;
mutable int v;//这一段相同元素的值，即使是常量也可以被修改
bool operator<(const node &a) const{
return l<a.l;
}
};
set<node>s;
set<node>::iterator split(int pos){//分裂成[l,pos-1] [pos,r]
set<node>::iterator it=s.lower_bound((node){pos,0,0});
if(it!=s.end()&&it->l==pos) return it;
it--;
if(it->r<pos) return s.end();
int l=it->l,r=it->r,v=it->v;
s.erase(it);
s.insert((node){l,pos-1,v});
return s.insert((node){pos,r,v}).first;
}
void assign(int l,int r,int x){
set<node>::iterator itr=split(r+1),itl=split(l);//注意顺序，否则会因操作r时删去了l的指针而re
s.erase(itl,itr);//前闭后开
s.insert((node){l,r,x});
}
void add(int l,int r,int x){
set<node>::iterator itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++){
it->v+=x;//it是常量迭代器，本来不能下哦i高，但是加了mutable就好了
}
}
struct rankk{
int num,cnt;
bool operator<(const rankk &a)const{
return num<a.num;
}
};
int rnk(int l,int r,int x){
set<node>::iterator itr=split(r+1),itl=split(l);
vector<rankk>v;
for(auto i=itl;i!=itr;i++){
v.push_back((rankk){i->v,i->r-i->l+1});
}
sort(v.begin(),v.end());
int i;
for(i=0;i<v.size();i++){
if(v[i].cnt<x) x-=v[i].cnt;
else break;
}
return v[i].num;
}
int qpow(int x,int y,int mod){
int res=1; x%=mod;
while(y){
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int query(int l,int r,int x,int y){
set<node>::iterator itr=split(r+1),itl=split(l);
int ans=0;
for(auto i=itl;i!=itr;i++){
ans=(ans+qpow(i->v,x,y)*(i->r-i->l+1)%y)%y;
}
return ans;
}
int rnd(){
int ret=seed;
seed=(seed*7+13)%mod;
return ret;
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
for(int i=1;i<=n;i++){
a[i]=rnd()%vmax+1;
s.insert((node){i,i,a[i]});
}
for(int i=1;i<=m;i++){
int opt,l,r,x,y;
opt=rnd()%4+1;
l=rnd()%n+1;
r=rnd()%n+1;
if(l>r) swap(l,r);
if(opt==3) x=rnd()%(r-l+1)+1;
else x=rnd()%vmax+1;
if(opt==4) y=rnd()%vmax+1,printf("%lld\n",query(l,r,x,y));
else if(opt==3) printf("%lld\n",rnk(l,r,x));
else if(opt==2) assign(l,r,x);
else add(l,r,x);
}
return 0;
}