链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698
刚开始看到这个题的时候还自作聪明，这次不是区间集体增加一个值了，而是更改为某个值 ，想到我不用线段树了不就好了，反正只是最后只查询一次
我每次都给它修改好了，也不建树了，最后输出之前来遍历一遍······然后就TLE了，看来还是处理不来数据量比较大的情况的，复杂度O(N)但是常数太大
1 #include <string> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 7 const int N = 100010; 8 int num[N]; 9 10 int main() 11 { 12 int t,n,q,x,y,b,i,j; 13 int ca = 1; 14 cin >> t; 15 while(t--) 16 { 17 memset(num,0,sizeof num); 18 scanf("%d",&n); 19 for(i = 1;i <= n;i++) 20 num[i] = 1; 21 scanf("%d",&q); 22 for(i = 1;i <= q;i++) 23 { 24 scanf("%d %d %d",&x,&y,&b); 25 for(j = x;j <= y;j++) 26 num[j] = b; 27 } 28 int p = 0; 29 for(i = 1;i <= n;i++) 30 p += num[i]; 31 printf("Case %d: The total value of the hook is %d. ",ca++,p); 32 } 33 34 return 0; 35 } 36 37 // 一不小心删代码删多了 又补了几行 反正不是AC代码 问题不大 2333
这下就不得不用线段树了，但是这次单点更新不是加一个值了，所以需要改一改之前的代码
原本是+t或者-t 现在修改为+(t-num[i]) 这样就巧妙的避开了问题 但是提交后仍然TLE 还需要进行优化
1 #include <string> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 #define N 100001 9 10 int num[N]; 11 struct node 12 { 13 int l,r; 14 int sum; 15 int mid() 16 { 17 return (l+r)/2; 18 } 19 }tree[N*4]; 20 21 void BuildTree(int root,int l,int r) 22 { 23 tree[root].l = l; 24 tree[root].r = r; 25 if(l == r) 26 { 27 tree[root].sum = num[l]; 28 return ; 29 } 30 BuildTree(root*2,l,(l+r)/2); 31 BuildTree(root*2+1,(l+r)/2+1,r); 32 tree[root].sum = tree[root*2].sum+tree[root*2+1].sum; 33 } 34 35 void add(int root,int i,int t) 36 { 37 tree[root].sum += (t-num[i]); 38 if(tree[root].l == i && tree[root].r == i) 39 { 40 num[i] = t; 41 return ; 42 } 43 if(i <= tree[root].mid()) 44 add(root*2,i,t); 45 else 46 add(root*2+1,i,t); 47 } 48 49 int query(int root,int s,int e) 50 { 51 if(tree[root].l == s && tree[root].r == e) 52 return tree[root].sum; 53 if(e <= tree[root].mid()) 54 return query(root*2,s,e); 55 else 56 if(s > tree[root].mid()) 57 return query(root*2+1,s,e); 58 else 59 return query(root*2,s,tree[root].mid())+query(root*2+1,tree[root].mid()+1,e); 60 } 61 62 int main() 63 { 64 int t,n,q,x,y,b,i,j; 65 int ca = 1; 66 cin >> t; 67 while(t--) 68 { 69 scanf("%d",&n); 70 for(i = 1;i <= n;i++) 71 num[i] = 1; 72 BuildTree(1,1,n); 73 scanf("%d",&q); 74 for(i = 1;i <= q;i++) 75 { 76 scanf("%d %d %d",&x,&y,&b); 77 for(j = x;j <= y;j++) 78 { 79 add(1,j,b); 80 } 81 } 82 83 printf("Case %d: The total value of the hook is %d. ",ca++,query(1,1,n)); 84 } 85 86 return 0; 87 }
终于在看过别人的写法以后AC了 但是现在还是对线段树不是很理解
稍后会打上详细注释
1 #include <string> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 #define N 100001 9 10 11 struct node 12 { 13 int l,r; 14 int same; 15 int sum; 16 }tree[N*4]; 17 18 void BuildTree(int root,int l,int r) 19 { 20 tree[root].l = l; 21 tree[root].r = r; 22 if(l == r) 23 { 24 tree[root].same = 1; 25 tree[root].sum = 1; 26 } 27 else 28 { 29 int mid = (l+r)/2; 30 BuildTree(root*2,l,mid); 31 BuildTree(root*2+1,mid+1,r); 32 tree[root].same = 0; 33 tree[root].sum = (tree[root*2].sum + tree[root*2+1].sum); 34 } 35 } 36 37 void update(int root,int L,int R,int t) 38 { 39 if(tree[root].l == L && tree[root].r == R) 40 { 41 tree[root].same = t; 42 tree[root].sum = (R-L+1)*t; 43 } 44 else 45 { 46 if(tree[root].same > 0) 47 { 48 tree[root*2].same = tree[root].same; 49 tree[root*2].sum = (tree[root*2].r-tree[root*2].l+1)*tree[root*2].same; 50 tree[root*2+1].same = tree[root].same; 51 tree[root*2+1].sum = (tree[root*2+1].r-tree[root*2+1].l+1)*tree[root*2+1].same; 52 } 53 tree[root].same = 0; // 不懂 54 int mid = (tree[root].l+tree[root].r)/2; 55 if(R <= mid) 56 update(root*2,L,R,t); 57 else 58 if(L > mid) 59 update(root*2+1,L,R,t); 60 else 61 { 62 update(root*2,L,mid,t); 63 update(root*2+1,mid+1,R,t); 64 } 65 tree[root].sum = tree[root*2].sum+tree[root*2+1].sum; 66 } 67 } 68 69 int main() 70 { 71 int t,n,q,x,y,b,i; 72 int ca = 1; 73 cin >> t; 74 while(t--) 75 { 76 scanf("%d",&n); 77 // cout << n << endl; 78 BuildTree(1,1,n); 79 scanf("%d",&q); 80 for(i = 1;i <= q;i++) 81 { 82 scanf("%d %d %d",&x,&y,&b); 83 update(1,x,y,b); 84 } 85 printf("Case %d: The total value of the hook is %d. ",ca++,tree[1].sum); 86 } 87 88 return 0; 89 }