精华内容
下载资源
问答
  • 线段树 区间合并 poj3368
    2020-09-11 17:39:46

    poj 3368 Frequent values

    题意:

    给一个单调不递减的数列,求给定区间内重复最多数字的次数

    • 1、RMQ(这里不说这个)
    • 2、线段树的区间合并,可以说是一个比较简单的模板吧,至于难的,咱不会啊

    用线段树进行维护的话,要记录五个值:
    区间左边界的数字,
    区间左边界在本区间内的次数,
    区间右边界的数字 ,
    区间右边界在本区间内的次数,
    该区间内出现的最大次数
    在用线段树维护的时候,不能只对左右区间的值进行比较,还要把两个区间合并(如果 左区间的右边界 == 右区间的左边界)看合并后中间是否形成出现次数更多的数字

    这里引用下别的文章吧,毕竟我老懒人了(doge)

    这一类区间查询的问题很容易想到用线段树来做。显然我们首先要线段树的节点中维护么i各区间的最大次数。但这样是不够的,如果一个查询区间跨越了两个区间,那查询区间的最大次数怎么取呢?取较大值?加和?显然不是那么简单。
    仔细观察题目条件,数组本身是升序的。这表示,两个区间连接之后,最大次数改变只可能发生在两个区间交接的地方。即左区间的右端和右区间的左端一样,连接起来形成了一个比原来两区间的最大值更大的一个值。
    而进行这个连接处的判断和计算,我们只需要知道左子树的右端和它在左子树中出现的次数,右子树的左端和它在右子树中出现的次数。所以,线段树的每个节点需要维护五个值:本区间内最大次数,左端点及其次数,右端点及其次数。

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <string>
    #include <cmath>
    #include <cstdlib>
    
    using namespace std;
    
    const int MAXN = 100000 + 100;
    const int INF = 0x7f7f7f7f;
    
    int L[MAXN  * 4] , L_Num[MAXN * 4] ,  R[MAXN * 4] , R_Num[MAXN * 4] , S[MAXN * 4];
    //区间左边界的数字,区间左边界在本区间内的次数,区间右边界的数字 , 区间右边界在本区间内的次数
    //以及该区间内出现的最大次数
    int arr[MAXN];
    
    void update(int rt)
    {
    	int temp = 0;
    	//如果左子树区间的右边界 == 右子树区间的左边界,就计算中间连同部分出现次数
    	if(R[rt<<1] == L[rt<<1|1]){
    		temp = R_Num[rt<<1] + L_Num[rt<<1|1];  
    	} 
    
    	//判断是中间连同后出现次数多还是左右子树中的出现最多次数的数字多
    	temp  = max(temp ,  S[rt<<1]);
    	S[rt] = max(temp , S[rt<<1|1] );
    
    	//更新L[rt] 和 R[rt]
    	L[rt] = L[rt<<1] , R[rt] = R[rt<<1|1];
    
    	//如果左儿子的左边界和右儿子的左边界相同,那么该区间与左边界相同的数字数为
    	//左右儿子区间左端点出现次数的和
    	if(L[rt<<1] == L[rt<<1|1]){
    		L_Num[rt] = L_Num[rt<<1] + L_Num[rt<<1|1];
    	}
    	else{
    		L_Num[rt] = L_Num[rt<<1];
    	}
    
    	//右边界数字在区间内出现次数同上
    	if(R[rt<<1] == R[rt<<1|1]){
    		R_Num[rt] = R_Num[rt<<1] + R_Num[rt<<1|1];
    	}
    	else{
    		R_Num[rt] = R_Num[rt<<1|1];
    	}
    }
    
    void Build(int rt, int l, int r)
    {
    	if( l  == r){
    		L[rt] = R[rt] = arr[l];
    		L_Num[rt] = R_Num[rt] = 1;
    		S[rt] = 1;
    		return ;
    	}
    	int mid = (l + r) >> 1;
    	Build(rt << 1 , l , mid);
    	Build(rt << 1|1 , mid + 1 , r);
    	update(rt);
    }
    
    int Query(int rt , int l , int r , int a , int b)
    {
    	if( a <= l && r <= b){
    		return S[rt];
    	}
    	int mid = (l + r)>>1;
    	int lr  = 0, rr = 0;
    	if(a <= mid){
    		lr = Query(rt<<1 , l , mid , a, b);
    	}
    	if(b > mid){
    		rr = Query(rt<<1|1 , mid + 1, r, a, b);
    	}
    	//下面关于最大值要更新两次,一次是比较左右儿子区间的最大值,还有一次是比较合并区间后
    	//中间数出现的次数
    	int res = max(lr,rr);//第一次更新
    
    	//如果左右儿子出现在查询区间内,并且左右儿子区间可以合并 ,就要考虑是否因为合并导致
    	//出现  出现次数更多的数字
    	if( lr && rr && R[rt<<1] == L[rt<<1|1]){
    		//注意在合并区间时,要找在查询区间范围内的出现次数,注意这里是min
    		int temp  = min(R_Num[rt<<1] , mid  - a  + 1);//连接左儿子
    		temp  += min(L_Num[rt<<1|1] , b -  mid);//连接右儿子
    
    		//第二次更新
    		res = max(temp , res);
    	}
    	return res;
    }
    
    int main()
    {
    	int  n;
    	while(scanf("%d", &n), n){
    		int q;
    		scanf("%d",&q);
    
    		for(int i = 1; i <= n; i++){
    			scanf("%d",arr + i);
    		}
    
    		Build(1,1,n);
    
    		while(q--){
    			int L , R;
    			scanf("%d%d",&L,&R);
    			int ans = Query(1,1,n,L,R);
    			printf("%d\n",ans);
    		}
    	}
    	return 0;
    }
    
    更多相关内容
  • 【模板】线段树区间合并

    千次阅读 2018-05-28 21:17:20
    区间合并是一类问题的统称,种类很多,但在这篇博客中只需实现以下操作即可: 有一个01串,你有三种操作: 1.将[a, b]中的所有数字改成0 2.将[a, b]中的所有数字改成1 3.询问[a, b]中最长连续的1的长度是多少 ...

    区间合并是一类问题的统称,种类很多,但在这篇博客中只需实现以下操作即可:
    有一个01串,你有三种操作:

    • 1.将[a, b]中的所有数字改成0
    • 2.将[a, b]中的所有数字改成1
    • 3.询问[a, b]中最长连续的1的长度是多少

    前两种操作其实可以算作一个操作,重点在于如何高效地解决第三种操作。
    虽说平衡树也可以解决这类问题,但是这里我们使用线段树来解决。


    这是一个经典的老套路

    线段树维护四个值(可以缩成三个,使用第四个是为了加强程序的可读性),分别是:

    • lsum记录该区间左端点开始的最长连续的值为1区间
    • rsum记录该区间右端点开始的最长连续的值为1区间
    • sum记录该区间内最长连续的值为1的区间
    • color形象解释就是记录区间的“颜色”,具体操作是当这个区间全部是1时color置1,全部为0时color置0,否则置-1。在pushup()的时候会用到。

    接下来来讲讲具体的操作

    首先是重中之重 pushup() p u s h u p ( )

    这里博主有点懒,就不画图了,相信听了讲解自己脑补一下也是能搞懂的(听起来真的很简单~~)。
    开始假设当前节点为 this t h i s ,其左儿子为 lc l c ,右儿子为 rc r c ,且 lc l c rc r c 中四个值均准确无误,接下来要对 this t h i s 节点做 pushup() p u s h u p ( ) 操作。
    分步骤讨论:

    • 1、计算 lsum l s u m
      脑补一下,当 lc l c color c o l o r 为1时(也就是说左儿子结点全部由1组成),那么 lsum l s u m 就是 lc l c lsum l s u m (实际上 lsum l s u m rsum r s u m sum s u m 的值都是左儿子结点的区间长度,换一下也没有什么大的差别)加上 rc r c lsum l s u m 。否则直接赋值为 lc>lsum l c − > l s u m
    • 2、计算 rsum r s u m
      与计算 lsum l s u m 的方法类似,当 rc r c color c o l o r 为1时,那么 rsum r s u m 就是 rc r c rsum r s u m 加上 lc l c rsum r s u m 。否则直接赋值为 rc>rsum r c − > r s u m
    • 3、计算 sum s u m
      这应该很好想,就直接在 lc>sum l c − > s u m rc>sum r c − > s u m lc>rsum+rc>lsum l c − > r s u m + r c − > l s u m 中间取个 max m a x 就可以了,其中最后一个有点特殊,想想也挺简单,因为 lc>rsum l c − > r s u m rc>lsum r c − > l s u m 中所记录的区间是连续的(看看定义就知道了)。
    • 4.计算 color c o l o r
      有了前面的经验,这个应该很简单,直接给出,脑补也不困难。
      color=0,1,1,if sum= 0if sum= r - l + 1if0<sum<r - l + 1 c o l o r = { 0 , if  s u m = 0 1 , if  s u m = r - l + 1 − 1 , if 0<sum<r - l + 1

    其次是 query() q u e r y ( )

    由于本人比较蒟蒻,所以我使用了一个 struct s t r u c t 来存储我需要的 Ans A n s 并逐步更新, Ans A n s 里面存储三个值, ls l s rs r s s s ,意义应该很明白,和上面的lsum rsum r s u m sum s u m 一一对应,答案的转移与 pushup() p u s h u p ( ) 相类似由于上面的 pushup() p u s h u p ( ) 使用到了 color c o l o r 来简化操作,现在的 Ans A n s 中不便维护 color c o l o r ,所以不能偷懒了~。

    然后就没有什么可以说的了,其余操作和原版线段树类似,如果不明白可以参考

    Code C o d e

    struct SegTree {
        #define lc(o) o << 1 //简化操作
        #define rc(o) o << 1 | 1  
        #define mid ((l + r) >> 1)
        struct Ans { 
            int ls, rs, s; 
            Ans(int ls, int rs, int s) : ls(ls), rs(rs), s(s) {}
        };
        static const int MAXSIZE = 100000 + 5;
        int lsum[MAXSIZE << 2], rsum[MAXSIZE << 2], sum[MAXSIZE << 2], color[MAXSIZE << 2];
        void creat(int o, int l, int r, int value) { //更新一个结点
            color[o] = value;
            lsum[o] = rsum[o] = sum[o] = value ? r - l + 1 : 0; //三目运算符秀了一波~
        }
        void pushdown(int o, int l, int r) {  
            if (color[o] != -1) { //如果有color那么pushdown,注意color不会在向子结点更新后发生改变
                creat(lc(o), l, mid, color[o]);
                creat(rc(o), mid + 1, r, color[o]);
            }
        }
        void pushup(int o, int l, int r) { //繁琐的pushup(),具体已经解释过了
            lsum[o] = color[lc(o)] == 1 ? lsum[lc(o)] + lsum[rc(o)] : lsum[lc(o)];
            rsum[o] = color[rc(o)] == 1 ? rsum[lc(o)] + rsum[rc(o)] : rsum[rc(o)];
            sum[o] = max(rsum[lc(o)] + lsum[rc(o)], max(sum[lc(o)], sum[rc(o)]));
            if (sum[o] == 0) color[o] = 0; else if (sum[o] == r - l + 1) color[o] = 1; else color[o] = -1;
        }
        void set(int o, int l, int r, int L, int R, int value) { //和普通线段树一样的操作
            if (l > R || r < L) return;
            else if (L <= l && r <= R) creat(o, l, r, value);
            else {
                pushdown(o, l, r);
                set(lc(o), l, mid, L, R, value);
                set(rc(o), mid + 1, r, L, R, value);
                pushup(o, l, r);
            }
        }
        Ans query(int o, int l, int r, int L, int R) {
            if (l > R || r < L) return Ans(0, 0, 0);
            else if (L <= l && r <= R) return Ans(lsum[o], rsum[o], sum[o]);
            else {
                pushdown(o, l, r);
                if (R <= mid) return query(lc(o), l, mid, L, R);
                if (L > mid) return query(rc(o), mid + 1, r, L, R);
                Ans p = query(lc(o), l, mid, L, R);
                Ans q = query(rc(o), mid + 1, r, L, R);
                return Ans(p.ls == mid - l + 1 ? p.ls + q.ls : p.ls, 
                           q.rs == r - mid ? p.rs + q.rs : q.rs, 
                           max(max(p.s, q.s), p.rs + q.ls));
            }
        }
        void build(int o, int l, int r) {
            if (l > r) return;
            else if (l == r) creat(o, l, r, a[l]);
            else {
                build(lc(o), l, mid);
                build(rc(o), mid + 1, r);
                pushup(o, l, r);
            }
        }
    };
    展开全文
  • 线段树区间合并操作 线段树区间合并操作维护信息时,除了区间和、更新标记等,最重要的就是要维护lsum和rsum这两个特殊值 这两个值分别各自的意义是:lsum 代表以该区间左端点为起点的连续段的长度(左连续段) ...

    线段树的区间合并操作

    • 线段树的区间合并操作维护信息时,除了区间和、更新标记等,最重要的就是要维护lsum和rsum这两个特殊值
    • 这两个值分别各自的意义是:lsum 代表以该区间左端点为起点的连续段的长度(左连续段) ,rsum代表以该区间右端点为终点(注意是终点)的连续段的长度(右连续段),而rsum[rt<<|1]+lsum[rt<<1|1]则是代表了含有当前区间终点的最大连续段长度。
    • 另外还有一个需要维护的值就是 sum[rt] 也就是当前节点下的最大连续区间的长度,而对于每一次lsum和rsum更新完成后 sum[rt]应这样给出:
    • sum[rt] = max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1])
    • 其值就在左子树最大连续区间,右子树最大连续区间和中间连续段中取最大值
    • 另外 区间合并在线段树操作中主要体现在pushup函数的变化上:
    void pushup(int rt,int tot)
    {
    	if(tot == 1) return ;
    	lsum[rt] = lsum[rt<<1];
    	rsum[rt] = rsum[rt<<1|1];
    	// 体现区间合并的地方
    	if(lsum[rt] == (tot-tot/2)) lsum[rt]+=lsum[rt<<1|1];//代表左子树的区间满了需要加上右子树左区间
    	if(rsum[rt] == (tot/2)) rsum[rt]+=rsum[rt<<1];// 和上方同理
    	sum[rt] = max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1]));
    }
    

    POJ3667 HDU4553(比前面麻烦一点 维护两个树)
    这两道题都要求返回一个查询的位置信息写在query函数中就是

    int query(int rt,int l,int r,int len)// len代表需要满足的区间长度
    {
    	if(l == r) return l;
    	pushdown(rt,r-l+1);
    	int mid = (l+r)>>1;
    	if(sum[rt<<1] >= len) return query(rt<<1,l,mid,len);//做子树区间满足要求 那么位置一定在左子树区间中
    	else if(rsum[rt<<1]+lsum[rt<<1|1] >= len) return mid-rsum[rt<<1]+1;// 中间段满足要求 那么起始点一点是左子树右连续区间的起点
    	else return query(rt<<1|1,mid+1,r,len);//其他情况就一定存在于右子树中
    }
    
    

    代码:

    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    const int MAXN = 5e4+7;
    int sum[MAXN<<2],lsum[MAXN<<2],rsum[MAXN<<2];
    int lazy[MAXN<<2];
    // 这个就是 hdu4553的弱化版
    // 这中区间一个起始位置的题目应该都是一个套路
    // 区间合并的关键 在pushup中 而query或者其他函数需要根据具体题目具体 确定
    void pushup(int rt,int tot)
    {
    	if(tot == 1) return ;
    	lsum[rt] = lsum[rt<<1];
    	rsum[rt] = rsum[rt<<1|1];
    	if(lsum[rt] == (tot-tot/2)) lsum[rt]+=lsum[rt<<1|1];
    	if(rsum[rt] == (tot/2)) rsum[rt]+=rsum[rt<<1];
    	sum[rt] = max(rsum[rt<<1]+lsum[rt<<1|1],max(sum[rt<<1],sum[rt<<1|1]));
    }
    
    void pushdown(int rt,int tot)
    {
    	if(tot == 1) return ;
    	if(lazy[rt]){
    		lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
    		if(lazy[rt] == 2){
    			sum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = tot-tot/2;
    			sum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = tot/2;
    		}
    		else if(lazy[rt] == 1){
    			sum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = 0;
    			sum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = 0;
    		}
    		lazy[rt] = 0;
    	}
    }
    
    void build(int rt,int l,int r)
    {
    	lazy[rt] = 0;
    	if(l == r){
    		sum[rt] = lsum[rt] = rsum[rt] = 1;
    		return ;
    	}
    	//pushdown(rt,r-l+1);
    	int mid = (l+r)>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt,r-l+1);
    }
    
    void update(int rt,int l,int r,int ul,int ur,int p)
    {
    	if(l>=ul&&r<=ur){
    		if(p == 1){
    			sum[rt] = lsum[rt] = rsum[rt] = 0;
    		}
    		else if(p == 2){
    			sum[rt] = lsum[rt] = rsum[rt] = r-l+1;
    		}
    		lazy[rt] = p;
    		return ;
    	}
    	pushdown(rt,r-l+1);
    	int mid = (l+r)>>1;
    	if(ul <= mid) update(rt<<1,l,mid,ul,ur,p);
    	if(ur > mid) update(rt<<1|1,mid+1,r,ul,ur,p);
    	pushup(rt,r-l+1);
    }
    
    int query(int rt,int l,int r,int len)
    {
    	if(l == r) return l;
    	pushdown(rt,r-l+1);
    	int mid = (l+r)>>1;
    	if(sum[rt<<1] >= len) return query(rt<<1,l,mid,len);
    	else if(rsum[rt<<1]+lsum[rt<<1|1] >= len) return mid-rsum[rt<<1]+1;
    	else return query(rt<<1|1,mid+1,r,len);
    }
    
    int main()
    {
    	int n,m;
    	scanf("%d%d",&n,&m);
    	build(1,1,n);
    	int k;
    	while(m--){
    		scanf("%d",&k);
    		if(k == 1){
    			int len;
    			scanf("%d",&len);
    			if(sum[1]>=len){
    				int pos = query(1,1,n,len);
    				printf("%d\n",pos);
    				update(1,1,n,pos,pos+len-1,1);
    			}
    			else printf("0\n");
    		}
    		else if(k == 2){
    			int st,len;
    			scanf("%d%d",&st,&len);
    			update(1,1,n,st,st+len-1,2);
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 线段树区间合并详解

    2018-05-24 15:20:30
    深入理解线段树区间合并问题摘自:百度文库

    深入理解线段树区间合并问题

    摘自:百度文库

    展开全文
  • 线段树区间合并

    千次阅读 2018-08-14 16:27:32
    线段树区间合并主要解决一段连续区间修改,查询问题。 线段树是树形结构,为解决相邻区间更新,修改问题,我们必须在原本须要维护的区间内,连续段最大值的基础上加上,从左,右两边起,最大的连续区间长度。 例题...
  • 其实就是一道线段树区间合并的例题,考虑维护左右端点即可,相等的时候减去即可。 另外由于是树链的原因,查询的时候需要查询很多次,因此在每次查询的时候需要额外考虑两个查询区间的区间并是否端点相等,在最后的...
  • 本题我们要维护最左边的值,考虑使用线段树维护。我们发现只用一个来存储当前的节点的值并不够,因为对于一个节点我们无法用一个来描述这整个区间哪些为空,哪些满了,例如查询的跨越了两个区间,我们就无法找到最...
  • 如果该序列是静态的,那么既可用线段树区间合并操作来求解LCIS,又可以使用动态规划方式来求解。 如果该序列是动态的,不断地要更新序列的权重并且进行及时的LCIS求解,此时如果依旧使用DP方式,难免过于耗时,...
  • POJ3667-Hotel-线段树区间合并(模板)

    千次阅读 2015-08-06 09:52:08
    这是个线段树维护区间合并的问题;我们要维护一个区间的从左端点开始的最长区间,右端点的最长区间,以及该区间的最长区间,有了这些信息我们就可以轻易的合并子节点的信息,简单更新了; 好吧,我就不详细介绍了,...
  • 简单线段树区间合并
  • 关于区间合并 安利第三篇 通俗易懂 让我彻底学会了区间合并而不是背代码 题解 p编号代表的这段区间 L代表左起最长的空房间长度 R代表右起最长的空房间长度 dat代表区间最长不论位置的空房间长度 //视...
  • 关于线段树的更详细实现请参考线段树解决区间问题包括延迟操作以及离散化 /* 在数轴上,一次给一个线段涂上颜色 后面的颜色会覆盖前面的颜色 问最后能看到多少个颜色 显然是成段更新,线段树 区间范围是1千万...
  • 线段树区间合并小结

    千次阅读 多人点赞 2018-03-20 10:08:58
    个人感觉区间合并线段树各种应用中变形最多 也是比较难琢磨的一种 (以下以求01序列中最长连续1为例) tree[cur].left代表以区间左端点为起点的连续段的长度 tree[cur].right代表右边 tree[cur].all代表该区间内...
  • 题目链接: LCIS 大致题意 给定一个长度为nnn的序列. 有mmm次操作: ...我们可以通过线段树区间合并来解决本类题目: 考虑当前有两个区间left,rightleft, rightleft,right. 设合并后的新区间为resresres. 那
  • 个人感觉区间合并线段树各种应用中变形最多 也是比较难琢磨的一种 (以下以求01序列中最长连续1为例) tree[cur].left代表以区间左端点为起点的连续段的长度 tree[cur].right代表右边 tree[cur].all代表该区间内...
  • 线段树--合并区间

    2020-03-14 20:53:47
    合并区间其实就是在线段树–lazy标记的基础上,每个点储存多个区间信息。在修改时就需要合并区间。 例题 P2894 [USACO08FEB]Hotel G 分析 住店和退房其实就是修改区间,但怎么查找连续为0的区间呢?这就需要合并区间...
  •  那么,现在问题就比较好办了,线段树每个节点包含三个信息,分别是 以区间第一个元素开始的最大连续区间长度 ln ,以区间最后一个元素结尾的最大连续区间长度 rn , 以及区间最大连续长度 mn 。 接下来,便是Q...
  • https://blog.csdn.net/Diogenes_/article/details/80471916
  • 最长区间 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 给你一个长度为 n 的序列 a ,求最长的连续的严格上升区间的长度。 同时会进行 m 次修改...
  • 线段树 区间合并

    2013-03-15 01:20:49
    思路:线段树,定义三个数组分别表示从左,右,中,的最大连续长度,注意向上更新时合并区间的操作。 写了一段时间,错了很多地方。 AC代码: #include #include #include #define lson l,m,rt #define rson m+1,...
  • 题意: 给定一个环形序列,在线单次跟新,修改一个元素,求环上最大子串和 分析: 如何求每次的环上最大子串和那么相当于这里介绍的方法51nod...那么就是线段树区间合并问题 需要维护下列数组 int sum[maxn int l
  • 线段树区间合并例题之一
  • 线段树 区间合并模板

    2019-03-27 19:46:06
    区间合并是一类问题的总称包括以下操作 1.将[a, b]中的所有数字改成0 2.将[a, b]中的所有数字改成1 3.询问[a, b]中最长连续的1的长度是多少 主要解决第三种操作,也就是PushUp 函数 void PushUp(const int& rt, ...
  • 线段树维护区间内容的一道经典题,值得一做,废话少说,开始讲解吧。1.线段树维护内容 线段树维护一个最长区间线段树节点维护4个东西: 1.必须从左节点延伸的最长长度(lm) 2.必须从右节点延伸的最长长度(rm) ...
  • 这样的话我们对于每一种颜色动态开一个线段树,合并就把颜色为x的线段树区间l r合并到颜色为y的线段树的区间l r 上即可。 之前大多数的线段树合并是整颗线段树进行合并,这个是针对于某段区间进行合并,我们需要稍微...
  • HDU1540:Tunnel Warfare(线段树区间合并)

    千次阅读 2013-11-03 15:05:07
    //父亲区间内的最大区间必定是,左子树最大区间,右子最大区间,左右子树合并的中间区间,三者中最大的区间值 if(a[2*i].ls == a[2*i].r-a[2*i].l+1)//左子树区间满了的话,父亲左区间要加上右孩子的左区间 a...
  • #include using namespace std; #define N 100100 int a[N]; struct { int left,right,c; int ln,rn; int ls,rs,ms; }b[N*4]; void pushup(int i){ b[i].ls=b[i*2].ls; b[i].rs=b[2*i+1].rs;... b
  • 传送门: HDU 3308题解: ... 区间合并查询 /* adrui's submission Language : C++ Result : Accepted Favorite : Dragon Balls Love : yy Motto : Choose & Quit Standing in the Hall of Fame */#in

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,481
精华内容 5,792
关键字:

线段树区间合并

友情链接: MISSILETEST.rar