首页 > 代码库 > HDU 1698 Just a Hook (线段树 成段更新 lazy-tag思想)

HDU 1698 Just a Hook (线段树 成段更新 lazy-tag思想)

题目链接

题意: n个挂钩,q次询问,每个挂钩可能的值为1 2 3,  初始值为1,每次询问

把从x到Y区间内的值改变为z。求最后的总的值。

分析:用val记录这一个区间的值,val == -1表示这个区间值不统一,而且已经向下更新了,

val != -1表示这个区间值统一, 更新某个区间的时候只需要把这个区间分为几个区间更新就行了,

也就是只更新到需要更新的区间,不用向下更新每一个一直到底了,在更新的过程中如果遇到之前没有向下更新的,

就需要向下更新了,因为这个区间的值已经不统一了。

其实这就是Lazy思想:

介绍Lazy思想:lazy-tag思想,记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。
 
在此通俗的解释我理解的Lazy意思,比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,它的节点标记为rt,这时tree[rt].l == a && tree[rt].r == b 这时我们可以一步更新此时rt节点的sum[rt]的值,sum[rt] += c * (tree[rt].r - tree[rt].l + 1),注意关键的时刻来了,如果此时按照常规的线段树的update操作,这时候还应该更新rt子节点的sum[]值,而Lazy思想恰恰是暂时不更新rt子节点的sum[]值,到此就return,直到下次需要用到rt子节点的值的时候才去更新,这样避免许多可能无用的操作,从而节省时间 。

 1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <cstdlib> 6 #include <algorithm> 7 #define LL __int64 8 const int maxn = 100000+10; 9 using namespace std;10 int n;11 struct line12 {13     int l, r, val;  //val代表这个区间的值,==-1表示这个区间值不统一,而且已经向下更新了14 }tr[4*maxn];15 16 void build(int o, int l, int r)17 {18     tr[o].l = l; tr[o].r = r;19     tr[o].val = 1;20     if(l==r)  return;21     int mid = (l+r)/2;22     build(2*o, l, mid);23     build(2*o+1, mid+1, r);24 }25 void update(int o, int l, int r, int v)26 {27     if(tr[o].l==l && tr[o].r==r)  //找到区间以后只更新这个区间的val就行了,不用向下了28     {29         tr[o].val = v;30         return;31     }32     if(tr[o].val != -1) //如果在查找的过程中目标区间之前的区间没有向下更新,就向下更新一下,因为下面的值不一样了。33     {34         tr[2*o].val = tr[o].val;35         tr[2*o+1].val = tr[o].val;36         tr[o].val = -1;  //向下更新完以后,把这个区间的val标记为已经向下更新了。37     }38     int mid = (tr[o].l+tr[o].r)/2;39     if(r<=mid) update(2*o, l, r, v);40     else if(l > mid) update(2*o+1, l, r, v);41     else42     {43         update(2*o, l, mid, v);44         update(2*o+1, mid+1, r, v);45     }46 }47 int query(int o, int l, int r)48 {49     if(tr[o].val!=-1)  //说明这一段还没有向下更新,值是统一的,可以加上这一段和返回了。50         return tr[o].val*(r-l+1);51     int mid = (tr[o].l+tr[o].r)/2;52     if(r<=mid) return query(2*o, l, mid);53     else if(l > mid) return query(2*o+1, mid+1, r);54     else55     {56        return query(2*o, l, mid)+query(2*o+1, mid+1, r);57     }58 }59 int main()60 {61     int t, q, ca = 1;62     int x, y, z;63     scanf("%d", &t);64     while(t--)65     {66         scanf("%d%d", &n, &q);67         build(1, 1, n);68         while(q--)69         {70             scanf("%d%d%d", &x, &y, &z);71             update(1, x, y, z);72         }73         printf("Case %d: The total value of the hook is %d.\n", ca++, query(1, 1, n));74     }75     return 0;76 }