首页 > 其他分享 >[数据结构]Segment tree(线段树)

[数据结构]Segment tree(线段树)

时间：2023-06-25 21:11:54浏览次数：51  
标签：return val int tree mid seg 数据结构 Segment id

Segment tree(线段树)

1.线段树的结构和思想

线段树基本结构：

image

简单操作：

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;
}

标签：return,val,int,tree,mid,seg,数据结构,Segment,id
From： https://www.cnblogs.com/nannandbk/p/17503963.html

相关文章

  • 洛谷P4178 Tree 题解 树上点分治
    题目链接：https://www.luogu.com.cn/problem/P4178解题思路：点分治模板题。设当前重心为\(u\)，一共有三种不同类型的路径：路径的一个端点恰好是重心\(u\)；路径的两个端点在\(u\)的不同子树中；路径的两个端点在\(u\)的同一个子树中。找到重心\(u\)之后，前两类路径分开求......
  • 3.数据结构与算法复习--线性表
    线性表的定义和特点线性表是具有相同特性的数据元素的一个有限序列（a1,a2,..ai-1,ai,ai+1,...an）a1:线性起点ai-1为ai的直接前驱，ai+1为ai的直接后驱an为线性终点，当n＝0时称为空表线性表同一线性表中的元素必定具有相同特性，数据元素间的关系时线性关系线性表的逻辑特征是：......
  • CodeForces 1842F Tenzing and Tree
    洛谷传送门CF传送门事实上自己方向一直是错的……绝对值不好弄，我一开始的想法是直接去绝对值，但是不可避免地要\(O(n^3)\)。考虑我们直接钦定黑点重心为根，设这个根为\(r\)，设\(sz_i\)为\(i\)子树内黑点数，由重心的性质，可以直接去绝对值，也就是说答案为\(\sum\limits_{i\n......
  • Oracle 安装报SGA size can not be greater than maximum shared memory segment size
    问题现象：问题分析：        从问题现象上来看可以比较清晰的看出是因为系统的内核参数调整问题，导致无法分配正确的内存给SGA；那么这种情况通常是由于我们的/etc/sysctl.conf中配置的内存信息和实际内存信息不符合导致。 我们的物理内存的大小为2G，swap内存的大小为4G;[root@d......
  • sourcetree Authentication failed
    sourcetree的git密码存在mac的钥匙串里面，需要在钥匙串里删除掉对应信息，再次打开就会让你重新输入密码，问题就解决了。参看：https://stackoverflow.com/questions/20953940/authentication-failed-to-bitbucket......
  • B+ tree implemented in Java
    B+树相关介绍B+树是一棵多叉排序树，即每个非叶子节点可以包含多个子节点，其整体结构呈扁平化，所以其非常适配于数据库和操作系统的文件系统中。且B+树能够保持数据的稳定有序，插入和删除都拥有较稳定的对数时间复杂度。B+树的特性：以m阶为例，m表示内部节点即非叶子节点可以包含的......
  • 【数据结构】树的介绍
    前言......
  • Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees
    bfs解法如果是暴力求解的话就每次都扫描一次所有边直到所有点都和树连接优化:每次扫描我们可以发现会重复扫描那些已经存在树中的边了，因此我们可以只扫描还没有存在树中的边且是没扫过的边对于每次更新，比如由点a已经在树中，更新点b，我们只需判断点a被更新到树中点的编号和a-b边的......
  • python入门（六）：数据结构和容器
    Python数据结构和容器指南原文|大纲|首页在Python中，数据结构和容器用于存储和组织数据。它们提供了不同的方式来操作和访问数据，以满足不同的需求。了解Python的数据结构和容器对于编写高效和灵活的代码至关重要。列表（List）列表是Python中最常用的数据结构之一。它是一个......
  • 数据结构课设打飞机————SFML如何配置到VS上
    解决这个问题真的是花费了我好长好长好长时间首先是SFML的版本安装，我用的编译器是VisualStudio2022，下载最新版本的SFML也没什么问题，但关键是这个（下图） 这两个版本的区别是一个32位一个64位我也是无语的今天才知道电脑如果是64位就下64位版本的，我一开始下载的是32位版本的所......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99