首页 > 代码库 > HDU1689(Just a Hook)
HDU1689(Just a Hook)
题目地址：Just a Hook
题目大意：
在data中 一位英雄“屠夫”有个钩子，是由几段金属棒构成的，其中金属棒可以分为铜棒其val为1，银棒其val为2，金棒其val为3，其中屠夫的钩子其金属棒的初始值为1，屠夫想要进行一些操作，来改变一些区间的金属棒的val值。其改变的性质是从x->y区间的所有金属棒值改变为z。最后求出钩子的价值总和。
解题思路：
线段数，成段的更新求出总和，需要用到lazy 标记。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 const int M=100100; 44 struct tree 45 { 46 int sum; //该区间的总和 47 int lazy,tag; 48 int left,right; //记录区间的左右闭区间坐标 49 } node[M*4]; //需开四倍的空间大小 50 int p[M]; 51 int cnt; 52 void build__tree(int id,int l,int r) //建树 53 { 54 int mid=(l+r)/2; 55 node[id].left=l; //初始化赋值区间的坐标 56 node[id].right=r; 57 node[id].tag=1; 58 node[id].lazy=0; //lazy初始化 59 if (l==r) 60 { 61 node[id].sum=1; //初始化区间节点的val值 62 return ; 63 } 64 build__tree(id*2,l,mid); //左孩子 65 build__tree(id*2+1,mid+1,r); //右孩子 66 node[id].sum=node[id*2].sum+node[id*2+1].sum; //通过递归将各个区间节点val更新 67 } 68 void updata(int id,int l,int r, int v) //区间的更新 69 { 70 int mid=(node[id].left+node[id].right)/2; 71 if (node[id].left==l&&node[id].right==r) 72 { 73 node[id].lazy=1; 74 node[id].tag=v; 75 node[id].sum=(r-l+1)*v; 76 return ; 77 } 78 if (node[id].lazy==1) 79 { 80 node[id].lazy=0; 81 updata(id*2,node[id].left,mid,node[id].tag); 82 updata(id*2+1,mid+1,node[id].right,node[id].tag); 83 } 84 if (l>mid) //[l，r]在右孩子部分 85 updata(id*2+1,l,r,v); 86 else if (r<=mid) // [l，r]在左孩子部分 87 updata(id*2,l,r,v); 88 else //[l，r]区间，左右孩子都有分别递归。 89 { 90 updata(id*2,l,mid,v); 91 updata(id*2+1,mid+1,r,v); 92 } 93 node[id].sum=node[id*2].sum+node[id*2+1].sum; //通过递归将各个区间节点val更新 94 } 95 96 int main() 97 { 98 int cas; 99 scanf("%d",&cas);100 int icas=1;101 while(cas--)102 {103 int n,q;104 scanf("%d%d",&n,&q);105 build__tree(1,1,n);106 int x,y,z;107 while(q--)108 {109 scanf("%d%d%d",&x,&y,&z);110 updata(1,x,y,z);111 }112 printf("Case %d: The total value of the hook is %d.\n",icas++,node[1].sum);113 }114 return 0;115 }
HDU1689(Just a Hook)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。