首页 > 代码库 > hdu 3308线段树 区域合并
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线段树 区域合并
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。