poj 3468 A Simple Problemwith Integers(セグメント化)
13100 ワード
http://acm.sdut.edu.cn/bbs/read.php?tid=5651
..本来はアップデートしかできないのですが、今は遅延マーク法をダウンデートする方法を学びました...複雑さを軽減
View Code
1 #include <iostream>
2 #include<cstdio>
3 #include<string.h>
4 using namespace std;
5 #define max 100000
6 __int64 s[max*4],te[max*4];
7 void pushup(int w)
8 {
9 s[w] = s[2*w]+s[2*w+1];
10 }
11 void pushdown(int w,int m)
12 {
13 if(te[w])
14 {
15 te[2*w]+=te[w];
16 te[2*w+1] += te[w];
17 s[2*w] += (te[w]*(m-(m/2)));
18 s[2*w+1]+=(te[w]*(m/2));
19 te[w] = 0;//
20 }
21 }
22 void build(int l,int r,int w)
23 {
24 te[w] = 0;
25 if(l==r)
26 {
27 scanf("%I64d",&s[w]);
28 return ;
29 }
30 int m = (l+r)/2;
31 build(l,m,2*w);
32 build(m+1,r,2*w+1);
33 pushup(w);
34 }
35 void add(int a,int b,int da,int l,int r,int w)
36 {
37 if(a<=l&&b>=r)
38 {
39 te[w] += da;//
40 s[w]+=da*(r-l+1);
41 return ;
42 }
43 pushdown(w,r-l+1);//
44 int m = (l+r)/2;
45 if(a<=m)
46 add(a,b,da,l,m,2*w);
47 if(b>m)
48 add(a,b,da,m+1,r,2*w+1);
49 pushup(w);
50 }
51 __int64 search(int a,int b,int l,int r,int w)
52 {
53 if(a<=l&&b>=r)
54 {
55 return s[w];
56 }
57 pushdown(w,r-l+1);
58 int m=(l+r)/2;
59 __int64 re = 0;
60 if(a<=m)
61 re+=search(a,b,l,m,2*w);
62 if(b>m)
63 re+=search(a,b,m+1,r,2*w+1);
64 return re;
65 }
66 int main()
67 {
68 int i,j,k,n,m,t,a,b,c;
69 char z;
70 scanf("%d%d",&n,&m);
71 build(1,n,1);
72 while(m--)
73 {
74 scanf("%*c%c",&z);
75 if(z=='Q')
76 {
77 scanf("%d%d",&a,&b);
78 printf("%I64d
",search(a,b,1,n,1));
79 }
80 else
81 {
82 scanf("%d%d%d",&a,&b,&c);
83 add(a,b,c,1,n,1);
84 }
85 }
86 return 0;
87 }