{"problem":{"name":"L. All’s Wall That Ends Wall","description":{"content":"In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The ith wall consists of ai blocks stacked on top of each other. Your job is to ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10135L"},"statements":[{"statement_type":"Markdown","content":"In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The ith wall consists of ai blocks stacked on top of each other.\n\nYour job is to answer queries of two types:\n\n- For queries of the first type, print the amount of water that could be stored between all the walls.\n\n- For queries of the second type, increase the number of blocks on the xth wall by v.\n\nThe first line of input is T – the number of test cases.\n\nThe first line of each test case is integers N and Q (1 ≤ N, Q ≤ 105).\n\nThe second line contains N space-separated integers ai (1 ≤ ai ≤ 105).\n\nThe next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 104).\n\nFor each test case and query of the first type, output on a line the amount of water that could be stored between the walls.\n\n## Input\n\nThe first line of input is T – the number of test cases.The first line of each test case is integers N and Q (1 ≤ N, Q ≤ 105).The second line contains N space-separated integers ai (1 ≤ ai ≤ 105).The next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 104).\n\n## Output\n\nFor each test case and query of the first type, output on a line the amount of water that could be stored between the walls.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of walls.  \n- Let $ Q \\in \\mathbb{Z} $ be the number of queries.  \n- Let $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of non-negative integers representing the height of each wall.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. For each test case:  \n   - $ 1 \\leq N, Q \\leq 10^5 $  \n   - $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, N\\} $  \n   - For update queries: $ 1 \\leq x \\leq N $, $ 1 \\leq v \\leq 10^4 $  \n\n**Operations**  \n- **Type P (Query)**: Compute the total trapped water between walls:  \n  $$\n  W = \\sum_{i=1}^{N} \\left( \\min\\left( \\max_{j=1}^{i-1} a_j, \\max_{j=i+1}^{N} a_j \\right) - a_i \\right)^+\n  $$  \n  where $ (x)^+ = \\max(0, x) $.  \n\n- **Type U (Update)**: Update $ a_x \\leftarrow a_x + v $.  \n\n**Objective**  \nFor each query of type P, output the value of $ W $ as defined above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10135L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}