分块

最新推荐文章于 2024-12-08 10:30:31 发布

「已注销」

最新推荐文章于 2024-12-08 10:30:31 发布

阅读量220

点赞数

分类专栏： Daily algorithm

本文链接：https://blog.csdn.net/CC_1012/article/details/94648201

版权

Daily algorithm 专栏收录该内容

56 篇文章

订阅专栏

题目链接

题意：就是单点更新区间查询最小值

线段树做法：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
typedef long long LL;
LL tree[N<<2];
const int inf=0x3f3f3f3f; 
void build(int l,int r,int k)
{
	if(l==r){
		tree[k]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(1,mid,k<<1);
	build(mid+1,r,k<<1|1);
}
void update(int x,LL z,int l,int r,int k)
{
	if(l==r){
		tree[k]+=z;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(x,z,l,mid,k<<1);
	else update(x,z,mid+1,r,k<<1|1);
	tree[k]=max(tree[k<<1],tree[k<<1|1]);
}
LL query(int x,int y,int l,int r,int k)
{
	if(x<=l&&y>=r){
		return tree[k];
	}
	int mid=(l+r)>>1;
	LL  minn=0;
	if(x<=mid) minn=max(minn,query(x,y,l,mid,k<<1));
	if(y>mid) minn=max(minn,query(x,y,mid+1,r,k<<1|1));
	return minn;
	
}
int main()
{
	int n,q;scanf("%d %d",&n,&q);
	while(q--){
		int id;
		scanf("%d",&id);
		if(id==1){
			int x;
			LL y;
			scanf("%d %lld",&x,&y);
			update(x,y,1,n,1);
		}
		else{
			int a,b;
			scanf("%d %d",&a,&b);
			printf("%lld\n",query(a,b,1,n,1));
		}
	}
	return 0;
}

分块做法比较简单好理解

分块是一个在线算法不是莫队那种离线算法

分块可以处理区间奇奇怪怪的操作

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int block;//块的大小 
int belong[N];//表示i属于那一块 
int num;//块的个数 
int l[N],r[N];//表示i这块的左右端点位置 
int n,q;
long long a[N],maxn[N];
void build()
{
	block=sqrt(n);
	num=n/block;
	if(n%block) num++;
	for(int i=1;i<=num;i++){
		l[i]=(i-1)*block+1;
		r[i]=i*block;
	}
	r[num]=n;
	for(int i=1;i<=n;i++){
		belong[i]=(i-1)/block+1;
	}
	
	//这部分没有用到 因为没有给a[i]初始值 这里的初始值为0 
	for(int i=1;i<=num;i++){
		for(int j=l[i];j<=r[i];j++){
			maxn[i]=max(maxn[i],a[j]);
		}
	}
}

void update(int x,int y)
{
	a[x]+=y;
	maxn[belong[x]]=max(maxn[belong[x]],a[x]);
	
}
long long query(int x,int y)
{
	long long ans=0;
	if(belong[x]==belong[y]){
		for(int i=x;i<=y;i++){
			ans=max(ans,a[i]);
		}
		return ans;
	}
	for(int i=x;i<=r[belong[x]];i++){
		ans=max(ans,a[i]);
	}
	for(int i=belong[x]+1;i<belong[y];i++){
		ans=max(ans,maxn[i]);
	}
	for(int i=l[belong[y]];i<=y;i++){
		ans=max(ans,a[i]);
	}
	return ans;
}
int main()
{
	scanf("%d %d",&n,&q);
	build();
	while(q--){
		long long t,x,y;
		scanf("%lld %lld %lld",&t,&x,&y);
		if(t==1){
			update(x,y); 
		} 
		else{
			printf("%lld\n",query(x,y));
		}
	}
	return 0;
}