一个空间怎么放2个网站,邯郸网站建设兼职,工业设计好就业吗,网站防止采集http://poj.org/problem?id3468 题意#xff1a; 给出一串数#xff0c;每次在一个区间内增加c#xff0c;查询[a,b]时输出a、b之间的总和。 思路#xff1a; 总结一下懒惰标记的用法吧。 比如要对一个区间范围内的数都要加c#xff0c;在找到这个区间之后#xff0c;本…http://poj.org/problem?id3468 题意 给出一串数每次在一个区间内增加c查询[a,b]时输出a、b之间的总和。 思路 总结一下懒惰标记的用法吧。 比如要对一个区间范围内的数都要加c在找到这个区间之后本来它的孩子结点也是需要更新的但是我们可以暂时不更新如果到时候需要用到这些孩子结点的时候我们再来更新。这个时候就要用到懒惰标记了也就是add[o]c之后它的孩子结点更新时就只需要加上add[o]就可以了。 1 #includeiostream2 #includestring3 #includecstring4 #includecstdio5 using namespace std;6 7 const int maxn 100000 10;8 int n, m;9 10 long long add[maxn 2];11 long long sum[maxn 2];12 13 void PushDown(int o, int m)14 {15 if (add[o])16 {17 //传递懒惰标记18 add[o 1] add[o];19 add[o 1 | 1] add[o];20 //更新子节点的值21 sum[o 1] add[o] * (m - (m 1));22 sum[o 1 | 1] add[o] * (m 1);23 //出去懒惰标记24 add[o] 0;25 }26 }27 28 void PushUp(int o)29 {30 sum[o] sum[o 1] sum[o 1 | 1];31 }32 33 void build(int L, int R, int o)34 {35 add[o] 0;36 if (L R)37 {38 scanf(%lld, sum[o]);39 return;40 }41 int mid (L R) / 2;42 build(L, mid, 2 * o);43 build(mid 1, R, 2 * o 1);44 PushUp(o);45 }46 47 void update(int L, int R, int x, int l,int r,int o)48 {49 if (L l R r) //如果找到区间了则不需要往下更新孩子结点了等下次需要时再更新50 {51 add[o] x;52 sum[o] (r - l 1)*x;53 return;54 }55 PushDown(o, r - l 1);56 int mid (l r) / 2;57 if (L mid)58 update(L, R, x, l, mid, 2 * o);59 if (R mid)60 update(L, R, x, mid 1, r, 2 * o 1);61 PushUp(o);62 }63 64 long long query(int L, int R, int l, int r, int o)65 {66 if (L l R r)67 return sum[o];68 PushDown(o, r - l 1);69 int mid (l r) / 2;70 long long ans 0;71 if (L mid)72 ans query(L, R, l, mid, 2 * o);73 if (R mid)74 ans query(L, R, mid 1, r, 2 * o 1);75 return ans;76 }77 78 79 int main()80 {81 //freopen(D:\\txt.txt, r, stdin);82 while (~scanf(%d%d, n, m))83 {84 build(1, n, 1);85 char c[5];86 int x, y, z;87 while (m--)88 {89 scanf(%s, c);90 if (c[0] Q)91 {92 scanf(%d%d, x, y);93 printf(%lld\n, query(x, y, 1, n, 1));94 }95 else96 {97 scanf(%d%d%d, x, y, z);98 update(x, y, z, 1, n, 1);99 }
100 }
101 }
102 } 转载于:https://www.cnblogs.com/zyb993963526/p/6561795.html
