文档章节

线段树——区间合并 区间更新 模板

o
 osc_1ee7cxmx
发布于 2018/08/06 18:57
字数 528
阅读 10
收藏 0

精选30+云产品,助力企业轻松上云!>>>

线段树 区间合并模板  --区间更新

题目:http://poj.org/problem?id=3667 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>          //区间合并 区间更新 
using namespace std;

struct node{
	int ls,rs,ms;
};
node tree[4*80000];
int lazy[4*80000];
void pushup(int cr,int l,int r){   
	tree[cr].ls=tree[cr<<1].ls;   //左端点最长连续 
	tree[cr].rs=tree[cr<<1|1].rs; //右端点最长连续 
	tree[cr].ms=max( tree[cr<<1].rs+tree[cr<<1|1].ls,max( tree[cr<<1].ms,tree[cr<<1|1].ms) ); //区间最长连续 
	int mid=(l+r)/2;
	if(tree[cr<<1].ls==mid-l+1) tree[cr].ls+=tree[cr<<1|1].ls;
	if(tree[cr<<1|1].rs==r-mid) tree[cr].rs+=tree[cr<<1].rs;
}	
void pushdown(int l,int r,int cr){  //lazy[cr]=1 表示空出房间,lazy[cr]=0 表示入驻房间 
	if(lazy[cr]!=-1){
		int mid=(l+r)/2;
		lazy[cr<<1]=lazy[cr];
		lazy[cr<<1|1]=lazy[cr];
		tree[cr<<1].rs=tree[cr<<1].ls=tree[cr<<1].ms=lazy[cr]*(mid-l+1);
		tree[cr<<1|1].ls=tree[cr<<1|1].ms=tree[cr<<1|1].rs=lazy[cr]*(r-mid);

		lazy[cr]=-1;
	}
}
void build(int l,int r,int cr){
	if(l==r){
		tree[cr].ls=tree[cr].rs=tree[cr].ms=1;
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,cr<<1);
	build(mid+1,r,cr<<1|1);
	pushup(cr,l,r);
}
void update(int l,int r,int cr,int L,int R,int val){    
	if(L==l&&R==r){
		tree[cr].ls=tree[cr].rs=tree[cr].ms=(r-l+1)*val;
		lazy[cr]=val;
		return ;
	}
	int mid=(L+R)/2;
	pushdown(L,R,cr);
	if(l<=mid) update( l,min(r,mid),cr<<1,L,mid,val );
	if(r>mid) update( max(mid+1,l),r,cr<<1|1,mid+1,R,val);
	pushup(cr,L,R);
}
int query(int L,int R,int cr,int n){ ///找到区间的左端点 
	if(L==R){
		return L;
	}
	int mid=(L+R)/2;
	pushdown(L,R,cr);
	if(tree[cr<<1].ms>=n){  //左 
		return query(L,mid,cr<<1,n);
	}
	if(tree[cr<<1|1].ls+tree[cr<<1].rs>=n){	//中 
		return mid-tree[cr<<1].rs+1;
	}
	if(tree[cr<<1|1].ms>=n){
		return query(mid+1,R,cr<<1|1,n);
	}
	return 0;
}
int main(){
	int n,m;
	while(EOF!=scanf("%d%d",&n,&m)){
		memset(lazy,-1,sizeof(lazy));
		build(1,n,1);
		for(int j=1;j<=m;j++){
			int a;
			scanf("%d",&a);
			if(a==1){
				int b;
				scanf("%d",&b);
				int pp=query(1,n,1,b);
				if(pp) {
					update(pp,pp+b-1,1,1,n,0);
				}
				printf("%d\n",pp);	
			}
			else{
				int b,c;
				scanf("%d%d",&b,&c);
				update(b,b+c-1,1,1,n,1);
			}		
		}
	}
}

  

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

MongoDB入门系列——3.可视化工具篇

点击上方,轻松关注!! 前面我们已经介绍了MongoDB怎么安装,接下来要安装他的可视化工具——Studio 3T。 先到这下载一个压缩包,百度网盘,https://pan.baidu.com/s/1M8mlWo334KE8I1_UA2Da...

学习Java的小姐姐
2018/11/08
17
0
分层图的绘制 python(来自国外课程)

Exercise 10: Hierarchical clustering of the grain data In the video, you learnt that the SciPy linkage() function performs hierarchical clustering on an array of samples. Use th......

齐勇cn
43分钟前
13
0
微信小程序超简单的双向绑定(类似vue的v-model)

<input model:value="{{value}}" />

祖达
44分钟前
9
0
为什么AngularJS在select中包含一个空选项? - Why does AngularJS include an empty option in select?

问题: I've been working with AngularJS for the last few weeks, and the one thing which is really bothering me is that even after trying all permutations or the configuration de......

技术盛宴
46分钟前
13
0
centos宝塔面板安装及常见错误处理(超级详细)

原文连接:https://www.wjcms.net/archives/centos%E5%AE%9D%E5%A1%94%E9%9D%A2%E6%9D%BF%E5%AE%89%E8%A3%85%E5%8F%8A%E5%B8%B8%E8%A7%81%E9%94%99%E8%AF%AF%E5%A4%84%E7%90%86%E8%B6%85%E7%......

神兵小将
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部