Segment tree beats 的时间复杂度下限为 2log

我们注意到代码的时间复杂度下限为 $O(Q \log^2 n)$

代码：

#include<bits/stdc++.h>
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
struct node{
	int l,r;
	long long val;
	long long mx1,mx2,mxnum;
	long long mi1,mi2,minum;
	long long add;
};
node tr[1000005];
long long a[200005];
const long long inf=1e18;
void nd_add(int root,long long val){
	tr[root].add+=val;
	tr[root].val+=val*(tr[root].r-tr[root].l+1);
	tr[root].mx1+=val;
	tr[root].mi1+=val;
	if(tr[root].mx2!=-inf){
		tr[root].mx2+=val;
	}
	if(tr[root].mi2!=inf){
		tr[root].mi2+=val;
	}
}
void nd_mx(int root,long long val){
	if(tr[root].mx1<=val){
		return;
	}
	tr[root].val=tr[root].val-(tr[root].mx1-val)*tr[root].mxnum;
	if(tr[root].mi1==tr[root].mx1){
		tr[root].mi1=val;
	} 
	if(tr[root].mi2==tr[root].mx1){
		tr[root].mi2=val;
	}
	tr[root].mx1=val; 
}
void nd_mi(int root,long long val){
	 if(tr[root].mi1>=val){
		return;
	}
	tr[root].val=tr[root].val+(val-tr[root].mi1)*tr[root].minum;
	if(tr[root].mx1==tr[root].mi1){
		tr[root].mx1=val;
	} 
	if(tr[root].mx2==tr[root].mi1){
		tr[root].mx2=val;
	}
	tr[root].mi1=val; 
}
void up(int root){
	tr[root].val=tr[ls(root)].val+tr[rs(root)].val;
	tr[root].mx1=max(tr[ls(root)].mx1,tr[rs(root)].mx1);
	tr[root].mi1=min(tr[ls(root)].mi1,tr[rs(root)].mi1); 
	if(tr[ls(root)].mx1==tr[rs(root)].mx1){
		tr[root].mxnum=tr[ls(root)].mxnum+tr[rs(root)].mxnum;
		tr[root].mx2=max(tr[ls(root)].mx2,tr[rs(root)].mx2);
	}
	else if(tr[ls(root)].mx1>tr[rs(root)].mx1){
		tr[root].mxnum=tr[ls(root)].mxnum;
		tr[root].mx2=max(tr[ls(root)].mx2,tr[rs(root)].mx1); 
	}
	else{
		tr[root].mxnum=tr[rs(root)].mxnum;
		tr[root].mx2=max(tr[rs(root)].mx2,tr[ls(root)].mx1); 
	}
	if(tr[ls(root)].mi1==tr[rs(root)].mi1){
		tr[root].minum=tr[ls(root)].minum+tr[rs(root)].minum;
		tr[root].mi2=min(tr[ls(root)].mi2,tr[rs(root)].mi2);
	}
	else if(tr[ls(root)].mi1<tr[rs(root)].mi1){
		tr[root].minum=tr[ls(root)].minum;
		tr[root].mi2=min(tr[ls(root)].mi2,tr[rs(root)].mi1); 
	}
	else{
		tr[root].minum=tr[rs(root)].minum;
		tr[root].mi2=min(tr[rs(root)].mi2,tr[ls(root)].mi1); 
	}
}
void down(int root){
	if(tr[root].add){
		nd_add(ls(root),tr[root].add);
		nd_add(rs(root),tr[root].add);
		tr[root].add=0;
	}
	if(tr[root].mx1<tr[ls(root)].mx1){
		nd_mx(ls(root),tr[root].mx1);
	}
	if(tr[root].mi1>tr[ls(root)].mi1){
		nd_mi(ls(root),tr[root].mi1);
	}
	if(tr[root].mx1<tr[rs(root)].mx1){
		nd_mx(rs(root),tr[root].mx1);
	}
	if(tr[root].mi1>tr[rs(root)].mi1){
		nd_mi(rs(root),tr[root].mi1);
	}
}
void build(int root,int l,int r){
	tr[root].l=l;
	tr[root].r=r;
	if(l==r){
		tr[root].val=a[l];
		tr[root].mx1=tr[root].mi1=a[l];
		tr[root].mxnum=tr[root].minum=1;
		tr[root].mx2=-inf,tr[root].mi2=inf;
		return;
	}
	int mid=(l+r)>>1;
	build(ls(root),l,mid);
	build(rs(root),mid+1,r);
	up(root);
} 
void cg_add(int root,int l,int r,int x,int y,long long w){
	if(x<=l && r<=y){
		nd_add(root,w);
		return;
	}
	down(root);
	int mid=(l+r)>>1;
	if(x<=mid){
		cg_add(ls(root),l,mid,x,y,w);
	}
	if(y>mid){
		cg_add(rs(root),mid+1,r,x,y,w);
	}
	up(root);
}
void cg_max(int root,int l,int r,int x,int y,long long w){
	if(tr[root].mx1<=w){
		return;
	}
	if(x<=l && r<=y){
		if(w>tr[root].mx2){
			nd_mx(root,w); 
			return;
		}
	}
	down(root);
	int mid=(l+r)>>1;
	if(x<=mid){
		cg_max(ls(root),l,mid,x,y,w);
	}
	if(y>mid){
		cg_max(rs(root),mid+1,r,x,y,w);
	}
	up(root);
}
void cg_min(int root,int l,int r,int x,int y,long long w){
	if(tr[root].mi1>=w){
		return;
	}
	if(x<=l && r<=y){
		if(w<tr[root].mi2){
			nd_mi(root,w);
			return;
		}
	}
	down(root);
	int mid=(l+r)>>1;
	if(x<=mid){
		cg_min(ls(root),l,mid,x,y,w);
	}
	if(y>mid){
		cg_min(rs(root),mid+1,r,x,y,w);
	}
	up(root);
}
long long query(int root,int l,int r,int x,int y){
	if(x<=l && r<=y){
		return tr[root].val;
	}
	down(root);
	int mid=(l+r)>>1;
	long long ans=0;
	if(x<=mid){
		ans+=query(ls(root),l,mid,x,y);
	}
	if(y>mid){
		ans+=query(rs(root),mid+1,r,x,y);
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		int op,l,r;
		long long b;
		cin>>op>>l>>r;
		if(op==0){
			cin>>b;
			cg_max(1,1,n,l+1,r,b);
		}
		if(op==1){
			cin>>b;
			cg_min(1,1,n,l+1,r,b);
		}
		if(op==2){
			cin>>b;
			cg_add(1,1,n,l+1,r,b);
		}
		if(op==3){
			cout<<query(1,1,n,l+1,r)<<"\n";
		}
	}
	return 0;
}

题目大意

题目描述清楚，不做赘述

解题思路

区修区查，考虑线段树

$op=2$ $:$ 懒标记即可

$op=3$ $:$ 正常查询即可

$op=0$ $:$ 要求将区间内所有大于 $b$ 的数修改为 $b$ 。考虑记录区间最大值 $mx1$ 与次大值 $mx2$ ，在 $b$ 仅小于最大值时，即 $mx2<b<mx1$ ，对区间进行修改。其中，$mx2$ 严格小于 $mx1$ 。

$op=1$ $:$ 操作类似于 $op=0$ 的情况

注意事项

$①$ $mx1$ $mx2$ 初始化时要设为 $±inf$

$②$ 在修改 $mx1$ 时，要判断与 $mn1$ 或 $mn2$ 是否相等，若相等则要一同修改； $mn1$ 同理

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define MID ((l+r)>>1)
#define N 200010
#define inf 1000000000000000ll
struct node{
	int l,r,sum;
	int mx1,mx2,mxnum;
	int mn1,mn2,mnnum;
	int add;
}tr[N<<2];
int n,q;
int a[N];

void apply_chgmx(int p,int val){
	if(tr[p].mx1<=val)return;
	tr[p].sum+=(val-tr[p].mx1)*tr[p].mxnum;
	if(tr[p].mn1==tr[p].mx1)tr[p].mn1=val;
	if(tr[p].mn2==tr[p].mx1)tr[p].mn2=val;
	tr[p].mx1=val;
}
void apply_chgmn(int p,int val){
	if(tr[p].mn1>=val)return;
	tr[p].sum+=(val-tr[p].mn1)*tr[p].mnnum;
	if(tr[p].mx1==tr[p].mn1)tr[p].mx1=val;
	if(tr[p].mx2==tr[p].mn1)tr[p].mx2=val;
	tr[p].mn1=val;
}
void apply_add(int p,int val){
	tr[p].sum+=val*(tr[p].r-tr[p].l+1);
	tr[p].mx1+=val;
	if(tr[p].mx2!=-inf)tr[p].mx2+=val;
	tr[p].mn1+=val;
	if(tr[p].mn2!=inf)tr[p].mn2+=val;
	tr[p].add+=val;
}

void pushup(int p){
	tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum;
	
	if(tr[lc(p)].mx1==tr[rc(p)].mx1){
		tr[p].mx1=tr[lc(p)].mx1;
		tr[p].mxnum=tr[lc(p)].mxnum+tr[rc(p)].mxnum;
		tr[p].mx2=max(tr[lc(p)].mx2,tr[rc(p)].mx2);
	}
	else if(tr[lc(p)].mx1>tr[rc(p)].mx1){
		tr[p].mx1=tr[lc(p)].mx1;
		tr[p].mxnum=tr[lc(p)].mxnum;
		tr[p].mx2=max(tr[lc(p)].mx2,tr[rc(p)].mx1);
	}
	else{
		tr[p].mx1=tr[rc(p)].mx1;
		tr[p].mxnum=tr[rc(p)].mxnum;
		tr[p].mx2=max(tr[lc(p)].mx1,tr[rc(p)].mx2);
	}
	
	if(tr[lc(p)].mn1==tr[rc(p)].mn1){
		tr[p].mn1=tr[lc(p)].mn1;
		tr[p].mnnum=tr[lc(p)].mnnum+tr[rc(p)].mnnum;
		tr[p].mn2=min(tr[lc(p)].mn2,tr[rc(p)].mn2);
	}
	else if(tr[lc(p)].mn1<tr[rc(p)].mn1){
		tr[p].mn1=tr[lc(p)].mn1;
		tr[p].mnnum=tr[lc(p)].mnnum;
		tr[p].mn2=min(tr[lc(p)].mn2,tr[rc(p)].mn1);
	}
	else{
		tr[p].mn1=tr[rc(p)].mn1;
		tr[p].mnnum=tr[rc(p)].mnnum;
		tr[p].mn2=min(tr[lc(p)].mn1,tr[rc(p)].mn2);
	}
}
void pushdown(int p){
	if(tr[p].add){
		apply_add(lc(p),tr[p].add);
		apply_add(rc(p),tr[p].add);
		tr[p].add=0;
	}
	
	if(tr[lc(p)].mx1>tr[p].mx1)apply_chgmx(lc(p),tr[p].mx1);
	if(tr[lc(p)].mn1<tr[p].mn1)apply_chgmn(lc(p),tr[p].mn1);
	
	if(tr[rc(p)].mx1>tr[p].mx1)apply_chgmx(rc(p),tr[p].mx1);
	if(tr[rc(p)].mn1<tr[p].mn1)apply_chgmn(rc(p),tr[p].mn1);
}
void build(int p,int l,int r){
	if(l==r){
		tr[p]={l,r,a[l],a[l],-inf,1,a[l],inf,1,0};
		return;
	}
	tr[p]={l,r,0,0,0,0,0,0,0,0};
	build(lc(p),l,MID);build(rc(p),MID+1,r);
	pushup(p);
}
void chgmx(int p,int l,int r,int b){
	if(tr[p].r<l||tr[p].l>r)return;
	if(b>=tr[p].mx1)return;
	if(l<=tr[p].l&&tr[p].r<=r){
		if(b>tr[p].mx2){
			apply_chgmx(p,b);
			return;
		}
	}
	pushdown(p);
	chgmx(lc(p),l,r,b);chgmx(rc(p),l,r,b);
	pushup(p);
}
void chgmn(int p,int l,int r,int b){
	if(tr[p].r<l||tr[p].l>r)return;
	if(b<=tr[p].mn1)return;
	if(l<=tr[p].l&&tr[p].r<=r){
		if(b<tr[p].mn2){
			apply_chgmn(p,b);
			return;
		}
	}
	pushdown(p);
	chgmn(lc(p),l,r,b);chgmn(rc(p),l,r,b);
	pushup(p);
}
void chgadd(int p,int l,int r,int b){
	if(tr[p].r<l||tr[p].l>r)return;
	if(l<=tr[p].l&&tr[p].r<=r){
		apply_add(p,b);
		return;
	}
	pushdown(p);
	chgadd(lc(p),l,r,b);chgadd(rc(p),l,r,b);
	pushup(p);
}
int query(int p,int l,int r){
	if(tr[p].r<l||tr[p].l>r)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].sum;
	pushdown(p);
	return query(lc(p),l,r)+query(rc(p),l,r);
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(q--){
		int op,l,r,b;cin>>op>>l>>r;l++;
		if(op==0){
			cin>>b;
			chgmx(1,l,r,b);
		}
		else if(op==1){
			cin>>b;
			chgmn(1,l,r,b);
		}
		else if(op==2){
			cin>>b;
			chgadd(1,l,r,b);
		}
		else{
			cout<<query(1,l,r)<<'\n';
		}
	}
	
	return 0;
}