데이터 구조 - 선분 트 리 - lazy 지연 작업

A Simple Problem with Integers
Time Limit: 5000MS
 
Memory Limit: 131072K
Total Submissions: 53749
 
Accepted: 16131
Case Time Limit: 2000MS
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

Sample Output

4

55

9

15

 
  
 
  
//          ，      ~~
  ：
  
 1 #include "cstdio" //poj 3468 lazy  

 2 #include "cstring"

 3 #include "iostream"

 4 using namespace std;

 5 

 6 #define N 100005

 7 #define LL long long

 8 

 9 struct node{

10     int x,y;

11     LL sum;

12     LL add;   //                    

13 }a[3*N];

14 

15 void Build(int t,int x,int y)

16 {

17     a[t].x = x; 

18     a[t].y = y;

19     a[t].sum = a[t].add = 0;

20     if(a[t].x == a[t].y)  //      

21     {

22         scanf("%lld",&a[t].sum);

23         return ;

24     }

25     int mid = (a[t].x + a[t].y)/2;

26     Build(t<<1,x,mid);

27     Build(t<<1|1,mid+1,y);

28     a[t].sum = a[t<<1].sum + a[t<<1|1].sum;

29 }

30 

31 void Push_down(int t)  // add(  )     

32 {

33     LL add = a[t].add;

34     a[t<<1].add += add;

35     a[t<<1|1].add += add;

36     a[t<<1].sum += add*(a[t<<1].y-a[t<<1].x+1);

37     a[t<<1|1].sum += add*(a[t<<1|1].y-a[t<<1|1].x+1);

38     a[t].add = 0;

39 }

40 

41 LL Query(int t,int x,int y)

42 {

43     if(a[t].x==x &&a[t].y==y)

44         return a[t].sum;

45     Push_down(t);

46     int mid = (a[t].x + a[t].y)/2;

47     if(y<=mid)

48         return Query(t<<1,x,y);

49     if(x>mid)

50         return Query(t<<1|1,x,y);

51     else

52         return Query(t<<1,x,mid) + Query(t<<1|1,mid+1,y);

53 }

54 

55 void Add(int t,int x,int y,int k)

56 {

57     if(a[t].x==x && a[t].y==y) //        ，t           a[t].add 

58     {

59         a[t].add += k;

60         a[t].sum += (a[t].y-a[t].x+1)*k;

61         return ;

62     }

63     a[t].sum += (y-x+1)*k;

64     Push_down(t);

65     int mid = (a[t].x+a[t].y)/2;

66     if(y<=mid)

67         Add(t<<1,x,y,k);

68     else if(x>mid)

69         Add(t<<1|1,x,y,k);

70     else

71     {

72         Add(t<<1,x,mid,k);

73         Add(t<<1|1,mid+1,y,k);

74     }

75 }

76 

77 int main()

78 {

79     int n,m;

80     char ch;

81     int x,y,k;

82     scanf("%d %d",&n,&m);

83     Build(1,1,n);

84     while(m--)

85     {

86         getchar();

87         scanf("%c %d %d",&ch,&x,&y);

88         if(ch=='Q')

89             printf("%lld
",Query(1,x,y));

90         else

91         {

92             scanf("%d",&k);

93             Add(1,x,y,k);

94         }

95     }

96     return 0;

97 }