本文主要是介绍hdu 3308线段树 区域合并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
区域合并时需要考虑两点
1、pushup中区域合并时最左右递增长度（llen/rlen）等于整个区域长度(r - l)时需要重新计算父区域的最左右的递增长度
2、query中需要考虑区域合并接口处是否有可能产生ans值
#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>using namespace std;const int maxn = 100050;struct node{int l, r, ml;//最左右边界，最大长度 int lw, rw;//最左右的值 int llen, rlen;//最左右递增区域的长度 int mid(){return (l+r)/2;}
}tree[maxn*4];void pushUp(int left, int right, int ind)
{tree[ind].lw = tree[ind*2].lw;tree[ind].rw = tree[ind*2+1].rw;tree[ind].llen = tree[ind*2].llen;tree[ind].rlen = tree[ind*2+1].rlen;int len = 0;if( tree[ind*2].rw < tree[ind*2+1].lw ){len = tree[ind*2].rlen + tree[ind*2+1].llen;//考虑最左右递增区域等于整个区域的情况 if(tree[ind*2+1].llen == tree[ind*2+1].r - tree[ind*2+1].l+1){tree[ind].rlen = tree[ind*2+1].llen + tree[ind*2].rlen; }if(tree[ind*2].rlen == tree[ind*2].r - tree[ind*2].l+1){tree[ind].llen = tree[ind*2].rlen + tree[ind*2+1].llen;}} len = len > tree[ind*2].ml ? len : tree[ind*2].ml;tree[ind].ml = len > tree[ind*2+1].ml ? len : tree[ind*2+1].ml;
}void buildTree(int left, int right, int ind)
{tree[ind].l = left;tree[ind].r = right;if(left == right){cin >> tree[ind].lw;tree[ind].rw = tree[ind].lw;tree[ind].llen = tree[ind].rlen = 1;tree[ind].ml = 1; return ;}int mid = tree[ind].mid();buildTree(left, mid, ind*2);buildTree(mid+1, right, ind*2+1);pushUp(left, right, ind);
}void update(int left, int right, int ind, int pos, int add)
{if(left == right){tree[ind].lw = tree[ind].rw = add;return ;}int mid = tree[ind].mid();if(pos <= mid) update(left, mid, ind*2, pos, add);if(pos > mid) update(mid+1, right, ind*2+1, pos, add);pushUp(left, right, ind);
}int ans;
void query(int left, int right, int ind, int L, int R)
{if(L <= left && R >= right){ans = ans > tree[ind].ml ? ans : tree[ind].ml;if(ans > 1000) cout<<"que ind"<<ind<<endl;return ;}int mid = tree[ind].mid();if(L <= mid){query(left, mid, ind*2, L, R);}if(R > mid){query(mid+1, right, ind*2+1, L, R);}int len;//考虑区间合并时左右两段相加 if(tree[ind*2].rw < tree[ind*2+1].lw){len = min(mid-L+1, tree[ind*2].rlen) + min(R-mid, tree[ind*2+1].llen);ans = ans > len ? ans : len;}} int main()
{int T, m, n, a, b;string str; scanf("%d",&T);while(T --){scanf("%d%d", &n, &m);buildTree(1, n, 1);while(m --){cin >> str;scanf("%d%d",&a, &b);if(str == "Q"){ans = 0;query(1, n, 1, a+1, b+1);printf("%d\n", ans);}if(str == "U"){update(1, n, 1, a+1, b);}}}return 0;
}这篇关于hdu 3308线段树 区域合并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
