Thursday, 16 July 2015

****Addition and Multiplication

                               

Addition and Multiplication 

You are given a one dimensional integer array A of length N. You need to maintain the array under Qqueries of the following four types. Assume 1-based indexing and M = 109 + 7.
Query 1 : 1 x y v 

This implies adding v to array A to all the indices from x to y, i.e.,
for (i = x; i <= y; i++)	
	Ai += v;
	Ai %= M;
Query 2 : 2 x y v 
This implies multiplying the scalar v with the array A for all the indices from x to y, i.e.,
for (i = x; i <= y; i++)	
        Ai *= v
        Ai %= M
Query 3 : 3 x y v 
This implies initializing the array A at all the indices from x to y with the value v, i.e.,
for (i = x; i <= y; i++)	
	Ai = v
Query 4 : 4 x y

This is a report query which needs to find the sum of the values in A from x to y, i.e.,
sum = 0;
for (i = x; i <= y; i++)
	sum += Ai
	sum %= M
Output sum.
Note: a%b represents the remainder of a when divided by b.

Input

  • First line contains two space separated integers N, Q.
  • Next line contains N space separated integers denoting the array A.
  • Next Q lines contain queries which can be of any of the above four types.

Output

  • For each query of type 4, output a single integer corresponding to the answer in a single line.

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • 1 ≤ Initial value of Ai ≤ 109
  • 1 ≤ v ≤ 109

Subtasks

  • Subtask 1: Queries are of type 1, 3 and 4. Points - 5.
  • Subtask 2: Queries are of type 2, 3 and 4. Points - 5.
  • Subtask 3: Queries are of type 1, 2 and 4. Points - 30.
  • Subtask 4: All the queries are present. Points - 60.

Example

Input:
4 4
1 2 3 4
4 1 4
1 1 3 10
2 2 4 2
4 1 4

Output:
10
69

Explanation

Initial A : [1, 2, 3, 4]
Result of first query : 1 + 2 + 3 + 4 = 10
A after second query: [ 11, 12, 13, 4]
A after third query : [ 11, 24, 26, 8]
Result of fourth query : 11 + 24 + 26 + 8 = 69

*************************************************************QUICK EXP****************************************

PROBLEM:

Given array A of N size and M operations of type:
  1. Add v to all elements in a range.
  2. Multiply v to all elements in a range.
  3. Reset all items to v in a range.
  4. Report sum in a range.
**********************************************************EDITORIAL*********************************************

IN THIS PROBLEM EACH NODE OF SEG  LAZY TREE   WILL CONTAINS   3 ELEMENTS 
1- MUL MULTIPLICATION VALUE  WHICH NEED TO MULTIPLY 
2- ADDITION VAUE WHICH NEED TO ADD 
3 -  REPLACE  VALUE WHICH NEED TO UPDATE 
 THERE ARE TWO PARTS TO UPDATE
(1) UPDATING THE LAZY NODE
 FIRST WE CHECK THE LAZY NODE FOR A PENDING CHANGE OPERATION. IF THE NODE HAS A SET OPERATION THAT IS YET TO BE DONE THEN WE CHANGE THE SUM OF IN TREE AND COPY THE ADD VALUES AND MULITPLY VALUES TO THE LAZYS OF THE CHILD.
IF THERE IS ONLY ADD AND MUL OPERATION THAN WE DO THE OPERATION AS FOLLOWS
            CHILD[NODE].SUM=LAZY[NODE].MUL*CHILD[NODE].SUM+LAZY[NODE].SUM
          CHILD[NODE].MUL=LAZY[NODE].MUL*CHILD[NODE].MUL;
(2) THE SECONDPART IS UPDATING THE TREE NODE IF THE RANGE COPLETELY LIES IN THE UPDATED RABGE
      (1) IF TYPE IS SET
    THEN WE ADD THIS VALUE TO TREE [NODE] AND RESET THE CHILD LAZY(ADD,MULTIPLY) AND ONLY CARR THE SETVALUE TO THE LAZY.0
(2)  IF THE PRESENT UPDATE IS ADD
THEN WE ADD TO THE ENTIRE RANGE IN TREE AND ADD THESE VALUES TO LAZY [CHILDNODE].ADD
(3) IF THE PRESENT UPDATE IS MULTIPLY THEN WE MULTIPLY THE LAZY NODES WITH THIS VALUE AND ALSO 
MULTIPLY THE SUM WITH THIS VALUE.
         SEE THE CODE FOR ILLUSTRATION


*********************************************************CODE*****************************
  1. #include<iostream>
  2. using namespace std;
  3. typedef long long int lli;
  4. #include<bits/stdc++.h>
  5. #define M 1000000007
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<set>
  10. #include<stdio.h>
  11. struct node
  12. {
  13. lli product;
  14. lli plush;
  15. lli reinit;
  16. } pending[1000000];
  17. lli seg[1000000];
  18. lli arr[1000000];
  19. lli ul,uu;
  20. lli qu,ql;
  21. int type;
  22. lli val;
  26. void update(lli index,lli begin,lli end)
  27. {
  28. if(pending[index].reinit!=0 || pending[index].plush!=0 || pending[index].product!=1)
  29. {
  30. int flag=0;
  31. if(pending[index].reinit!=0)
  32. {
  33. flag=1;
  34. seg[index]=((end-begin+1)*pending[index].reinit)%M;
  35. if(begin!=end)
  36. {
  39. pending[2*index].reinit=pending[index].reinit;
  40. pending[2*index+1].reinit=pending[index].reinit;
  41. pending[2*index].plush=pending[index].plush;//((pending[index].product*pending[2*index].plush)%M+pending[index].plush)%M;
  42. pending[2*index+1].plush=pending[index].plush;//((pending[index].product*pending[2*index+1].plush)%M+pending[index].plush)%M;
  43. pending[2*index].product=pending[index].product;//(pending[index].product * pending[2*index].product)%M;
  44. pending[2*index+1].product=pending[index].product;//(pending[2*index+1].product*pending[index].product)%M;
  46. }
  47. }
  48. seg[index]=((seg[index]*pending[index].product)%M+(pending[index].plush*(end-begin+1))%M)%M;
  49. if(begin!=end && flag==0)
  50. {
  51. // pending[2*index].reinit=pending[index].reinit;
  52. //pending[2*index+1].reinit=pending[index].reinit;
  53. pending[2*index].plush=((pending[index].product*pending[2*index].plush)%M+pending[index].plush)%M;
  54. pending[2*index+1].plush=((pending[index].product*pending[2*index+1].plush)%M+pending[index].plush)%M;
  55. pending[2*index].product=(pending[index].product*pending[2*index].product)%M;
  56. pending[2*index+1].product=(pending[2*index+1].product*pending[index].product)%M;
  57. }
  58. pending[index].product=1;
  59. pending[index].plush=0;
  60. pending[index].reinit=0;
  61. }
  62. if(begin>end || ul>end || uu<begin) return ;
  63. else if(begin>=ul && end<=uu)
  64. {
  65. if(type==1)
  66. {
  67. seg[index]=(seg[index]+(end-begin+1)*val)%M;
  68. if(end!=begin)
  69. {
  70. pending[2*index].plush=(pending[2*index].plush+val)%M;
  71. pending[2*index+1].plush= (pending[2*index+1].plush+val)%M;
  72. }
  74. }
  75. else if(type==2)
  76. {
  77. seg[index]=(seg[index]*val)%M;
  78. if(begin!=end)
  79. {
  80. pending[2*index].product=(pending[2*index].product*val)%M;
  81. pending[2*index+1].product=(pending[2*index+1].product*val)%M;
  82. pending[2*index].plush=(pending[2*index].plush*val)%M;
  83. pending[2*index+1].plush=(pending[2*index+1].plush*val)%M;
  84. }
  86. }
  87. if(type==3)
  88. {
  89. seg[index]=(val*(end-begin+1))%M;
  90. if(begin!=end)
  91. {
  94. pending[2*index].reinit=val;
  95. pending[2*index+1].reinit=val;
  96. pending[2*index].plush=0;
  97. pending[2*index+1].plush=0;
  98. pending[2*index].product=1;
  99. pending[2*index+1].product=1;
  100. }
  101. }
  102. return ;
  103. }
  104. update(2*index,begin,(begin+end)/2);
  105. update(2*index+1,(begin+end)/2+1,end);
  106. seg[index]= (seg[2*index]+seg[2*index+1])%M;
  109. }
  110. lli build(int index,int begin,int end)
  111. {
  112. if(begin==end)
  113. {
  114. seg[index]=arr[begin];
  115. return seg[index];
  116. }
  117. if(begin>end) return 0;
  118. build(2*index,begin,(begin+end)/2);
  119. build(2*index+1,(begin+end)/2+1,end);
  120. seg[index]=(seg[2*index+1]+seg[2*index])%M;
  122. }
  123. lli query(int index,int begin,int end)
  124. {
  126. if(pending[index].reinit!=0 || pending[index].plush!=0 || pending[index].product!=1)
  127. {
  128. int flag=0;
  129. if(pending[index].reinit!=0)
  130. {
  131. flag=1;
  132. seg[index]=((end-begin+1)*pending[index].reinit)%M;
  133. if(begin!=end)
  134. {
  137. pending[2*index].reinit=pending[index].reinit;
  138. pending[2*index+1].reinit=pending[index].reinit;
  139. pending[2*index].plush=pending[index].plush;//((pending[index].product*pending[2*index].plush)%M+pending[index].plush)%M;
  140. pending[2*index+1].plush=pending[index].plush;//((pending[index].product*pending[2*index+1].plush)%M+pending[index].plush)%M;
  141. pending[2*index].product=pending[index].product;//(pending[index].product * pending[2*index].product)%M;
  142. pending[2*index+1].product=pending[index].product;//(pending[2*index+1].product*pending[index].product)%M;
  144. }
  145. }
  146. seg[index]=((seg[index]*pending[index].product)%M+(pending[index].plush*(end-begin+1))%M)%M;
  147. if(begin!=end && flag==0)
  148. {
  149. // pending[2*index].reinit=pending[index].reinit;
  150. // pending[2*index+1].reinit=pending[index].reinit;
  151. pending[2*index].plush=((pending[index].product*pending[2*index].plush)%M+pending[index].plush)%M;
  152. pending[2*index+1].plush=((pending[index].product*pending[2*index+1].plush)%M+pending[index].plush)%M;
  153. pending[2*index].product=(pending[index].product*pending[2*index].product)%M;
  154. pending[2*index+1].product=(pending[2*index+1].product*pending[index].product)%M;
  155. }
  156. pending[index].product=1;
  157. pending[index].plush=0;
  158. pending[index].reinit=0;
  159. }
  160. if(begin>end || begin>qu || end<ql) return 0 ;
  161. if(begin>=ql && end<=qu)
  162. {
  163. return seg[index];
  164. }
  165. lli a=query(2*index,begin,(begin+end)/2);
  166. lli b=query(2*index+1,(begin+end)/2+1,end);
  167. return (a+b)%M;
  169. }
  170.  
  172. int main()
  173. {
  174. int t;
  176. lli n,m;
  178. scanf("%lld %lld ",&n,&m);
  179. for(int i=0;i<n;i++)
  180. {
  181. scanf("%lld",&arr[i]);
  182. }
  183. build(1,0,n-1);
  184. // cout<<" build seg array "<<endl;
  185. // for(int i=0;i<10;i++) cout<<seg[i]<<" ";
  186. //cout<<endl;
  187. for(int i=0;i<4*n+100;i++)
  188. {
  189. pending[i].product=1;
  190. pending[i].plush=0;
  191. pending[i].reinit=0;
  192. }
  195. for(int i=0;i<m;i++)
  196. {
  197. // lli type;
  198. scanf("%d",&type);
  199. //cout<<" type "<<type<<endl;
  200. if(type==1)
  201. {
  202. // cout<<"type1"<<endl;
  203. scanf("%lld %lld %lld",&ul,&uu,&val);
  204. ul-=1;
  205. uu-=1;
  206. update(1,0,n-1);
  207. }
  208. if(type==2)
  209. {
  210. // cout<<"type2"<<endl;
  211. scanf("%lld %lld %lld",&ul,&uu,&val);
  212. ul-=1;
  213. uu-=1;
  214. update(1,0,n-1);
  215. }
  216. if(type==3)
  217. {
  218. // cout<<"type3"<<endl;
  219. scanf("%lld %lld %lld",&ul,&uu,&val);
  220. ul-=1;
  221. uu-=1;
  222. update(1,0,n-1);
  224. }
  225. if(type==4)
  226. {
  227. //cout<<"type4"<<endl;
  228. scanf("%lld %lld",&ql,&qu);
  229. ql-=1;
  230. qu-=1;
  231. lli ans=query(1,0,n-1);
  232. cout<<ans<<endl;
  233. }
  234. }
  236. return 0;
  237. }




********************************************CHEF EDITORIAL******************************************************

QUICK EXPLANATION:

================
Build a segment tree, where at each node we store sum and variables mul and add, which denotes that the lazy update Ai←mul∗Ai+add needs to be applied. If required, we update the current node's sum and variables and propagate the laziness down the tree. Also, an multiplication update v at a node can be summarised as mul←mul∗v and add←add∗v and also addition update v at a node can be written as add←add+v. Set operation with value v can be written as mul←0 and add←v.

EXPLANATION:

================

BASIC SEGMENT TREE STUFF

I assume you know how segment trees and lazy propagation work and the basic concepts behind them like time complexity, nodes, intervals. First, I'll introduce some terminology I'm going to use.
  • Node: It's one of the nodes in the segment tree, it represents a contiguous interval of the array A.
  • Interval of a node is the actual range covered by the node.
  • Answer of a node is defined the actual value needed for interval queries. Here, for example, we need sum of values in the range.
Let's think step by step here.
  • For range query problems, try to see if segment tree can be used.
  • When does segment tree work? When you can merge two contiguous intervals(i.e nodes) to get answer of merged interval(node) in sublinear time. If complexity of merging is O(K), then complexity for each operation can be worst case O(log N∗K). For example, when we talk about range minimum function, we can get minimum value of merged interval by taking minimum of answers of two individual intervals.
  • Also, for range updates you need to use lazy propagation. What does lazy propagation require to work? It requires that for an interval if we have multiple update operations, we can calculate the answer for that interval without actually updating every element in that interval. For example, if we are trying to find range minimum and range updation query is increase all elements by value v, then our new minimum is sum of existing minimum with v. Here also, we should be able to do this operation in sublinear time because it contributes to the factor of updations and queries.
Let's see how we use above two points to find here a solution using segment trees. Let's see the query part first: query is range sum, so merging two intervals is easy, just take the individual sums.

THE LAZY PROPAGATION SOLUTION

Now, let's see how we can handle all updations in such a way that we can find answer for an interval without actually updating the whole interval. We are going to store some data about the updations being done at that interval node and process it to find the answer. What could be this data? How do we find out? We need to observe what kind of operations we are doing. After some certain updations, our Ai could be transformed to something like ((Ai∗v1+v2)∗v3+v4+v5)∗v6+v7, where v1 to v7 are values of range multiplication or range addition. Now, we can store all these values v1 to v7 at our node, but we might have to do O(number of queries) operations at each node, which is not really sublinear. We need to find a compact notation at each node interval.
Now, thing worth noting here is that Ai has been transformed to a linear function of Ai i.e. something of form (mul∗Ai+add). Now, let's say I make one more multiplication range update v, what's the new value of Ai. It's (mul∗v∗Ai+add∗v). So, we update mul ∗= v and add ∗= v at our node. Similarly, if we make a sum update with value v, the new value of Ai is (mul∗Ai+add+v), so we update add += v. For setting all elements to v, we can just make one multiplication with 0 and then addition with value v.
So, if this interval is in range L to R, for interval sum, we need ∑Ri=L(mul∗Ai+add) which we can write as (R−L+1)∗add+mul∗∑Ri=LAi. So, we have to store sum of original Ai and R and L(basically size) and two variables mul and add at each node. Now, to make things easier we can just directly store the sum of a node(i.e.* sum of all elements in that interval) instead of storing sum of original Ai. Then, for each range multiplication update or range addition update, we also update this sum along with the variables mul and add.
Also, as we do we in lazy propagation, we propagate the laziness to the children of a node, if we need to query a children of a lazy node. In this problem, we can individually propagate variables mul and add. So, if at a node mul≠1, then we can say that this node is multiplication lazy and if required, we'll propagate this variable down to the children of this node. Similarly, if at a node add≠0, we can say that this node is addition lazy and propagate this laziness down to its children.

COMPLEXITY:

For building the segment tree we need O(NlogN) and each query is O(logN), so total complexity is O(NlogN+QlogN).
        

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)