Segment tree(线段树)

1.线段树的结构和思想

线段树基本结构：

简单操作：

1.单点修改：时间复杂度O(log n),因为线段树高是O(log n)的，然后会修改这个点到根的路径上的点权，所以是O(log n)的。

2.区间查询(比如：最小值)

实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];

struct node{
	int minv;
}seg[N*4];

void update(int id)
{
	seg[id].minv = min(seg[id*2].minv,seg[id*2+1].minv);
}

void build(int id,int l,int r)
{
	if(l==r)
		seg[id].minv = a[l];
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}


void change(int id,int l,int r,int pos,int val){
	if(l==r)
	{
		seg[id].minv = val;
		//a[pos] = val;已经把a数组记到线段树里面了，之后不用了，可以不写
	}
	else
	{
		int mid = (l+r)/2;
		if(pos<=mid)change(id*2,l,mid,pos,val);
		else change(id*2+1,mid+1,r,pos,val);
		//重要！改完之后记得更新节点的信息
		update(id);
	}
}

//O(logn)
int query(int id,int l,int r,int x,int y)
{
	if(l==x&&r==y)return seg[id].minv; 
	int mid = (l+r)/2;
	if(y<=mid)return query(id*2,l,mid,x,y);
	else if(x>mid)return query(id*2+1,mid+1,r,x,y);
	else{
		return min(query(id*2,l,mid,x,mid),query(id*2+1,mid+1,r,mid+1,y));
	}
}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}
		else
		{
			int l,r;
			cin>>l>>r;
			cout<<query(1,1,n,l,r)<<endl;
		}
	}
	return 0;
}

2.单点修改，区间查询(eg1)

线段树1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];
struct info
{
	int minv,mincnt;
};

info operator+(const info &l,const info &r)
{
	info a;
	a.minv = min(l.minv,r.minv);
	if(l.minv==r.minv)a.mincnt = l.mincnt + r.mincnt;
	else if(l.minv<r.minv)a.mincnt = l.mincnt;
	else a.mincnt = r.mincnt;
	return a;
}

struct node{
	info val;
}seg[N*4];

void update(int id)
{
	seg[id].val = seg[id*2].val+seg[id*2+1].val;
}

void build(int id,int l,int r)
{
	if(l==r)
		seg[id].val = {a[l],1};
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}


void change(int id,int l,int r,int pos,int val){
	if(l==r)
	{
		seg[id].val = {val,1};
	}
	else
	{
		int mid = (l+r)/2;
		if(pos<=mid)change(id*2,l,mid,pos,val);
		else change(id*2+1,mid+1,r,pos,val);
		//重要！改完之后记得更新节点的信息
		update(id);
	}
}

//O(logn)
info query(int id,int l,int r,int x,int y)
{
	if(l==x&&r==y)return seg[id].val; 
	int mid = (l+r)/2;
	if(y<=mid)return query(id*2,l,mid,x,y);
	else if(x>mid)return query(id*2+1,mid+1,r,x,y);
	else{
		return query(id*2,l,mid,x,mid)+query(id*2+1,mid+1,r,mid+1,y);
	}

}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}
		else
		{
			int l,r;
			cin>>l>>r;
			auto ans = query(1,1,n,l,r);
			cout<<ans.minv<<" "<<ans.mincnt<<endl;
		}
	}
	return 0;
}

2.1.复杂的信息合并(eg2)

线段树2

//最大字段和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];
struct info
{
	ll mss,mpre,msuf,s;
	int minv,mincnt;
	info(){};
	info(int a):mss(a),mpre(a),msuf(a),s(a){};
};

info operator+(const info &l,const info &r)
{
	info a;
	a.mss = max({l.mss,r.mss,l.msuf+r.mpre});
	a.mpre = max(l.mpre,l.s+r.mpre);
	a.msuf = max(r.msuf,r.s+l.msuf);
	a.s = l.s+r.s;
	a.minv = min(l.minv,r.minv);
	return a;
}

struct node{
	info val;
}seg[N*4];

void update(int id)
{
	seg[id].val = seg[id*2].val+seg[id*2+1].val;
}

void build(int id,int l,int r)
{
	if(l==r)
		seg[id].val = info(a[l]);
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}


void change(int id,int l,int r,int pos,int val){
	if(l==r)
	{
		seg[id].val = info(val);
	}
	else
	{
		int mid = (l+r)/2;
		if(pos<=mid)change(id*2,l,mid,pos,val);
		else change(id*2+1,mid+1,r,pos,val);
		//重要！改完之后记得更新节点的信息
		update(id);
	}
}

//O(logn)
info query(int id,int l,int r,int x,int y)
{
	if(l==x&&r==y)return seg[id].val; 
	int mid = (l+r)/2;
	if(y<=mid)return query(id*2,l,mid,x,y);
	else if(x>mid)return query(id*2+1,mid+1,r,x,y);
	else{
		return query(id*2,l,mid,x,mid)+query(id*2+1,mid+1,r,mid+1,y);
	}

}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}
		else
		{
			int l,r;
			cin>>l>>r;
			auto ans = query(1,1,n,l,r);
			cout<<ans.mss<<endl;
		}
	}
	return 0;
}

3.1区间打标记，以及下传(eg3)

线段树打标记1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];

struct node{
	ll t,val;
}seg[N*4];

void update(int id)
{
	seg[id].val = max(seg[id*2].val,seg[id*2+1].val);
}

void settag(int id,ll t)
{
	seg[id].val = seg[id].val+t;
	seg[id].t = seg[id].t + t;
}

void pushdown(int id)
{
	if(seg[id].t!=0)
	{
		settag(id*2,seg[id].t);
		settag(id*2+1,seg[id].t);
		seg[id].t = 0;
	}
}

void build(int id,int l,int r)
{
	if(l==r)
		seg[id].val = {a[l]};
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}


void modify(int id,int l,int r,int x,int y,ll t){
	if(l==x&&r==y)
	{
		settag(id,t);
		return;
	}
	int mid = (l+r)/2;
	pushdown(id);
	if(y<=mid) modify(id*2,l,mid,x,y,t);
	else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
	else{
		modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
	}
	update(id);
}

//O(logn)
ll query(int id,int l,int r,int x,int y)
{
	if(l==x&&r==y)return seg[id].val; 
	int mid = (l+r)/2;
	pushdown(id);
	if(y<=mid)return query(id*2,l,mid,x,y);
	else if(x>mid)return query(id*2+1,mid+1,r,x,y);
	else{
		return max(query(id*2,l,mid,x,mid),query(id*2+1,mid+1,r,mid+1,y));
	}

}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r;
			ll d;
			cin>>l>>r>>d;
			modify(1,1,n,l,r,d);
		}
		else
		{
			int l,r;
			cin>>l>>r;
			auto ans = query(1,1,n,l,r);
			cout<<ans<<endl;
		}
	}
	return 0;
}

3.2复杂的标记问题，标记的顺序(eg4)

给\(n\)个数\(a_1,a_2,a_3,…,a_n\)。

支持\(q\)个操作：

1. 1 l r d，令所有的\(a_i(l≤i≤r)\)加上\(d\)。
2. 2 l r d，令所有的\(a_i(l≤i≤r)\)乘上\(d\)。
3. 3 l r d，令所有的\(a_i(l≤i≤r)\)等于\(d\)。
4. 4 l r，查询\((\sum_{i = l}^{r})\bmod (109+7)\)。

线段树打标记2

思路：我们对于那么多操作，搞好几套标记显然是不太好的，那我们可以统一一下，把所有的\(a[i]\)变成\(a[i]*mul+add\)的标记，一开始默认$mul = 1,add = 0 $。

对于上述标记可以转化为：

1. \(*1+d\)
2. \(*d+0\)
3. \(*0+d\)

①更新信息：

对于\(a1,a1...an\)

原来总和是\(s\)。\(ai——>ai*x+y\)，那么\(s——>s*x+size*y\)

②标记合并(有时间顺序的)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
const ll mod = 1e9+7;
int n,q;
int a[N];

struct tag
{
	ll mul,add;
};

tag operator+(const tag &t1,const tag &t2)
{
	//(x*t1.mul+t1.add)*t2.mul+t2.add)
	return {t1.mul*t2.mul%mod,(t1.add*t2.mul+t2.add)%mod};
}
struct node{
	tag t;
	ll val;
	int sz;
}seg[N*4];

void update(int id)
{
	seg[id].val = (seg[id*2].val+seg[id*2+1].val)%mod;
}

void settag(int id,tag t)
{
	seg[id].val = (seg[id].val*t.mul+seg[id].sz*t.add)%mod;
	seg[id].t = seg[id].t + t;
}

void pushdown(int id)
{
	if(seg[id].t.mul!=1||seg[id].t.add!=0)
	{
		settag(id*2,seg[id].t);
		settag(id*2+1,seg[id].t);
		seg[id].t.add = 0;
		seg[id].t.mul = 1;
	}
}

void build(int id,int l,int r)
{
	seg[id].t = {1,0};
	seg[id].sz = r-l+1;
	if(l==r)
		seg[id].val = {a[l]};
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}


void modify(int id,int l,int r,int x,int y,tag t){
	if(l==x&&r==y)
	{
		settag(id,t);
		return;
	}
	int mid = (l+r)/2;
	pushdown(id);
	if(y<=mid) modify(id*2,l,mid,x,y,t);
	else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
	else{
		modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
	}
	update(id);
}

//O(logn)
ll query(int id,int l,int r,int x,int y)
{
	if(l==x&&r==y)return seg[id].val; 
	int mid = (l+r)/2;
	pushdown(id);
	if(y<=mid)return query(id*2,l,mid,x,y);
	else if(x>mid)return query(id*2+1,mid+1,r,x,y);
	else{
		return (query(id*2,l,mid,x,mid)+query(id*2+1,mid+1,r,mid+1,y))%mod;
	}

}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op<=3)
		{
			int l,r,d;
			cin>>l>>r>>d;
			if(op==1)
				modify(1,1,n,l,r,(tag){1,d});
			else if(op==2)
				modify(1,1,n,l,r,(tag){d,0});
			else 
				modify(1,1,n,l,r,(tag){0,d});
		}
		else
		{
			int l,r;
			cin>>l>>r;
			auto ans = query(1,1,n,l,r);
			cout<<ans<<endl;
		}
	}
	return 0;
}

4.线段树上二分(eg5)

线段树上二分

给\(n\)个数\(a1,a2,a3,…,an\)。

支持\(q\)个操作：

1. 1 x d，修改\(ax=d\)。
2. 2 l r d， 查询\(al,al+1,al+2,…,ar\)中大于等于\(d\)的第一个数的下标，如果不存在，输出\(−1\)。也就是说，求最小的\(i(l≤i≤r)\)满足\(ai≥d\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];

struct node{
	int val;
}seg[N*4];

void update(int id)
{
	seg[id].val = max(seg[id*2].val,seg[id*2+1].val);
}

void build(int id,int l,int r)
{
	if(l==r)
		seg[id].val = a[l];
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}


void change(int id,int l,int r,int pos,int val){
	if(l==r)
	{
		seg[id].val = val;
		return;
	}
	int mid = (l+r)/2;
	if(pos<=mid)change(id*2,l,mid,pos,val);
	else change(id*2+1,mid+1,r,pos,val);
	update(id);
}

int search(int id,int l,int r,int x,int y,int d)
{
	if(l==x&&r==y)
	{
		if(seg[id].val<d)return -1;
		else
		{
			if(l==r)return l;
			int mid = (l+r)>>1;
			if(seg[id*2].val>=d)return search(id*2,l,mid,x,mid,d);
			else return search(id*2+1,mid+1,r,mid+1,y,d);
		}
	}
	int mid = (l+r)/2;
	if(y<=mid)return search(id*2,l,mid,x,y,d);
	else if(x>mid)return search(id*2+1,mid+1,r,x,y,d);
	else{
		int pos = search(id*2,l,mid,x,mid,d);
		if(pos==-1)
			return search(id*2+1,mid+1,r,mid+1,y,d);
		else 
			return pos; 
	}
}

int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}
		else
		{
			int l,r,d;
			cin>>l>>r>>d;
			auto ans = search(1,1,n,l,r,d);
			cout<<ans<<endl;
		}
	}
	return 0;
}

5.区间最值操作

笼统地来说，区间最值操作指，将区间\([l,r]\)的数全部对\(x\)取 \(min\) 或 \(max\)，即 \(a_i = min(a_i,x)\) 或\(a_i = min(a_i,x)\)。

eg1.Gorgeous Sequence

[吉司机的ppt][[https://files.cnblogs.com/files/wawawa8/Segment_tree_Beats!.pdf]

维护一个序列 a：

1.0 l r t,对于任意i属于l到r,a[i] = min(a[i],t);
2.1 l r 输出区间 [l,r] 中的最大值。
3.2 l r 输出区间和。

思路：

对于区间取min，意味着该区间内>t的数要变。也就是说，操作不是对整个区间，而是【区间内大于t的数】。

那么我们需要维护的信息是：区间最大值，次大值，区间和，区间最大值的个数。

TIPS:

我们可以换种方式来考虑：把线段树上每一个节点的最大值看成是区间取min标记，次大值看成是子树中标记的最大值。因为每次更新只会更新到(区间次大值<t<区间最大值)的情况，然后取修改max和sum。一旦进入子树，就必须先更新子树的sum和max，就需要先pushdown，把当前区间信息传给子树。

对于\(t\)取\(min\)，我们讨论一下：

1. 如果区间最大值都比\(t\)小，那么整个操作无意义，直接\(return\)即可。
2. 如果次大值比\(t\)小，最大值比t大，我们只需要更新区间最大值为\(t\)。并且更新区间和为\(sum+cnt*(t-max)\)，并打上一个标记。
3. 如果次大值小于等于\(t\)，那我们不能确定有多少个要被更新。那我们就暴力递归下去(搜索它的子树)，然后再\(update\)信息回来。

时间复杂度:\(O(mlogn)\)

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int N = 1e6+10;
char nc() {
  static char buf[1000000], *p = buf, *q = buf;
  return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
             ? EOF
             : *p++;
}
int rd() {
  int res = 0;
  char c = nc();
  while (!isdigit(c)) c = nc();
  while (isdigit(c)) res = res * 10 + c - '0', c = nc();
  return res;
}


ll n,q;
int a[N];

struct node{
	ll sum;
	int mx,se;
	int t,cnt;
}seg[N*4];

void update(int id)
{
	const int ls = id<<1,rs = id<<1|1;
	seg[id].sum = seg[ls].sum + seg[rs].sum;
	if(seg[ls].mx==seg[rs].mx)
	{
		seg[id].mx = seg[ls].mx;
		seg[id].se = max(seg[ls].se,seg[rs].se);
		seg[id].cnt = seg[ls].cnt+seg[rs].cnt;
	}
	else if(seg[ls].mx>seg[rs].mx)
	{
		seg[id].mx = seg[ls].mx;
		seg[id].se = max(seg[ls].se,seg[rs].mx);
		seg[id].cnt = seg[ls].cnt;
	}
	else
	{
		seg[id].mx = seg[rs].mx;
		seg[id].se = max(seg[ls].mx,seg[rs].se);
		seg[id].cnt = seg[rs].cnt;
	}
}

void settag(int id,int t)
{
	if(seg[id].mx<=t)return;
	seg[id].sum += (1ll*t - seg[id].mx)*seg[id].cnt;
	seg[id].mx = seg[id].t = t;
}


void pushdown(int id)
{
	if(seg[id].t!=-1)
	{
		settag(id*2,seg[id].t);
		settag(id*2+1,seg[id].t);
		seg[id].t = -1;
	}
}

void build(int id,int l,int r)
{
	seg[id].t =-1;
	if(l==r)
		seg[id].mx = seg[id].sum = a[l],seg[id].cnt = 1,seg[id].se = -1;
	else 
	{
		int mid = (l+r)>>1;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}

void modify(int id,int l,int r,int x,int y,ll t){
	if(seg[id].mx<=t)return;
	if(x==l&&r==y&&seg[id].se<t)return settag(id,t);
	int mid = (l+r)>>1;
	pushdown(id);
	if(y<=mid) modify(id*2,l,mid,x,y,t);
	else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
	else{
		modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
	}
	update(id);
}


int query(int id,int l,int r,int x,int y)
{
	if(l==x&&r==y)return seg[id].mx; 
	int mid = (l+r)>>1;
	pushdown(id);
	if(y<=mid)return query(id*2,l,mid,x,y);
	else if(x>mid)return query(id*2+1,mid+1,r,x,y);
	else{
		return max(query(id*2,l,mid,x,mid),query(id*2+1,mid+1,r,mid+1,y));
	}

}

ll query2(int id,int l,int r,int x,int y)
{
	if(l==x&&r==y)return seg[id].sum; 
	int mid = (l+r)>>1;
	pushdown(id);
	if(y<=mid)return query2(id*2,l,mid,x,y);
	else if(x>mid)return query2(id*2+1,mid+1,r,x,y);
	else{
		return query2(id*2,l,mid,x,mid)+query2(id*2+1,mid+1,r,mid+1,y);
	}

}

int main()
{
	int t;
	t = rd();
	while(t--)
	{
		n = rd(), q = rd();
		for(int i = 1;i<=n;i++)
			a[i] = rd();
		build(1,1,n);
		for(int i = 1;i<=q;i++)
		{
			int op;	
			op = rd();
			if(op==0)
			{
				int l,r;
				int d;
				l = rd(), r = rd(), d = rd();
				modify(1,1,n,l,r,d);
			}
			else if(op==1)
			{
				int l,r;
				l = rd(), r = rd();
				printf("%d\n",query(1,1,n,l,r));
			}
			else
			{
				int l,r;
				l = rd(), r = rd();
				printf("%lld\n",query2(1,1,n,l,r));


			}
		}
	}
	return 0;
}

eg2(吉司机线段树模板题).BZOJ4695 最假女选手

[吉司机的ppt][[https://files.cnblogs.com/files/wawawa8/Segment_tree_Beats!.pdf]

给定一个长度为 N序列，编号从1 到 N。要求支持下面几种操作：

1.给一个区间[L,R] 加上一个数x

2.把一个区间[L,R] 里小于x 的数变成x

3.把一个区间[L,R] 里大于x 的数变成x

4.求区间[L,R] 的和

5.求区间[L,R] 的最大值

6.求区间[L,R] 的最小值

思路：

跟上一题同样的方法，我们取维护：最大mx，次大mx2，最小mn，次小mn2的值，和最大cmx和最小cmn的个数，区间和sum。还需要维护区间取min（tmn），取max和区间加的标记(tmx)。这里就会涉及到标记下传的顺序了。

策略：

1. 认为区间加优先级最大，取min和max一样
2. 对于某个节点加一个t标记，除了用t更新区间和信息，还需要用整个t更新区间取max和取min
3. 对于一个节点取min，除了更新区间和信息，还有注意与区间max的标记比较。如果t小于区间max的标记，则最后所有数都会变成t，那么吧区间max的标记也变成t，否则不管。

细节：

1. 注意取min和取max时候的特判，一个数可能即是最大值又是次小值这种(代码里有写)。
2. 卡常，加快读

时间复杂度：\(O(nlogn+mlog^2n)\)

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int rd() {
  char act = 0;
  int f = 1, x = 0;
  while (act = getchar(), act < '0' && act != '-')
    ;
  if (act == '-') f = -1, act = getchar();
  x = act - '0';
  while (act = getchar(), act >= '0') x = x * 10 + act - '0';
  return x * f;
}

const int N = 5e5 + 5, SZ = N << 2, inf = 0x7fffffff;

int n,m;
int a[N];

struct node
{
  int mx,mx2,mn,mn2,cmx,cmn,tmx,tmn,t;
  ll sum;
}seg[N * 4];


void update(int id)
{
  const int ls = id<<1,rs = id<<1|1;
  seg[id].sum = seg[ls].sum + seg[rs].sum;
  if(seg[ls].mx==seg[rs].mx)
  {
    seg[id].mx = seg[ls].mx,seg[id].cmx = seg[ls].cmx+seg[rs].cmx;
    seg[id].mx2 = max(seg[ls].mx2,seg[rs].mx2);
  }
  else if(seg[ls].mx>seg[rs].mx)
  {
    seg[id].mx = seg[ls].mx,seg[id].cmx = seg[ls].cmx;
    seg[id].mx2 = max(seg[ls].mx2,seg[rs].mx);
  }
  else
  {
    seg[id].mx = seg[rs].mx,seg[id].cmx = seg[rs].cmx;
    seg[id].mx2 = max(seg[ls].mx,seg[rs].mx2);
  }


  if(seg[ls].mn==seg[rs].mn)
  {
    seg[id].mn = seg[ls].mn,seg[id].cmn = seg[ls].cmn+seg[rs].cmn;
    seg[id].mn2 = min(seg[ls].mn2,seg[rs].mn2);
  }
  else if(seg[ls].mn<seg[rs].mn)
  {
    seg[id].mn = seg[ls].mn,seg[id].cmn = seg[ls].cmn;
    seg[id].mn2 = min(seg[ls].mn2,seg[rs].mn);
  }
  else
  {
    seg[id].mn = seg[rs].mn,seg[id].cmn = seg[rs].cmn;
    seg[id].mn2 = min(seg[ls].mn,seg[rs].mn2);
  }
}


void push_add(int id,int l,int r,int t)
{
   //更新加法标记的同时更新取min和取max的标记
  seg[id].sum += (r-l+1ll)*t;
  seg[id].mx += t,seg[id].mn += t;
  if(seg[id].mx2 != -inf)seg[id].mx2 += t;
  if (seg[id].mn2 != inf)seg[id].mn2 += t;
  if(seg[id].tmx != -inf)seg[id].tmx += t;
  if(seg[id].tmn != inf)seg[id].tmn += t;
  seg[id].t += t;
}



void push_min(int id,int t)
{
   //取min的时候不仅是改最大值，最小值也可能改，注意比较取max的标记
  if(seg[id].mx<=t)return;
  seg[id].sum += (t*1ll-seg[id].mx)*seg[id].cmx;
  if(seg[id].mn2 == seg[id].mx)//次小等于最大
    seg[id].mn2 = t;
  if(seg[id].mn==seg[id].mx)//最小等于最大
    seg[id].mn = t;
  if(seg[id].tmx>t)seg[id].tmx = t;//更新取max标记
  seg[id].mx = t,seg[id].tmn = t;
}

void push_max(int id,int t)
{
  if(seg[id].mn>t)return;
  seg[id].sum += (t*1ll-seg[id].mn)*seg[id].cmn;
  if(seg[id].mx2 == seg[id].mn)//次大等于最小
    seg[id].mx2 = t;
  if(seg[id].mx==seg[id].mn)//最小等于最大
    seg[id].mx = t;
  if(seg[id].tmn<t)seg[id].tmn = t;//更新取min标记
  seg[id].mn = t,seg[id].tmx = t;
}


void pushdown(int id,int l,int r)
{
  const int ls = id<<1,rs = id<<1|1,mid = (l+r)>>1;
  if(seg[id].t)
    push_add(ls,l,mid,seg[id].t),push_add(rs,mid+1,r,seg[id].t);
  if(seg[id].tmx != -inf)push_max(ls,seg[id].tmx),push_max(rs,seg[id].tmx);
  if(seg[id].tmn != inf)push_min(ls,seg[id].tmn),push_min(rs,seg[id].tmn);
  seg[id].t = 0,seg[id].tmx  = -inf,seg[id].tmn = inf;
}


void build(int id,int l,int r)
{
  seg[id].tmn = inf,seg[id].tmx = -inf;
  if(l==r)
  {
    seg[id].sum = seg[id].mx = seg[id].mn = a[l];
    seg[id].mx2 = -inf,seg[id].mn2 = inf;
    seg[id].cmx = seg[id].cmn = 1;
    return;
  }
  int mid = (l+r)>>1;
  build(id*2,l,mid),build(id*2+1,mid+1,r);
  update(id);
}


void add(int id,int l,int r,int x,int y,int t)
{
  if(y < l || r < x)return;
  if(x==l&&r==y)return push_add(id,l,r,t);//!!注意是return
  int mid = (l+r)>>1;
  pushdown(id,l,r);
  if(y<=mid) add(id*2,l,mid,x,y,t);
  else if(x>mid) add(id*2+1,mid+1,r,x,y,t);
  else{
    add(id*2,l,mid,x,mid,t),add(id*2+1,mid+1,r,mid+1,y,t);
  }
  update(id);
}


void tomin(int id,int l,int r,int x,int y,int t)
{
  if(y < l || r < x||seg[id].mx<=t)return;
  if(x==l&&r==y&&seg[id].mx2<t)return push_min(id,t);
  int mid = (l+r)>>1;
  pushdown(id,l,r);
  if(y<=mid) tomin(id*2,l,mid,x,y,t);
  else if(x>mid) tomin(id*2+1,mid+1,r,x,y,t);
  else{
    tomin(id*2,l,mid,x,mid,t),tomin(id*2+1,mid+1,r,mid+1,y,t);
  }
  update(id);
}


void tomax(int id,int l,int r,int x,int y,int t)
{
  if(y < l || r < x||seg[id].mn>=t)return;
  if(x<=l&&r<=y&&seg[id].mn2>t)return push_max(id,t);
  int mid = (l+r)>>1;
  pushdown(id,l,r);
  if(y<=mid) tomax(id*2,l,mid,x,y,t);
  else if(x>mid) tomax(id*2+1,mid+1,r,x,y,t);
  else{
    tomax(id*2,l,mid,x,mid,t),tomax(id*2+1,mid+1,r,mid+1,y,t);
  }
  update(id);
}


ll qsum(int id,int l,int r,int x,int y)
{
  if(y < l || r < x)return 0;
  if(x<=l&&r<=y)return seg[id].sum;
  int mid = (l+r)>>1;
  pushdown(id,l,r);
  if(y<=mid) qsum(id*2,l,mid,x,y);
  else if(x>mid) qsum(id*2+1,mid+1,r,x,y);
  else{
    return qsum(id*2,l,mid,x,mid)+qsum(id*2+1,mid+1,r,mid+1,y);
  }
}


ll qmax(int id,int l,int r,int x,int y)
{
  if(y < l || r < x)return -inf;
  if(x<=l&&r<=y)return seg[id].mx;
  int mid = (l+r)>>1;
  pushdown(id,l,r);
  if(y<=mid) qmax(id*2,l,mid,x,y);
  else if(x>mid) qmax(id*2+1,mid+1,r,x,y);
  else{
    return max(qmax(id*2,l,mid,x,mid),qmax(id*2+1,mid+1,r,mid+1,y));
  }
}

ll qmin(int id,int l,int r,int x,int y)
{
  if(y < l || r < x)return inf;
  if(x<=l&&r<=y)return seg[id].mn;
  int mid = (l+r)>>1;
  pushdown(id,l,r);
  if(y<=mid) qmin(id*2,l,mid,x,y);
  else if(x>mid) qmin(id*2+1,mid+1,r,x,y);
  else{
    return min(qmin(id*2,l,mid,x,mid),qmin(id*2+1,mid+1,r,mid+1,y));
  }
}

int main()
{
  n = rd();
  for(int i = 1;i<=n;i++)a[i] = rd();
  build(1,1,n);
  m = rd();
  for(int i = 1;i<=m;i++)
  {
    int op,l,r,x;
    op = rd(),l = rd(),r = rd();
    if(op<=3)
      x = rd();
    if(op==1)
      add(1,1,n,l,r,x);
    else if(op==2)
      tomax(1,1,n,l,r,x);
    else if(op==3)
      tomin(1,1,n,l,r,x);
    else if(op==4)
      printf("%lld\n",qsum(1,1,n,l,r));
    else if(op==5)
       printf("%lld\n",qmax(1,1,n,l,r));
    else
       printf("%lld\n",qmin(1,1,n,l,r));
  }
  return 0;
}

本栏目推荐文章
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库
• openpyxl模块--------------------------------重复数据
• Django客户端应用1向服务端应用2发送POST请求并接收解析数据
• 数据可视化是如何帮助我们高效了解数据的？

线段 数据结构 Segment 结构 数据线段 数据结构segment结构 线段 数据结构 结构 笔记 线段 数据结构 结构 数据 线段 数据结构 司机 结构 线段 模板segment heoi greenplum故障segment数据库 线段segment heoi 2013 segment单位 数据okio 线段 数组segment tree labeled segment数据rlhf