首页 > 代码库 > Poj 3468
Poj 3468
TLE + WA 了无数次, 发现了不少毛病, 做个记录先
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 9 10 #define lson l, m, rt << 1 11 #define rson m + 1, r, rt << 1 | 1 12 13 const int maxn = 100000 + 2; 14 long long n[maxn << 2], col[maxn << 2]; 15 long long N, Q; 16 17 void pushUp(int rt) 18 { 19 n[rt] = n[rt << 1] + n[rt << 1 | 1]; 20 } 21 22 void build(int l, int r, int rt) 23 { 24 if(l == r) 25 { 26 scanf("%lld", &n[rt]); 27 return ; 28 } 29 30 int m = (l + r) >> 1; 31 build(lson); 32 build(rson); 33 34 pushUp(rt); 35 } 36 37 void pushDown(int m, int rt) 38 { 39 if(!col[rt]) return ; 40 41 col[rt << 1] += col[rt]; 42 col[rt << 1 | 1] += col[rt]; 43 44 n[rt << 1] += (m - (m >> 1)) * col[rt]; 45 n[rt << 1 | 1] += (m >> 1) * col[rt]; 46 47 col[rt] = 0; 48 } 49 50 void upDate(int L, long long R, long long c, long long l, long long r, long long rt) 51 { 52 if(!c) return; 53 54 if(L <= l && R >= r) 55 { 56 col[rt] += c; 57 n[rt] += c * (r - l + 1); 58 return ; 59 } 60 61 long long m = (l + r) >> 1; 62 pushDown(r - l + 1, rt); 63 if(L <= m) upDate(L, R, c, lson); 64 if(R > m) upDate(L, R, c, rson); 65 pushUp(rt); 66 } 67 68 long long Query(long long L, long long R, long long l, long long r, long long rt) 69 { 70 if(L <= l && R >= r) 71 return n[rt]; 72 73 long long m = (l + r) >> 1, ret = 0; 74 pushDown(r - l + 1, rt); 75 76 upDate(L, R, col[rt], lson); 77 upDate(L, R, col[rt], rson); 78 col[rt] = 0; 79 80 if(L <= m) ret += Query(L, R, lson); 81 if(R > m) ret += Query(L, R, rson); 82 return ret; 83 } 84 85 int main() 86 { 87 //freopen("in", "r", stdin); 88 89 while(~scanf("%lld%lld", &N, &Q)) 90 { 91 memset(n, 0, sizeof(n)); 92 memset(col, 0, sizeof(col)); 93 94 build(1, N, 1); 95 96 for(long long i = 1; i <= Q; i++) 97 { 98 char q[5]; 99 scanf("%s", q); 100 if(!strcmp(q, "Q")) 101 { 102 long long l, r; 103 scanf("%lld%lld", &l, &r); 104 printf("%lld\n", Query(l, r, 1, N, 1)); 105 } else if(!strcmp(q, "C")){ 106 long long l, r, c; 107 scanf("%lld%lld%lld", &l, &r, &c); 108 upDate(l, r, c, 1, N, 1); 109 } 110 } 111 } 112 }
Mind:
1.数据范围没注意, int -> long long , 以及应该注意不同的oj用的编译器不同对long long , __int64的调用也不一样
2.线段树的延迟标记的处理
3.此模板一定要留住, 留住!!!再也没有再改一次的勇气了...
Poj 3468
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。