本文共 5509 字，大约阅读时间需要 18 分钟。
看到讲课安排上 线段树有一节课"区间合并" 我是迷茫的 因为并没有见过
然后了解了一下题目 发现以前写过 还是很麻烦的树链剖分 大概是 解决带修改的区间查询"连续问题"
意思就是给一个数组 要对这个数组进行修改 然后进行区间查询 查询的一般是 l r 区间内的 连续xx 可能是LCIS 也可能只是连续的数字..
解题的方法比较固定 由于是 连续性 相关 所以对于每个数组 维护它的左边与右边与全局的性质 例如紧靠左(右)边连续xx的长度和这个区间内连续xx的最长长度
关键就在up函数上 不管是单点还是区间修改 都能通过up来做巧妙地构造
POJ 3667
每次清空一段 或 查询一段中最靠左的x长度并填补
维护每个区间的左右连续 最简单的区间合并
HDU 3308
单点修改 或 查询一段中的LCIS
与上一道题的差别就是up函数 和 query函数中 对于 一个区间的两个子区间合并 需要判断一下数字的大小关系
HDU 3397
01串 区间赋值 区间反转 查询 区间sum 和 区间连续1的maxlen
同时维护左右全局的0和1的长度 在做反转的时候直接交换就可以了
在down的时候 如果down下去的是一个反转的历史 它可能会和上一次的历史发生化合 上一次的历史是赋值0 那这一次的历史就覆盖成赋值1而不是反转
#include #include #include #include #include #include #include using namespace std;const int maxn = 100050 ;int n , m ;struct node { int rl1, ll1, tl1 ; int rl0, ll0, tl0 ; int sum ; int l , r ; int len;}a[maxn * 4];int mark[maxn * 4] ; /// 0 -> 0 1 -> 0 -1 notdid 2 -> ycyint b[maxn] ;void up(int p) { if(a[p].l == a[p].r )return ; int pl = p*2 , pr = p*2+1 ; a[p].tl0 = max(a[pl].tl0 , a[pr].tl0) ; a[p].tl0 = max(a[p].tl0 , a[pl].rl0 + a[pr].ll0) ; a[p].tl1 = max(a[pl].tl1 , a[pr].tl1) ; a[p].tl1 = max(a[p].tl1 , a[pl].rl1 + a[pr].ll1) ; a[p].ll0 = a[pl].ll0; if(a[pl].sum == 0 ) { a[p].ll0 = max(a[p].ll0 , a[pl].len + a[pr].ll0) ; } a[p].rl0 = a[pr].rl0; if(a[pr].sum == 0 ) { a[p].rl0 = max(a[p].rl0 , a[pr].len + a[pl].rl0) ; } a[p].ll1 = a[pl].ll1; if(a[pl].sum == a[pl].len ) { a[p].ll1 = max(a[p].ll1 , a[pl].len + a[pr].ll1) ; } a[p].rl1 = a[pr].rl1; if(a[pr].sum == a[pr].len ) { a[p].rl1 = max(a[p].rl1 , a[pr].len + a[pl].rl1) ; } a[p].sum = a[pl].sum + a[pr].sum ; return ;}void build(int p,int l,int r){ mark[p] = -1 ; a[p].l = l , a[p].r = r; if(b[l] == 0) a[p].ll0 = 1 , a[p].ll1 = 0; else a[p].ll0 = 0 , a[p].ll1 = 1; if(b[r] == 0) a[p].rl0 = 1 , a[p].rl1 = 0; else a[p].rl0 = 0 , a[p].rl1 = 1; if(b[l] == 0) a[p].tl0 = 1 , a[p].tl1 = 0; else a[p].tl0 = 0 , a[p].tl1 = 1; a[p].len = r - l + 1 ; if(b[l] == 0)a[p].sum = 0 ; else a[p].sum = 1 ; if(l == r)return ; int mid = (l+r) / 2 ; build(p*2,l,mid); build(p*2+1,mid+1,r); up(p);}void ycy(int p) { swap(a[p].ll0 , a[p].ll1) ; swap(a[p].rl0 , a[p].rl1) ; swap(a[p].tl0 , a[p].tl1) ; a[p].sum = a[p].len - a[p].sum ;}void down(int p) { if(a[p].l == a[p].r)return ; if(mark[p] == -1)return ; int pl = p*2 , pr = p*2+1 ; if(mark[p] == 0) { mark[pl] = mark[pr] = mark[p] ; a[pl].ll0 = a[pl].rl0 = a[pl].tl0 = a[pl].len ; a[pl].ll1 = a[pl].rl1 = a[pl].tl1 = a[pl].sum = 0 ; a[pr].ll0 = a[pr].rl0 = a[pr].tl0 = a[pr].len ; a[pr].ll1 = a[pr].rl1 = a[pr].tl1 = a[pr].sum = 0 ; } else if(mark[p] == 1){ mark[pl] = mark[pr] = mark[p] ; a[pl].ll0 = a[pl].rl0 = a[pl].tl0 = 0 ; a[pl].ll1 = a[pl].rl1 = a[pl].tl1 = a[pl].sum = a[pl].len ; a[pr].ll0 = a[pr].rl0 = a[pr].tl0 = 0 ; a[pr].ll1 = a[pr].rl1 = a[pr].tl1 = a[pr].sum = a[pr].len ; } else { if(mark[pl] == 0) mark[pl] = 1; else if(mark[pl] == 1) mark[pl] = 0 ; else if(mark[pl] == 2) mark[pl] = -1 ; else mark[pl] = 2; if(mark[pr] == 0) mark[pr] = 1; else if(mark[pr] == 1) mark[pr] = 0 ; else if(mark[pr] == 2) mark[pr] = -1 ; else mark[pr] = 2; ycy(pl) , ycy(pr) ; } mark[p] = -1 ;}void upda1(int p , int l , int r ){ /// 0 if(a[p].l >= l && a[p].r <= r) { mark[p] = 0 ; a[p].ll0 = a[p].rl0 = a[p].tl0 = a[p].len ; a[p].ll1 = a[p].rl1 = a[p].tl1 = a[p].sum = 0 ; return ; } if(a[p].l == a[p].r)return ; down(p) ; int mid = (a[p].l + a[p].r) / 2 ; if(r <= mid) { upda1(p*2,l,r) ; } else if(l >= mid+1) { upda1(p*2+1,l,r); } else { upda1(p*2,l,mid); upda1(p*2+1,mid+1,r); } up(p);}void upda2(int p , int l , int r ){ /// 1 if(a[p].l >= l && a[p].r <= r) { mark[p] = 1 ; a[p].ll0 = a[p].rl0 = a[p].tl0 = 0 ; a[p].ll1 = a[p].rl1 = a[p].tl1 = a[p].sum = a[p].len ; return ; } if(a[p].l == a[p].r)return ; down(p) ; int mid = (a[p].l + a[p].r) / 2 ; if(r <= mid) { upda2(p*2,l,r) ; } else if(l >= mid+1) { upda2(p*2+1,l,r); } else { upda2(p*2,l,mid); upda2(p*2+1,mid+1,r); } up(p);}void upda3(int p, int l , int r ){ down(p); if(a[p].l >= l && a[p].r <= r) { ycy(p) ; mark[p] = 2 ; return ; } if(a[p].l == a[p].r) return ; int mid = (a[p].l + a[p].r) / 2; if(r <= mid) { upda3(p*2,l,r); } else if(l >= mid +1) { upda3(p*2+1,l,r); } else { upda3(p*2,l,mid); upda3(p*2+1,mid+1,r); } up(p);}int query1(int p,int l,int r){ down(p); if(a[p].l>=l&&a[p].r<=r) return a[p].sum; int mid = (a[p].l+a[p].r)/2; if(r<=mid)return query1(p*2,l,r); else if(l>=mid+1)return query1(p*2+1,l,r); else return query1(p*2,l,r) + query1(p*2+1,l,r);}int query2(int p,int l,int r){ down(p); if(a[p].l>=l&&a[p].r<=r)return a[p].tl1 ; if(a[p].l == a[p].r)return a[p].tl1; int mid = (a[p].l + a[p].r) / 2 ; if(r <= mid) { return query2(p*2,l,r); } else if(l >= mid+1) return query2(p*2+1,l,r); else { int res = 0; int r1 = r ; int r2 = a[p*2+1].l + a[p*2+1].ll1 - 1; r1 = min(r2,r1) ; int l1 = l ; int l2 = a[p*2].r - a[p*2].rl1 + 1; l1 = max(l1,l2) ; if(r1 >= l1) res = max(res , r1-l1+1); res = max(query2(p*2,l,r),res) ; res = max(query2(p*2+1,l,r),res); return res ; }}int main(){ int t; scanf("%d",&t); while(t-- ){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&b[i]) ; build(1,1,n) ; for(int i=1;i<=m;i++){ int op; scanf("%d",&op); int A,B; scanf("%d%d",&A,&B); A++,B++; if(op==0){ upda1(1,A,B); } else if(op==1){ upda2(1,A,B); } else if(op==2){ upda3(1,A,B); } else if(op==3){ printf("%d\n",query1(1,A,B)); } else { printf("%d\n",query2(1,A,B)); } } }}
感觉区间合并是一个线段树的思路
学习了kd-tree之后对线段树有了新的认识
转载于:https://www.cnblogs.com/rayrayrainrain/p/6359081.html