专栏文章

烟台五一培训day2笔记

ccxk_ctrl
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipfpsmm
此快照首次捕获于
2025/12/03 11:15
3 个月前
此快照最后确认于
2025/12/03 11:15
3 个月前
查看原文
线段树
线段树性质： 修改操作&询问操作？
用来针对区间操作的问题
线段树基础结构：
本质上是一棵二叉树，一定有左右儿子
N=8：1-8的区间，每个节点都有两个区间，就是上面节点区间从中间直接砍掉
只要区间长度没有达到1，就可以继续往左右两边分
线段树有log n层
和分治的分法其实差不多
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],sum[400005],tag[400005],n,m;
int ls(int x){
	return x*2;
} 
int rs(int x){
	return x*2+1;
}
void pushup(int x){
	sum[x]=sum[ls(x)]+sum[rs(x)];
}
void add(int x,int l,int r,int k){
	sum[x]+=(r-l+1)*k;
	tag[x]+=k;
}
void pushdown(int x,int l,int r){
	if(tag[x]!=0){
		int mid=l+r>>1;
		add(ls(x),l,mid,tag[x]);
		add(rs(x),mid+1,r,tag[x]);
		tag[x]=0;
	}
}
void build(int x,int l,int r){
	if(l==r){
		sum[x]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	pushup(x);
}
void update(int x,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		return add(x,l,r,k);
	}
	pushdown(x,l,r);
	int mid=l+r>>1;
	if(L<=mid)update(ls(x),l,mid,L,R,k);
	if(mid<R)update(rs(x),mid+1,r,L,R,k);
	pushup(x); 
}
int query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return sum[x];
	}
	pushdown(x,l,r);
	int mid=l+r>>1,ans=0;
	if(L<=mid)ans+=query(ls(x),l,mid,L,R);
	if(mid<R)ans+=query(rs(x),mid+1,r,L,R);
	return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		int opt;
		cin>>opt;
		if(opt==1){
			int x,y,k;
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}
		else{
			int x,y;
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
}
注意理解建树和询问的过程
线段树plus
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],sum[400005],mu[400005],ji[400005],n,q,m;
int ls(int x){
	return x<<1;
}
int rs(int x){
	return (x<<1)|1;
}
void mul(int x,int l,int r,int k){
	(mu[x]*=k)%=m;;
	(ji[x]*=k)%=m;
	(sum[x]*=k)%=m;
}
void add(int x,int l,int r,int k){
	(ji[x]+=k)%=m;
	(sum[x]+=k*(r-l+1))%=m;
}
void pushup(int x){
	(sum[x]=sum[ls(x)]+sum[rs(x)])%=m;
}
void pushdown(int x,int l,int r){
	if(mu[x]!=1){
		int m=l+r>>1;
		mul(ls(x),l,m,mu[x]);
		mul(rs(x),m+1,r,mu[x]);
		mu[x]=1;
	}
	if(ji[x]!=0){
		int m=l+r>>1;
		add(ls(x),l,m,ji[x]);
		add(rs(x),m+1,r,ji[x]);
		ji[x]=0;
	}
}
void build(int x,int l,int r){
	if(l==r){
		sum[x]=a[l];
		return;
	}
	int m=l+r>>1;
	mu[x]=1;
	build(ls(x),l,m);
	build(rs(x),m+1,r);
	pushup(x);
}
void ch(int x,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		return mul(x,l,r,k);
	}
	pushdown(x,l,r);
	int m=l+r>>1;
	if(L<=m)ch(ls(x),l,m,L,R,k);
	if(m<R)ch(rs(x),m+1,r,L,R,k);
	pushup(x);
}
void jia(int x,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		return add(x,l,r,k);
	}
	pushdown(x,l,r);
	int m=l+r>>1;
	if(L<=m)jia(ls(x),l,m,L,R,k);
	if(m<R)jia(rs(x),m+1,r,L,R,k);
	pushup(x);
}
int query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return sum[x];
	}
	pushdown(x,l,r);
	int m=l+r>>1;
	int ans=0;
	if(L<=m)(ans+=query(ls(x),l,m,L,R))%=::m;
	if(m<R)(ans+=query(rs(x),m+1,r,L,R))%=::m;
	return ans;
}
signed main(){
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(q--){
		int opt;
		cin>>opt;
		if(opt==1){
			int x,y,k;
			cin>>x>>y>>k;
			ch(1,1,n,x,y,k);
		}
		else if(opt==2){
			int x,y,k;
			cin>>x>>y>>k;
			jia(1,1,n,x,y,k);
		}
		else{
			int x,y;
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
}
注意线段树的查询写法和计算顺序，先乘法后加法
扶苏的问题
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1000005;
int sum[4*maxn],tag[4*maxn],tag2[4*maxn],a[maxn],n,m; 
int ls(int x){
	return x*2;
}
int rs(int x){
	return x*2+1;
}
void pushup(int x){
	sum[x]=max(sum[ls(x)],sum[rs(x)]);
}
void build(int x,int l,int r){
	if(l==r){
		sum[x]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	pushup(x);
}
void add(int x,int l,int r,int k){
	tag[x]=k;
	tag2[x]=0;
	sum[x]=k; 
}
void add2(int x,int l,int r,int k){
	tag2[x]+=k;
	sum[x]+=k;
}
void pushdown(int x,int l,int r){
	if(tag[x]!=-1e18){
		int mid=l+r>>1;
		add(ls(x),l,mid,tag[x]);
		add(rs(x),mid+1,r,tag[x]);
		tag[x]=-1e18;
	}
		int mid=l+r>>1;
		add2(ls(x),l,mid,tag2[x]);
		add2(rs(x),mid+1,r,tag2[x]);
		tag2[x]=0;
}
void pt(int x,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		return add(x,l,r,k);
	}
	pushdown(x,l,r);
	int mid=l+r>>1;
	if(L<=mid)pt(ls(x),l,mid,L,R,k);
	if(R>mid)pt(rs(x),mid+1,r,L,R,k);
	pushup(x);
}
void xj(int x,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		return add2(x,l,r,k);
	}
	pushdown(x,l,r);
	int mid=l+r>>1;
	if(L<=mid)xj(ls(x),l,mid,L,R,k);
	if(mid<R)xj(rs(x),mid+1,r,L,R,k);
	pushup(x);
}
int query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return sum[x];
	}
	int mid=l+r>>1;
	pushdown(x,l,r);
	int ans=-1e18;
	if(L<=mid)ans=max(query(ls(x),l,mid,L,R),ans);
	if(mid<R)ans=max(query(rs(x),mid+1,r,L,R),ans);
	return ans;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=4*n;i++){
		tag[i]=sum[i]=-1e18;
	}
	build(1,1,n);
	while(m--){
		int opt;
		scanf("%lld",&opt);
		if(opt==1){
			int x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			pt(1,1,n,x,y,k);
		}
		else if(opt==2){
			int x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			xj(1,1,n,x,y,k);
		}
		else{
			int x,y;
			scanf("%lld%lld",&x,&y);
			cout<<query(1,1,n,x,y)<<'\n';
		}
	}
}
和上面操作类似，注意题意的改法
方差
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	register int x=0;
	register bool f=0;
	register char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=100005;
struct _{
	int sum;
	bool tag;
}t[maxn<<2];
int a[maxn],n,m;
void pushup(int o){
	t[o].sum=t[o<<1].sum+t[o<<1|1].sum;
	if(t[o<<1].tag && t[o<<1|1].tag) t[o].tag=1;
	else t[o].tag=0;
}
void build(int o,int l,int r){
	if(l==r){
		t[o].sum=a[l];
		if(a[l]==0 || a[l]==1) t[o].tag=1;
		else t[o].tag=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);
	pushup(o);
}
void change(int o,int l,int r,int ql,int qr){
	if(l==r){
		t[o].sum=sqrt(t[o].sum);
		if(t[o].sum==0 || t[o].sum==1) t[o].tag=1;
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid && !t[o<<1].tag) change(o<<1,l,mid,ql,qr);
	if(qr>mid && !t[o<<1|1].tag) change(o<<1|1,mid+1,r,ql,qr);
	pushup(o);
}
int query(int o,int l,int r,int ql,int qr){
	if(ql<=l && qr>=r) return t[o].sum;
	int mid=(l+r)>>1;
	int res=0;
	if(ql<=mid) res+=query(o<<1,l,mid,ql,qr);
	if(qr>mid) res+=query(o<<1|1,mid+1,r,ql,qr);
	return res;
}
signed main(){
	int _case=0;
	while(~scanf("%d",&n)){
		printf("Case #%d:\n",++_case);
		memset(a,0,sizeof(a));
		memset(t,0,sizeof(t));
		for(int i=1;i<=n;i++) a[i]=read();
		build(1,1,n);
		m=read();
		while(m--){
			int opt=read(),l=read(),r=read();
			if(l>r) swap(l,r);
			if(opt==0) change(1,1,n,l,r);
			else printf("%lld\n",query(1,1,n,l,r));
		}
		puts("");
	}
	return 0;
}
这道题中要计算的每个数最多被开方7次后就变成1
启发：大于一就暴力修改，0(7 n log n)
等差数列，注意每个节点维护首项和公差
CPP
#include<bits/stdc++.h>
using namespace std;
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100010;
int n,m,a[maxn];
struct node{
	int sum;
	int size;
	int x,y;
	node(){sum=size=x=y=0;}
	void init(int v){sum=v;size=1;}
}z[maxn<<2];
node operator+(const node&l,const node&r){
	node res;
	res.sum=l.sum+r.sum;
	res.size=l.size+r.size;
	return res;
}
void color(int l,int r,int rt,int x,int y){
	z[rt].x+=x;
	z[rt].y+=y;
	z[rt].sum+=(x+x+(z[rt].size-1)*y)*z[rt].size/2;
}
void push_col(int l,int r,int rt){
	if(z[rt].x==0&&z[rt].y==0)return;
	int m=(l+r)>>1;
	color(lson,z[rt].x,z[rt].y);
	color(rson,z[rt].x+z[rt<<1].size*z[rt].y,z[rt].y);
	z[rt].x=z[rt].y=0;
}
void build(int l,int r,int rt){
	if(l==r){
		z[rt].init(a[l]);
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	z[rt]=z[rt<<1]+z[rt<<1|1];
}
node query(int l,int r,int rt,int nowl,int nowr){
	if(nowl<=l&&r<=nowr)return z[rt];
	push_col(l,r,rt);
	int m=(l+r)>>1;
	if(nowl<=m){
		if(m<nowr)return query(lson,nowl,nowr)+query(rson,nowl,nowr);
		else return query(lson,nowl,nowr);
	}
	else return query(rson,nowl,nowr);
}
void modify(int l,int r,int rt,int nowl,int nowr,int x,int y){
	if(nowl<=l&&r<=nowr){
		color(l,r,rt,x,y);
		return;
	}
	push_col(l,r,rt);
	int m=(l+r)>>1;
	if(nowl<=m)modify(lson,nowl,nowr,x,y);
	if(m<nowr)modify(rson,nowl,nowr,x,y);
	z[rt]=z[rt<<1]+z[rt<<1|1];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(root);
	cin>>m;
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r;
			cin>>l>>r;
			cout<<query(root,l,r).sum<<"\n";
		}
		else{
			int l,r,x,y;
			cin>>l>>r>>x>>y;
			modify(root,l,r,x,y);
		}
	}
	return 0;
}
可持久化线段树
CPP
#include<bits/stdc++.h>

using namespace std;
int cnt;//总共有多少个节点 
struct node
{
	int l,r;//左儿子 右儿子编号 
	int sum;//区间和 
	node(){
		l=r=sum=0;
	}
}z[maxn*logn];

void update(int p)
{
	z[p].sum = z[z[p].l].sum + z[z[p].r].sum;
}

int build(int l,int r)//当前的区间为l~r 是这段区间对应的节点编号 
{
	cnt++;
	int p=cnt;
	if (l==r)
	{
		z[p].sum = a[l];
		return p;
	}
	int m=(l+r)>>1;
	z[p].l = build(l,m);
	z[p].r = build(m+1,r);
	update(p);
	return p;
}

int query(int l,int r,int rt,int nowl,int nowr)
//当前线段树节点编号为rt 对应的区间为l~r 要询问nowl~nowr这段区间的和
{
	if (nowl <= l && r <= nowr) return z[rt].sum;
	int m=(l+r)>>1;
	if (nowl<=m)
	{
		if (m<nowr) return query(l,m,z[rt].l,nowl,nowr) + query(m+1,r,z[rt].r,nowl,nowr);
		else return query(l,m,z[rt].l,nowl,nowr);
	}
	else return query(m+1,r,z[rt].r,nowl,nowr);
} 

int modify(int l,int r,int rt,int p,int v)//返回修改后的新节点编号 
//当前线段树节点编号为rt 对应的区间为l~r 要把a[p]+=v 
{
	cnt++;int q = cnt;//新的节点q用于修改
	z[q] = z[rt]; 
	if (l==r)
	{
		z[q].sum += v;
		return q;
	}
	int m=(l+r)>>1;
	if (p<=m)//在左儿子
		z[q].l = modify(l,m,z[q].l,p,v);
	else 
		z[q].r = modify(m+1,r,z[q].r,p,v);
	update(q);
	return q;
}

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	cin >> m;
	root[0] = build(1,n);//root[i]代表第i次操作后的根节点是谁
	for (int i=1;i<=m;i++) 
	{
		int opt;
		cin >> opt;
		if (opt==1)
		{
			int p,v;
			cin >> p >> v;
			root[i] = modify(1,n,root[i-1],p,v);
		}
		else
		{
			int k,l,r;
			cin >> k >> l >> r;
			cout << query(1,n,root[k],l,r) << "\n";
			root[i] = root[i-1];
		}
	}
	
	return 0;
}
注意区间对应的关系
作业
https://www.luogu.com.cn/problem/P4513
https://www.luogu.com.cn/problem/P3372
https://www.luogu.com.cn/problem/P3373
https://www.luogu.com.cn/problem/P1253
https://www.luogu.com.cn/problem/SP1043
https://www.luogu.com.cn/problem/SP1716
https://www.luogu.com.cn/problem/SP2916
https://www.luogu.com.cn/problem/SP2713
http://cdqz.openjudge.cn/ds/1003/
http://cdqz.openjudge.cn/ds/1004/
http://cdqz.openjudge.cn/ds/1005/
https://vjudge.net/problem/HDU-3954#author=GPT_zh
https://hydro.ac/p/bzoj-P3333
https://www.luogu.com.cn/problem/P3919
https://www.luogu.com.cn/problem/P3834
http://cdqz.openjudge.cn/ds/1011/
http://cdqz.openjudge.cn/ds/1001/
http://cdqz.openjudge.cn/ds/1012/
https://vjudge.net/problem/HDU-3333#author=GPT_zh
https://vjudge.net/problem/HDU-4467#author=GPT_zh
https://hydro.ac/p/bzoj-P3251

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...