Just a Hook

  1 #include <map>
  2 #include <stack>
  3 #include <queue>
  4 #include <cmath>
  5 #include <string>
  6 #include <limits>
  7 #include <cstdio>
  8 #include <cstdlib>
  9 #include <cstring>
 10 #include <iostream>
 11 #include <algorithm>
 12 #define Scc(c) scanf("%c",&c)
 13 #define Scs(s) scanf("%s",s)
 14 #define Sci(x) scanf("%d",&x)
 15 #define Sci2(x, y) scanf("%d%d",&x,&y)
 16 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z)
 17 #define Scl(x) scanf("%I64d",&x)
 18 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y)
 19 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z)
 20 #define Pri(x) printf("%d\n",x)
 21 #define Prl(x) printf("%I64d\n",x)
 22 #define Prc(c) printf("%c\n",c)
 23 #define Prs(s) printf("%s\n",s)
 24 #define For(i,x,y) for(int i=x;i<y;i++)
 25 #define For_(i,x,y) for(int i=x;i<=y;i++)
 26 #define FFor(i,x,y) for(int i=x;i>y;i--)
 27 #define FFor_(i,x,y) for(int i=x;i>=y;i--)
 28 #define Mem(f, x) memset(f,x,sizeof(f))
 29 #define LL long long
 30 #define ULL unsigned long long
 31 #define MAXSIZE 100005
 32 #define INF 0x3f3f3f3f
 33 const int mod=1e9+7;
 34 const double PI = acos(-1.0);
 35 
 36 using namespace std;
 37 struct node
 38 {
 39     int left,right;
 40     int lazy;
 41     int tag;
 42     int sum;
 43 } tree[MAXSIZE*4];
 44 void build(int i,int l,int r)
 45 {
 46     tree[i].left=l;
 47     tree[i].right=r;
 48     tree[i].lazy=0;
 49     tree[i].tag=0;
 50     if(l==r)
 51     {
 52         tree[i].sum=1;
 53         return ;
 54     }
 55     int mid=(l+r)/2;
 56     build(i<<1,l,mid);
 57     build(i<<1|1,mid+1,r);
 58     tree[i].sum=tree[i*2].sum+tree[i<<1|1].sum;
 59 }
 60 void Update(int i,int l,int r,int v)
 61 {
 62     if(tree[i].left==l&&tree[i].right==r)
 63     {
 64         tree[i].sum=(r-l+1)*v;
 65         tree[i].tag=v;
 66         tree[i].lazy=1;
 67         return ;
 68     }
 69     int mid=(tree[i].left+tree[i].right)/2;
 70     if(tree[i].lazy==1)
 71     {
 72         tree[i].lazy=0;
 73         Update(i<<1,tree[i].left,mid,tree[i].tag);
 74         Update(i<<1|1,mid+1,tree[i].right,tree[i].tag);
 75         tree[i].tag=0;
 76     }
 77     if(r<=mid)
 78         Update(i<<1,l,r,v);
 79     else if(l>mid)
 80         Update(i<<1|1,l,r,v);
 81     else
 82     {
 83         Update(i<<1,l,mid,v);
 84         Update(i<<1|1,mid+1,r,v);
 85     }
 86     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 87 }
 88 int main()
 89 {
 90     int t;
 91     Sci(t);
 92     int k=1;
 93     while(t--)
 94     {
 95         int n;
 96         Sci(n);
 97         int m;
 98         Sci(m);
 99         build(1,1,n);
100         int a,b,c;
101         while(m--)
102         {
103             Sci3(a,b,c);
104             Update(1,a,b,c);
105         }
106         printf("Case %d: The total value of the hook is %d.\n",k++,tree[1].sum);
107     }
108     return 0;
109 }