题目链接：http://poj.org/problem?id=3468

很基础的一道延迟标记的题

需要注意的是数据得到了加强，故这里要用__int64 

  1 #include <cmath>
  2 #include <queue>
  3 #include <string>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <iostream>
  7 #include <algorithm>
  8 #define forn(i, n) for (int i = 0; i < (n); i++)
  9 #define forab(i, a, b) for (int i = (a); i <= (b); i++)
 10 #define forba(i, b, a) for (int i = (b); i >= (a); i--)
 11 #define mset(a, n) memset(a, n, sizeof(a))
 12 #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
 13 #define P pair<int,int>
 14 #define fi first
 15 #define se second
 16 using namespace std;
 17 #define N 100000
 18 #define inf 0x3f3f3f3f
 19 #define ll long long
 20 struct SegmentTree
 21 {
 22     int l, r;
 23     __int64 data, add;
 24     #define l(x) t[x].l
 25     #define r(x) t[x].r
 26     #define data(x) t[x].data
 27     #define add(x) t[x].add
 28 } t[N * 4 + 5];
 29 __int64 temp[N], ans;
 30 int n, m;
 31 void build(int p,int l,int r)
 32 {
 33     l(p) = l;
 34     r(p) = r;
 35     add(p) = 0;
 36     if(l==r)
 37     {
 38         data(p) = temp[l];
 39         return;
 40     }
 41     int m = (r + l) / 2;
 42     int ls = 2 * p, rs = 2 * p + 1;
 43     build(ls, l, m);
 44     build(rs, m + 1, r);
 45     data(p) = data(ls) + data(rs);
 46 }
 47 void spread(int p)
 48 {
 49     if(add(p))
 50     {
 51         int ls = 2 * p, rs = ls + 1;
 52         data(ls) += add(p) * (r(ls) - l(ls) + 1);
 53         data(rs) += add(p) * (r(rs) - l(rs) + 1);
 54         add(ls) += add(p);
 55         add(rs) += add(p);
 56         add(p) = 0;
 57     }
 58 }
 59 void change(int p,int l,int r,__int64 d)
 60 {
 61     if(l<=l(p)&&r>=r(p))
 62     {
 63         data(p) += (__int64)d * (r(p) - l(p) + 1);
 64         add(p) += d;
 65         return;
 66     }
 67     spread(p);
 68     int m = (l(p) + r(p)) / 2;
 69     int ls = 2 * p, rs = 2 * p + 1;
 70     if(l<=m)
 71         change(ls, l, r, d);
 72     if(r>m)
 73         change(rs, l, r, d);
 74     data(p) = data(ls) + data(rs);
 75 }
 76 __int64 Query(int p,int l,int r)
 77 {
 78     if(l<=l(p)&&r>=r(p))
 79     {
 80         return data(p);
 81     }
 82     spread(p);
 83     int m = (l(p) + r(p)) / 2;
 84     int ls = 2 * p, rs = 2 * p + 1;
 85     ll val = 0;
 86     if(l<=m)
 87         val += Query(ls, l, r);
 88     if(r>m)
 89         val += Query(rs, l, r);
 90     return val;
 91 }
 92 int main()
 93 {
 94     scanf("%d%d", &n, &m);
 95     forab(i, 1, n) scanf("%I64d", temp + i);
 96     build(1, 1, n);
 97     forab(i,1,m)
 98     {
 99         getchar();
100         char c;
101         int a, b;
102         scanf("%c %d %d", &c, &a, &b);
103         if(c=='Q')
104         {
105             printf("%I64d\n", Query(1, a, b));
106         }
107         else
108         {
109             __int64 x;
110             scanf("%I64d", &x);
111             change(1, a, b, x);
112         }
113     }
114 }

View Code