hdu1698 Just a Hook 线段树区间更新懒操作

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1698

题意:

输入一个n表示一段长度为n的区间，有n个编号为1~n的点，初始值全部为1。有q个操作，每个操作有3个数：l，r，v表示将区间l~r的所有元素修改为v。
求经过q次修改后的整个区间的值之和。

题解:

线段树。区间更新 lazy。需要用的时候再pushdown
一个点一个点的更新之所以慢，是因为每个被该点影响的点我们都需要更新。为了能”顺便“更新，我们在每个结点上多维护一个信息（lazy），表示上次该区间修改的值是多少，然后然后每次向下更新之前将标记更新到儿子结点（pushdowm）

代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 1e5+10;
 17 
 18 int n,q;
 19 
 20 struct node{
 21     int l,r;
 22     ll sum,lazy;
 23     void update(ll x){
 24         sum = 1LL * (r-l+1)*x;
 25         lazy = x;
 26     }
 27 }tree[maxn<<2];
 28 
 29 void pushup(int rt){
 30     tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;
 31 }
 32 
 33 void pushdown(int rt){
 34     int lazyval = tree[rt].lazy;
 35     if(lazyval){
 36         tree[rt<<1].update(lazyval);
 37         tree[rt<<1|1].update(lazyval);
 38         tree[rt].lazy = 0;
 39     }
 40 }
 41 
 42 
 43 void build(int rt,int l,int r){
 44     tree[rt].l = l,tree[rt].r = r;
 45     tree[rt].sum = 0;
 46     tree[rt].lazy = 0;
 47     if(l == r){
 48         tree[rt].sum = 1;
 49     }else{
 50         int mid = (l+r)/2;
 51         build(rt<<1,l,mid);
 52         build(rt<<1|1,mid+1,r);
 53         pushup(rt);
 54     }
 55 }
 56 
 57 void update(int rt, int l,int r,ll val){
 58     int L = tree[rt].l, R = tree[rt].r;
 59     if(l<=L && R<=r){
 60         tree[rt].update(val);
 61     }else{
 62         pushdown(rt);
 63         int mid = (L+R) / 2;
 64         if(mid >= l) update(rt<<1,l,r,val);
 65         if(r > mid) update(rt<<1|1,l,r,val);
 66         pushup(rt);
 67     }
 68 }
 69 
 70 ll query(int rt,int l,int r){
 71     int L = tree[rt].l, R = tree[rt].r;
 72     if(l<=L && R<=r){
 73         return tree[rt].sum;
 74     }else{
 75         pushdown(rt);
 76         ll ans = 0;
 77         int mid = (L+R) / 2;
 78         if(mid >= l) ans += query(rt<<1,l,r);
 79         if(r > mid) ans += query(rt<<1|1,l,r);
 80         pushup(rt);
 81         return ans;
 82     }
 83 }
 84 
 85 int main(){
 86     int T = read();
 87     for(int cas=1; cas<=T; cas++){
 88         n = read();
 89         build(1,1,n);
 90         q = read();
 91         for(int i=1; i<=q; i++){
 92             int l,r,val;
 93             scanf("%d%d%d",&l,&r,&val);
 94             update(1,l,r,val);
 95         }
 96         ll ans = query(1,1,n);
 97         cout << "Case " << cas << ": The total value of the hook is " << ans << ".
";
 98     }
 99 
100     return 0;
101 }

hdu1698 Just a Hook 线段树 区间更新 懒操作

题目链接:

题意:

题解:

代码:

hdu1698 Just a Hook 线段树区间更新懒操作