{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003eDescription\u003c/h4\u003e \n \u003cp\u003eFor the understanding of segment tree shown by Little Ho, Little Hi expressed quite satisfaction, but is satisfaction enough? So Little Hi changed the problem a bit and gave it to Little Ho:\u003c/p\u003e \n \u003cp\u003eAssume that there are N types of products placed on the shelf from left to right, numbered from 1 to N, where the price of the product with label i is Pi. Each operation of Little Hi falls into two categories: the first one is to modify the price—Little Hi gives a range [L, R] and a new price NewP, and the prices of all products in this range will be changed to NewP. The second operation is to inquire—Little Hi gives a range [L, R], and Little Ho\u0027s task is to calculate the total price of all products in this range and then inform Little Hi.\u003c/p\u003e \n \u003cp\u003eSo how should Little Ho solve such a problem?\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#myModal\"\u003eHint: Besides people\u0027s curiosity, people\u0027s laziness also drives the development of science!\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal fade\" id\u003d\"myModal\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003eHint: Besides people\u0027s curiosity, people\u0027s laziness also drives the development of science!\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e\u003cstrong\u003eLittle Hi\u0027s warm reminder: Before solving this problem, why not take a look at last week\u0027s introduction to segment trees!\u003c/strong\u003e\u003c/p\u003e \n \u003cp\u003eAfter listening to the whole problem, Little Ho said, \"Hmm... since you said it\u0027s a modification to the segment tree problem, then this problem should still be solved using a segment tree, right?\"\u003c/p\u003e \n \u003cp\u003eLittle Hi sighed and said, \"Well, you\u0027re not wrong, but is it really appropriate to judge like this... in real applications, no one will tell you, huh?\"\u003c/p\u003e \n \u003cp\u003eLittle Ho laughed, \"Don\u0027t fool me, our series has been going on for so long, I know that the application scenarios of algorithms in life are extremely limited.\"\u003c/p\u003e \n \u003cp\u003eLittle Hi looked defeated, sighed again, and said, \"Well, algorithms are like mathematics, they can make you understand things thoroughly, but in real life, many problems are either too simple or too complex, so these classic algorithms often have no place to be used.\"\u003c/p\u003e \n \u003cp\u003eSeeing Little Hi looking depressed, Little Ho hurriedly said, \"Don\u0027t be like this! Let\u0027s quickly look at today\u0027s problem—since we are using a segment tree to solve this problem, it\u0027s easy to think that \u003cstrong\u003eeach node in the segment tree maintains the sum of the values of all products in the corresponding interval\u003c/strong\u003e, so when performing each inquiry operation, we can use the same method as before—\u003cstrong\u003edecompose the inquiry interval on the tree into several pre-calculated intervals, then sum the values of these intervals maintained on the tree, which is the answer we need.\u003c/strong\u003e\"\u003c/p\u003e \n \u003cp\u003eLittle Hi nodded and said, \"This part is indeed the same as the previous problem, but how do you plan to handle the modification operation? It\u0027s not that simple this time!\"\u003c/p\u003e \n \u003cp\u003e\"The difference in this modification operation from the previous one is indeed too big—previously, only one position needed to be modified, but now it is the same as an inquiry, modifying the value of a range at once. If we continue to modify one by one using the previous method, the complexity of modification may rise to O(N)!\" Little Ho suddenly exclaimed, \"Right, then I will \u003cstrong\u003edecompose the modified range into several small intervals like an inquiry, only modify these intervals and their ancestor nodes\u0027 values, right? There will only be O(logN) intervals like this, so the modification time complexity will also be at this level!\"\u003c/strong\u003e\u003c/p\u003e \n \u003cp\u003e\"You can try doing that!\" Little Hi said with a mischievous smile.\u003c/p\u003e \n \u003cp\u003eSo Little Ho went back happily to write the program, but struggled for a long time on the test data without success. Fortunately, he finally found where his problem was, so he came back to find Little Hi again.\u003c/p\u003e \n \u003cp\u003e\"Little Hi, you\u0027re so mean! You didn\u0027t tell me about this problem. \u003cstrong\u003eIf I first modify the range [3, 9], then I will split it into [3, 3], [4, 5], [6, 8], [9, 9] 4 intervals, so only these orange intervals will be modified. But if I later inquire about the range [6, 7], I will still calculate based on the prices before the modification!\"\u003c/strong\u003e Little Ho complained.\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/4d03d03b00a161861195a4015ed2e192?v\u003d1659861152\" style\u003d\"width:100%;\" title\u003d\"1.png\"\u003e \n \u003cp\u003e\"I just said you could try doing that, but I didn\u0027t say you would pass by doing that~\" Little Hi laughed.\u003c/p\u003e \n \u003cp\u003eLittle Ho helplessly said, \"You... so now how should I solve this problem?\"\u003c/p\u003e \n \u003cp\u003e\"Think again—actually, theoretically, if the range [3, 9] is modified, the values of all green nodes should be recalculated.\" Little Hi pointed out some nodes again.\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/031ad67c0c1201db8991e65e9cf316c3?v\u003d1659861152\" style\u003d\"width:100%;\" title\u003d\"2.png\"\u003e \n \u003cp\u003e\"But in reality, it is unnecessary to do so—we can introduce something called a Lazy Tag, which is indeed for a modification operation like [3, 9], I can only modify the orange nodes, \u003cstrong\u003ebut on this basis, I need to add a lazy tag to the nodes corresponding to the 4 intervals [3, 3], [4, 5], [6, 8], [9, 9] decomposed from [3, 9]\u003c/strong\u003e, indicating \u003cstrong\u003e\u0027there was an operation before that needed to modify the prices of all nodes in this subtree, but because the values of this subtree have not been used yet, I temporarily won\u0027t make the modification\u0027. Little Hi explained.\u003c/strong\u003e \u003cimg src\u003d\"CDN_BASE_URL/f6b112f84142ab5ce65c08a0d2b561d6?v\u003d1659861152\" style\u003d\"width:100%;\" title\u003d\"3.png\"\u003e \u003c/p\u003e \n \u003cp\u003e\"But what\u0027s the use of these lazy tags?\" Little Ho asked.\u003c/p\u003e \n \u003cp\u003e\"It\u0027s actually a concept of temporarily not processing, and only processing when needed later.\" Little Hi said, \"For example, as you mentioned before, if you inquire about the range [6, 7], then when decomposing from top to bottom, you will find a lazy tag on the range [6, 8], so you should \u003cstrong\u003eperform a \u0027push-down operation\u0027 of the lazy tag—meaning to modify the values of the left and right children of the node [6, 8], and at the same time add new lazy tags to the left and right children, then remove the lazy tag of [6, 8].\u003c/strong\u003e\"\u003c/p\u003e \n \u003cp\u003e\"In other words—originally, the left and right children of [6, 8] needed to be modified together in the previous modification operation, but because the individual ranges like [6, 7], [8, 8] have not been used yet, I can temporarily not process the modification of these nodes, but use a lazy tag to record that these nodes need to be modified. Then when these values are needed later, I will perform these operations?\"\u003c/p\u003e \n \u003cp\u003e\"Exactly!\" Little Hi nodded, \"If you\u0027re still unclear, you can take a look at this pseudo code:\"\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/859040d7f05f4efa530c2534949dea3b?v\u003d1659861152\" style\u003d\"width:100%;\" title\u003d\"4.png\"\u003e \n \u003cbr\u003e \n \u003cp\u003e\"Hmm! That\u0027s right, so through the effect of lazy tags, the modification operation can also be reduced to O(logN) complexity, so this problem is perfectly solved!\"\u003c/p\u003e \n \u003cp\u003eSo Little Ho hummed a little song and happily went back to improve the algorithm~\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-primary\"\u003eSave changes\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003eInput\u003c/h4\u003e \n \u003cp\u003eEach test case (input file) contains exactly one set of test data.\u003c/p\u003e \n \u003cp\u003eThe first line of each test data is an integer N, as described earlier.\u003c/p\u003e \n \u003cp\u003eThe second line of each test data consists of N integers, describing the weight of each type of product, where the i-th integer represents the weight Pi of the product with label i.\u003c/p\u003e \n \u003cp\u003eThe third line of each test data is an integer Q, indicating the number of operations performed by Little Hi.\u003c/p\u003e \n \u003cp\u003eLines N+4 to N+Q+3 of each test data describe each operation. Each line starts with a number belonging to 0 or 1, indicating whether the line describes an inquiry or a change in the price of a product. For the N+i+3 line, if it describes an inquiry, the next two integers Li, Ri follow, indicating the range [Li, Ri] that Little Hi inquires about; if it describes a change in the price of a product, the next three integers Li, Ri, NewP follow, indicating that the prices of products in the range [Li, Ri] are all changed to NewP.\u003c/p\u003e \n \u003cp\u003eFor 100% of the data, it holds that N\u0026lt;\u003d10^5, Q\u0026lt;\u003d10^5, 1\u0026lt;\u003dLi\u0026lt;\u003dRi\u0026lt;\u003dN, 1\u0026lt;\u003dPi\u0026lt;\u003dN, 0\u0026amp;ltPi, NewP\u0026lt;\u003d10^4.\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003eOutput\u003c/h4\u003e \n \u003cp\u003eFor each set of test data, for each inquiry by Little Hi, output one line for each inquiry in the order it appears in the input, representing the result of the query: the sum of the prices of all products in the range [Li, Ri].\u003c/p\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e10\r\n4733 6570 8363 7391 4511 1433 2281 187 5166 378 \r\n6\r\n1 5 10 1577\r\n1 1 7 3649\r\n0 8 10\r\n0 1 4\r\n1 6 8 157\r\n1 3 4 1557\r\n\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e4731\r\n14596\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003eDescription\u003c/h4\u003e \n \u003cp\u003eFor the understanding of segment tree shown by Little Ho, Little Hi expressed quite satisfaction, but is satisfaction enough? So Little Hi changed the problem a bit and gave it to Little Ho:\u003c/p\u003e \n \u003cp\u003eAssume that there are N types of products placed on the shelf from left to right, numbered from 1 to N, where the price of the product with label i is Pi. Each operation of Little Hi falls into two categories: the first one is to modify the price—Little Hi gives a range [L, R] and a new price NewP, and the prices of all products in this range will be changed to NewP. The second operation is to inquire—Little Hi gives a range [L, R], and Little Ho\u0027s task is to calculate the total price of all products in this range and then inform Little Hi.\u003c/p\u003e \n \u003cp\u003eSo how should Little Ho solve such a problem?\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#myModal\"\u003eHint: Besides people\u0027s curiosity, people\u0027s laziness also drives the development of science!\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal fade\" id\u003d\"myModal\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003eHint: Besides people\u0027s curiosity, people\u0027s laziness also drives the development of science!\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e\u003cstrong\u003eLittle Hi\u0027s warm reminder: Before solving this problem, why not take a look at last week\u0027s introduction to segment trees!\u003c/strong\u003e\u003c/p\u003e \n \u003cp\u003eAfter listening to the whole problem, Little Ho said, \"Hmm... since you said it\u0027s a modification to the segment tree problem, then this problem should still be solved using a segment tree, right?\"\u003c/p\u003e \n \u003cp\u003eLittle Hi sighed and said, \"Well, you\u0027re not wrong, but is it really appropriate to judge like this... in real applications, no one will tell you, huh?\"\u003c/p\u003e \n \u003cp\u003eLittle Ho laughed, \"Don\u0027t fool me, our series has been going on for so long, I know that the application scenarios of algorithms in life are extremely limited.\"\u003c/p\u003e \n \u003cp\u003eLittle Hi looked defeated, sighed again, and said, \"Well, algorithms are like mathematics, they can make you understand things thoroughly, but in real life, many problems are either too simple or too complex, so these classic algorithms often have no place to be used.\"\u003c/p\u003e \n \u003cp\u003eSeeing Little Hi looking depressed, Little Ho hurriedly said, \"Don\u0027t be like this! Let\u0027s quickly look at today\u0027s problem—since we are using a segment tree to solve this problem, it\u0027s easy to think that \u003cstrong\u003eeach node in the segment tree maintains the sum of the values of all products in the corresponding interval\u003c/strong\u003e, so when performing each inquiry operation, we can use the same method as before—\u003cstrong\u003edecompose the inquiry interval on the tree into several pre-calculated intervals, then sum the values of these intervals maintained on the tree, which is the answer we need.\u003c/strong\u003e\"\u003c/p\u003e \n \u003cp\u003eLittle Hi nodded and said, \"This part is indeed the same as the previous problem, but how do you plan to handle the modification operation? It\u0027s not that simple this time!\"\u003c/p\u003e \n \u003cp\u003e\"The difference in this modification operation from the previous one is indeed too big—previously, only one position needed to be modified, but now it is the same as an inquiry, modifying the value of a range at once. If we continue to modify one by one using the previous method, the complexity of modification may rise to O(N)!\" Little Ho suddenly exclaimed, \"Right, then I will \u003cstrong\u003edecompose the modified range into several small intervals like an inquiry, only modify these intervals and their ancestor nodes\u0027 values, right? There will only be O(logN) intervals like this, so the modification time complexity will also be at this level!\"\u003c/strong\u003e\u003c/p\u003e \n \u003cp\u003e\"You can try doing that!\" Little Hi said with a mischievous smile.\u003c/p\u003e \n \u003cp\u003eSo Little Ho went back happily to write the program, but struggled for a long time on the test data without success. Fortunately, he finally found where his problem was, so he came back to find Little Hi again.\u003c/p\u003e \n \u003cp\u003e\"Little Hi, you\u0027re so mean! You didn\u0027t tell me about this problem. \u003cstrong\u003eIf I first modify the range [3, 9], then I will split it into [3, 3], [4, 5], [6, 8], [9, 9] 4 intervals, so only these orange intervals will be modified. But if I later inquire about the range [6, 7], I will still calculate based on the prices before the modification!\"\u003c/strong\u003e Little Ho complained.\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/4d03d03b00a161861195a4015ed2e192?v\u003d1659861152\" style\u003d\"width:100%;\" title\u003d\"1.png\"\u003e \n \u003cp\u003e\"I just said you could try doing that, but I didn\u0027t say you would pass by doing that~\" Little Hi laughed.\u003c/p\u003e \n \u003cp\u003eLittle Ho helplessly said, \"You... so now how should I solve this problem?\"\u003c/p\u003e \n \u003cp\u003e\"Think again—actually, theoretically, if the range [3, 9] is modified, the values of all green nodes should be recalculated.\" Little Hi pointed out some nodes again.\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/031ad67c0c1201db8991e65e9cf316c3?v\u003d1659861152\" style\u003d\"width:100%;\" title\u003d\"2.png\"\u003e \n \u003cp\u003e\"But in reality, it is unnecessary to do so—we can introduce something called a Lazy Tag, which is indeed for a modification operation like [3, 9], I can only modify the orange nodes, \u003cstrong\u003ebut on this basis, I need to add a lazy tag to the nodes corresponding to the 4 intervals [3, 3], [4, 5], [6, 8], [9, 9] decomposed from [3, 9]\u003c/strong\u003e, indicating \u003cstrong\u003e\u0027there was an operation before that needed to modify the prices of all nodes in this subtree, but because the values of this subtree have not been used yet, I temporarily won\u0027t make the modification\u0027. Little Hi explained.\u003c/strong\u003e \u003cimg src\u003d\"CDN_BASE_URL/f6b112f84142ab5ce65c08a0d2b561d6?v\u003d1659861152\" style\u003d\"width:100%;\" title\u003d\"3.png\"\u003e \u003c/p\u003e \n \u003cp\u003e\"But what\u0027s the use of these lazy tags?\" Little Ho asked.\u003c/p\u003e \n \u003cp\u003e\"It\u0027s actually a concept of temporarily not processing, and only processing when needed later.\" Little Hi said, \"For example"}}]}