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
", 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 }

View Code

Mind:

1.数据范围没注意, int -> long long , 以及应该注意不同的oj用的编译器不同对long long , __int64的调用也不一样

2.线段树的延迟标记的处理

3.此模板一定要留住, 留住!!!再也没有再改一次的勇气了...