【HDOJ】【1754】I Hate It

线段树

---

　　这是一道线段树的裸题……带单点修改的RMQ

　　为什么我会想到写这么一道傻逼题呢？是因为这样……aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABQYAAABVCAIAAACU464EAAAABmJLR0QA/wD/AP+gvaeTAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAgAElEQVR4nO3df1BTd94v8M8JaMvSfbogtDSAtGCiWBa9PmHxdkZnOoBFaG/3amuH9jLWgQ6ls7sVWIedwdarrXOXhyW2u3cXeRZHHUZ56q4818cSqYXrvTjTkZKHlSwVTSS9CGSx8kB/bESr5Nw/vsnJSXJOCJCQg7xf4zjkm+855xv4wHw/5/vjcDzPE8yG13eM4zjfQlbC8zzHcSqVyqt8enr6/v377N2IiIiIiAjhJOxd3oWVC1QqVWRkJMdxXuWsssPh4HlepVKpVCrfCl4lsNghDkEJEIegBIhDUALEISgB4nBuOPY9ujoe3mbMy5o4okX+EbSxDpVKtag/AgAAAACApAeguw4PHhaWRKTyWw0WCLt9Eu5WAAAAAAAALC1IiRWBzSUIdysAAAAAAACWFqTEioBRYgAAAAAAgIWHlFgR2KLzcLcCAAAAAABgaUFKrAgYJQYAAAAAAFh4SIkBAAAAAABgiYoMdwOAiIjjuEBGiXMqujsPZQd4zpyKbq+SwI8FAAAAAABYCpASK8I8Z017Zb9C6ivOgX0zZAAAAAAAUBCr/uXsqv7X2gY+KFigK3aUpteubf+0MiWUF+nazZWd0FV397yeGsrLzNWST4m9gqCjNL3oiGcN5w+vazdXdsK33HIsT1t7WSgsabzVtDnkjZYgZL+Bpb7jdRWD7RRz8JB2Y0CnZ/XdtFszGrZEz7qVAAAAAABhJtuBl+nwiwpkkwX5pEA4xCPRNeyN37fKO0W0HCurogPmgXINkf1UXX+jTXhL6Ld7lm9I6yyOc70Q9dhF5Zeau2t6xVeJKqvO3JHgfNH18ZGMbeYU2cPlLje78s0f8O2rs/LL9M+GOPeemyWcEgvRub7eXZjbNHCrybNOn/ulxA0by3Wqb7/l/NF27ebK8kJ+lyUITBPtRESTF020MTPQg/J3Ze9hlU3mnKODpzLdv0sAAAAAAIuE3w68/xFa2WRB7pyGvUV91d08y5n3dvDv5xIRDTXsu3bg5PteQ6YdtbWXSxo/1RAR0dQQqY8fSk4iIpbW1g0f35Oc5FE+XlcxmEPUWRzHvrZuzejcEs3y0pxmcmfLHpmzmOH8CV1ht0b+cLnLzbacUsr3b3+38I8dlew7oChLOCXObRq41TTUkJXfKlfDcqz2CL3W5nd8v+D9T92/M5ufL6ETV4aIgpISS473zmqFsNyI8aW+SdqQdpAGa/rG92R6/3qMnDcdpDR/g8CPRWlpcugrIqTEAAAAALDIBKsDL04WZM7Z0Xqa1jWmEpEm9Wmq/djwfm4BWfW/bC36jTP19ThbxgGza8Jp3J497vc2rouh3qkRoiSP8riirbb2vqkRIjpva1erjzs78NE7itUXam2n8uJmGMHqaD29vqg9lUZkD5e+nFwz5MuJqOCNA7r8Wv0buYobPlzCKfGMnPdpAp/Hb9hbJI7jWeA4juM4r0LfXNfP9lqS2a/MWuLxi72UvytuI03Q0YlLxXGBzZ12GzFNmtXqmoCHlwEAAAAAFGnuHXj5ZGGGc3b9tmp1Ne+dFlrPtl3WFTZqpI4Yrzs6qd2a4dtpH7k5RRQjcURCVCrZZhzBGrL0ZWyrTiEaCexwucsFWJ7yXFHGuy0XrJVKW1GMhzDJYfdpqj1C+URhejyXHs+lx5d2icut+pfjufT4fau6+T+VS8bxDCIiIiIiIvzXYfmw3MBv56Fs9m/mi5km2ilmUyZRZmw+TR4/bw+wke1Hu3MqunMquneem8p/zjmLAwAAAABg8ZHrwMt1+L1JJQu+58zdtp36rFYisli/oO3PF5BV/7sv6t/ItRzLY1fh9nawY6/007pUr1xxbLi8ojunwpZSnS0xhXNs+HgvadfFJhElZcZobbYWk/DWlFVcs3eQdeNzKsyXRB/hQqtxtUZDMx7uc7k5lqeuWU3G6xKnDjOMEsvwmMpPRLT5A37gA+fXXbu5snhyL5pPrfzTrUoiy7E8Lp3q57CWODJy4X4QbNb0RiKiuE0bBtv7Jka2RCd5b6DVn3OOiIjU6uN7nNmvey3x2HB5bXed8BIAAAAAYHGR6sD76/B78UkWZM5Z8MaBffnZXC0RvdY2kGs5ltdS2NhDDVm1bO1xR2l6UekWdpX1a72TiITkhkPJRPZTdd055O6WExGR/VSzzSzMdk5Ibtg1lXO029mfV0dpXfU2Fmd3Fju/vtTcXVNhdu7UZT3bdrnk57nk/3Dpy82xXLNqPV2X/H6GFVJiSV5T+b1t/kV9xokWq5U2e9zI0bzeWN+WraDJAFJDyuMXe4loMKd30FUy+dlY8o6EuD2H4tjM/5nXEick79xgk1yHDAAAAACweMh24GU6/Iz/ZMHjnCnlPQPlrnc6Smuf3j+QSl3XjBnbTqYQG0beZ7WS35nbbHEv67SzEvupuv5GryQ5U9t5yPX12HB5LaU85n2ijXlqbe/kjTHamEBDn7T0v7Z/c0CHS11uLuUKhZRYiuRdn0BYr/QTFYagRcIqYjZ3WnKZse9REmuJTRPtanF02k/V9V8w2XckzOqJSvYbY9hbCwAAAAAWvzl04GdMFqTPaTlW21fd2CR1ABERXZbf5eurKTPRs84XMyeclz61mdXqGn/ddcuFVuP2auldkzwPD2I+bLl+2btICbCW2JfMwoA8/ZBQoayqf33Rs6lEHaXpuw3iA+m1/WEZIhbWErM0WG4jrkt9k5QQJYrO6JUJZO6b8F5S759ptNFG+eswRAwAAAAAi41cB16uw88mQovf8k0WAkgKhhpebdt2khWmrNb1t54dIqKO1tNsCXHq2gznqmMiIjKZc5rHXS/spz6ZpA3qHQlENF5X0d+YkNYpnw+PnDfV9EaVFScnEdHYcHnd8IhwnmabWR3zTIJz1vQWqecheRwue7nZlhMRkfXqNdKtUsZ0WrElPErsftC2MT++SngE2VDDq1ILA9asvlyYH1/lfCk8ryx32/aiwnThid7+n2M2V175re9AcUC7apFzjXv+Lo9UduO6GOoVT8OgpC2ZDVJHtwurCyiqrDobDyUGAAAAgMVHrgMv1+H3JJ0szJgUWPW/fHfdz285j0opP1ndqmXX2t7Cbyai1BcK11e1fWJ5ne3LlRmbf1S01FF4sLBpop2IesWrIJ07/lxq7q7pZQUxztXCRJQQlWob3Flh8zqP96xpkjlc7nI0y/JMcl50fdFvlJcSczzPE9HV8RlrKteaOKIH9yPIjff6fyDTrB7gBAAAAAAQOg9Ad30hdJSmF8lv6BVUXbu588/z70uNEoeMYW98IbUs8EX9WeMaKFzCo8SKx1b/yuWxwgOZvCr4pr5yz20CAAAAAAClyK2uXq/9XUP15jk91XU2DOdP6Fb9IsQX8TTUsO/0+vp2xeTDYhglVoQH4CMAAAAAAEhCXzdQVv3L2VX9oVmMGUZdu7myE7rq7h6FPJeHEUaJkRIrwgPwEQAAAAAAJKGvCwokpMTYcRoAAAAAAACWKKTEAAAAAAAAsEQhJQYAAAAAAIAlyrmW+MHmcDju37/vcDiIKCIiIiIiQqVy3wu4d+8ee4t9K9j/HMepVCpWk+O42V6R5/k5HAUPNsQhKAHiEJQAcQhKgDgEJUAcKsGSeAgT7+L14xeiiuPctwaEOjzPT09POxwOVsEr5rxuJXidGXEGvhCHoASIQ1ACxCEoAeIQlABxqARLIiVm2I+fxQ0R8TzvcDgcDocQiEI14TaMEJ0cx7GYU6lU7M4NggnmBnEISoA4BCVAHIISIA5BCRCH4bWEUmJyxQeLIYeL+C3xrRfxF+z/uU1OAPCCOAQlQByCEiAOQQkQh6AEiMMwWlopMYsw9rVw64XdUOFchPhjt17Ed2WEOzcA84E4BCVAHIISIA5BCRCHoASIwzBaiimxePqBSqVatmyZbww5RAvZOdcEffHdF+EMAkQhBAhxCEqAOAQlQByCEiAOQQkQh2G0JB7CxImQKIAiIiKWL1/O6gjxp1KpIl0iIiJYNWH/N3E8cZ7m387E4u5F8T/MzWKJQ3iwIQ5BCRCHoASIQ1ACxKESPLAPYRLiiYimp6fv3bsnvpUinoTg/wxsWgIiCeYGcQhKgDgEJUAcghIgDkEJEIdKsxCjxF+P9Az1/svNob8uwLX8EN8pEUJtxvoLuVRd+WOwym+h8ik/DmEpQByCEiAOQQkQh6AEiMPwWoi1xF8P9wz/9eNHU7cuj/rhoyuSVBELvYBZPBKu5OgZbc4OdxNmoPwWKtliiUN4sCEOQQkQh6AEiENQAsShEizQWuJl/N+X/f2v5s9P3/72lsMxHaKreE0C50Qz8oUSgeQh4aX8MVjlt1AJFnscwoMBcQhKgDgEJUAcghIgDpVsgVLiH0TcSYgYfuibS9c+//N3E7aFuaiY3O0WRd2GUf4YrPJbqHCLIg7hgYc4BCVAHIISIA4hbCz6LI5TvWGgsMehoZTL0lsW4krSF+fCeHmXYKbEgxc/+Ov/+pnvv5tXz0U8/KNH4jVJ0d9yf/tk2PRvE2ODQbyuf8IWbcKydY/w8goCQynnzfm2zzs+PzxDKcdxpYa5N9VzDNZ+uKY7sZj9Mx0eFVccryzurjSKCoxmnzpi9sM13VvP2ANrhdd1PY7FKPGczRCHAAsCcQhKgDgEJUAcLg0WfZa49y7up4u69jLdd7+df9GZhcOFAzxOKJlxWvSvVlG9efqft7rjsPfLJ/fZvvSOQ1HPvGHcVTheWexb6GI0J9YMWz2KRPWLzR1eH7P1iK7oBY3XGdy5hjg1EF3OaHYXSiQsEs3uaJCoX9DEm+up6tUwJ8XBXNb7je0vy+7aHnnkUa/yR2KiH3n0ycjo+B/9w827d/92y/Z/bkYu4zgu5vHUIF5dku8DvtwMpVzhESIiXb27sKCJ55s86/S5X5a08U0F0ley6LPY2ebBcww2+s2D2VvOmDZ9HnPxYHLIv1Oy17Uflm0hBMpfHAIsFMQhKAHiEJQAcbhkWK5QvZmvZPmeoZQrzFpr7qnUsC6+8x2LPkvLlcp08iU7/xZ9lraK6s18jziRNJQ6T2nRZ2lLDc7jLPp9ffUnmzTkEWuGf6oylnz8+SrH9DTP8/y/f7mq4RsiouQojwuNDm/9lY1eyhg9GC0qHa8sHhx4KWP0xWgi++Ga/sQGGi2PIyIymhM/nCQiWhklU586Grp3FpuPN2tzXU1pPaIrMos+yOjwVnYSpykzqS82s2RkvLJ4MJFotDyOdNrRZlEtoznxwzt+m01ERM+kOZsqoqncX1JVWGuolEuzFkAwR4nvLU9a9oPHH3s8+am0DK9/8fFPcNPfRy7/weM/5GId5tuDZ2xX//d3330XxKuT/OwC6b93BU08z5vrdfLns+j3HaGS/ZUa+SpOhlJt1bq2tpIAGyojCGOwo8NbRXdfKo3EflXeu0GmP/eL7gy57xX5HT32PhajxIGYXRwChAbiEJQAcQhKgDhcwgqaetwd+YJtJWS8YmFdfF39Sec7msqT9boj+wIeprToX60ylrT1eGUIhtYjtG6Nhog0a9bRkVaDs25LEbuQKA4t+v9+RFdfzRJAnudpw5PX/zmz86cPe17IfvgPNtMzaede9EgsrWdsH61U/95ZGP3mW+rMz2zO4VmddrQ5++JLXnn11ABFvahzniT3v6gz6c51YTjXe4x4vPJXtvS3015xHx+ndw/Oxf3spSgamfIcgiYi++F/naRn1G8myjbbr4LqWf0EQiCYo8RTMVv+4/pJ4r5KW7ViWWQEcRHON+7fobvf0N1v6Pubkd+PJTx857bty5tXIx2x2U8//bRKFcL1zLyLUDKLWTGG2ipjSVvPjPcrLPqswr56c0+BpXSOzXQKxhhs7O+bXVFrNCd+aNL+OvPNgxlU03/mJxmu0ByvLB6kt7NHdezr/srEbL30nYFon2NhLuYVhwBBgjgEJUAcghIgDpckQ2nhEV29uYDIO/XSrFnHcuWZh8GILGdbjLr6kwENaBpqq9bt573Pajn7L0Zd0UkNz/udqjA6ceZG1DtveY+pekuMSieb+W9Eif4qvPeH4S0Hk1OJrMZJ08qY37sqW6726YqqXS20H64ZHHgp45xuqlLmZFbbFFGMd6lx9L0bMccPxs2i2Z40LxTpqlrOWioDGIkMiWCmoxrNqh889dP/9128pe9T+o+/0O2bdPsruv0Vff8NOe4J1e5+f//e/em7d+9OTn5ttwe4wHUuxEtESLSteWB/9dj9o2qPeD9S6LvmgA0Qe98ompNZjcF+9KFoLr4wvSEx2j3FWhf7Ck2Z/+ZzpHHio5Xqnzlz4LiCZ+ijHp9FCMFoITDzi0OA4EAcghIgDkEJEIdLjnPZ7761Zp712DUvFOmMVbVCb95ytU/uWN/Ov+WKkajlVZ8FygXbSqjvqsV5upJtBWzOdHWBe9Wxs6blipHWrV7lE4ecc1G789J/mzIRnfmD1/RPStXFZN6w/U9hU6HRqYEZPn+cvjnjHbJtKu5OLO72XJJpOdtiZEPbRNTR0P9ekt/R3dHh+s8o8yexnis67Yf/dTLzpcRcv812+mxQekmzcFciTII5ShwXF3cvLf3m7b77N6doeopuD7vf44mm79DfR/5++/bIrW/Hlv1nPvHFFStiIyIi5M83LxzHORwOh8NBRMJfuoiIiED/3jmHiN2JrniVsaGUK+SojW/SuAaIg9LmWY0Sv/K2aGjXZ/q+Sajmc6B19A7dmNxULNr3+5mQtBBo/nEIEAyIQ1ACxCEoAeJwKdJU9vCVzsyY6s09lRpNZU/bFa6Qc+4DpNNJTpeU7PyzTn/RSdc6YvcC5YLq+n1aLVdFRCVtfIFFn9VSdLKH9FlVbD2zoZQrLN3GzqBbu4rnveNQRUTecfjiW9nn2IiuMP0zMfnc21OJH3Z/xGqsjMqc4fPbD9f0n/lJxujBaOsZ06Y/2zbVkDMrtpxtMZbsLyAisp4x7RxRXzzoZ3TXfvgPNtNK9UWvnNk5ROxRKNVsyi3PHi13VvBZ0qxZq6MrM3yQEArmKPFDDz30+OOP/zDhx5Nc6pfWa19aLgv/vhq94rCP2P8+MXrrm1Fuw/QThStSfhIXF7d8+fIgNsCLSqWKiIiIdJnN3zupIWKRgup6HfVdtZDlipGMVVrnrZ/CI+xe0lx3nQ7CGKzRnPgrW/rb2aPN2aPNab75sNNK9cVmVid7tDnbd5l7CFu49MwjDgGCBnEISoA4BCVAHC5VmsqT9Tpjy1k2FFnQJMyf508WEenW+p3xKXT+iYhIGFhlbzhPqqnscZ6wqYDNma7UkOWK0blW1z2MTBRoHD68SpgOrUt8Z+XUGaOdyLlm2PnvrRiiKO0T8k03jr53I6bqxWgiSn0xc/TXamGQ2XK2xViyjeU7VtsU3XCOJCcWD37EZqS6t7O2H67pf4/UPpv+eg4R+2+2iPeS5nAL8jreqKio6Md+fC92s/XbFdZvV1i/WWH9Nu7Lm3du2r68/e1Xo+P24btP3k346YqnNiUmqh999NHIyGAOU/tik2FmPR/GUFtlDGhbLfFvE8+3lRCVtPGyu1LPZP5jsB09k/RMmszCYKfUxIfphu+y+IBglHhu5hiHAEGFOAQlQByCEiAOlyjLFaNUsaG2yuj9GCJ5mrWi3FjupM4507InMV6xzBiHT0R5Jo1T5hsSZ+r4N5tpZcwWuYXEvhKj0l2NFGXElFsuGi1rTnuF6JW3hWEzuXzYI9+eVbN9yPxsFkrwt7ZasSI2JSNv2T/+U+SGX6v+0/9Y9o+1Eeq8u/emv/r6ztWvln+tLn8sbVNSUmJMTMzDDz888+kCJrc2ffbbCUoNEVv0We4niln0r87mNydg8x+DTVW7d4GznrF9JHrLZJtyfqWLfYUmdwp3fUaHK2d6ZLFwLEaJZxS8OASYO8QhKAHiEJQAcbikGUpFkzelHyVj0WcVureftuizXI8fluv8ayr3lxiF5+hKnlS0zzRp1uqMLWfNPO/eklqUVPuLw8Tkqmem3vvDsKhj75l8stnOn0W985bfx7U+EZUp6vmz8xTovDJiP8Yri/vfS0oblXgorNQQsVyzR4e3up+WzOZgizJ5y9W+mQbqQyr4g7TR0dFPPfVUUlKS3W7neZ7juJvfrrg1+P139Ait3/9kylp1ovpHP/rRQw89FPRL+xJ2UJC49SI8l5iMWq5KeOyYa2N1z5+JZs06YyFbHUDk9wHF8+A5But8ABLR1KbiyXd+nflmALd/Ul9Me+fzfrZOOPMl9SvEUtnoN99Sn/nVYOJng0Qxx5u1+maiYvaSiKLe+XWyv+t6HItR4rnwF4cACwVxCEqAOAQlQBwuFQXbSgqFFcMeHXh3HiDXrZfv/Bc08W2lnOstn8Mt+ldF+0xrKk/Wt2hXq1xLjMm9vXJFxSpicfjvFtdeuVObim3Cw3tzy7OPN3S7NgCKEVbedjR07/yMvAqJRM8lFp8nMflcc1Slu+fvPES0jtgv48RHRPSZcDiRa0sj65lB31XEss1OjEq/MejezMjzAcWWsy1GXdHJ8KXEXIhukvE8Pz09zU5+4/++Z/n8T/eS/ltC+nNq9RNsfDjoz16S/LvGGrBY/t4lFncrfGay8lsYdg9AHMIDAHEISoA4BCVAHIISeMehoZQrpI8dfywIXxwaSrnWbaEY45sDQylXSCEZcAxUqFJisWuXTg1e/cs/rHr+ySdTYmNjQ5EPAwAAAAAALAYWfZa2pcgclMe4zomhlNu3NozXFwn794JCsZbY1/LHf7Ii/b+uXJkcGxsbFRXFcZy/x1IvYcpfqav8FgZO2BUt3A2BJQ1xCEqAOAQlQByCEixUHGoqT9ZTlXbOz6mZt4ImXhH5sKGU01aRay132IQ2JWYhlZyc9OMfZ7D50qyEPREOf/W8jDZns5xTsf8v0lnT4m3BHS6IQ1hgiENQAsQhKAHiEJQgzHHIHtmkjInLYVTQxPMKSM5DuJaYiNgTqL3utbCXbNtxPAsOQgpxCEqAOAQlQByCEiAOQQkQh+AlJI8FZvdX2P/kGWriWdMIMggpxCEoAeIQlABxCEqAOAQlQByCryCnxF7TD4QbLeSz0xr7GtEGoYA4BCVAHIISIA5BCRCHoASIQ5AT5JRYPBGfxZYQUkJUiUt4PBEOQgBxCEqAOAQlQByCEiAOQQkQhyAnmCnx9PT09PQ0CzU2BV+lUrEvSHSjhc1SICL2bhAbAECIQ1AGxCEoAeIQlABxCEqAOAQ/grO9Fu+5URsRqVy8brqQaNk64gyCC3EISoA4BCVAHIISIA5BCRCHMCNnSnx1PNwNmYc1cUT4CAAAAAAAioS+LigQC0sK9XOJAQAAAAAAABQLKTEAAAAAAAAsUUiJAQAAAAAAYIlCSgwAAAAAAABLFFJiAAAAAAAAWKKQEgMAAAAAAMAShZQYAAAAAAAAliikxCBpvK6iu84U7lZIMplz6oZHwt0KAAAAAIAFYtW/HM+l7zYE/8wdpel5+qEgnaxrN5cen3XMGqTTLZTIcDcg3DpK02vXtn9amSK8LDriWUNX3d3zeip17ebKTsyiPHjG6yoG2ynm4CHtxkDeHRsur53aKV154dlP1fU32tyv83dl78kMX3MAAAAAAKRZjuVpay+7Xr3WNvBBgeuFYW984WmJcrGZ6nSUphcd2d7Cv5/rfil1oX2rvLMJy7GyKjpgHijXePeuN6R1Fse5XrC8wLeciIhM5pxPoo7vSU7ybFTXx0cytplT5A43mXOOTnoeEVVWnbkjQboZmz/g21dn5ZfpnxXSq8VgCafEQhSur3cX5jYN3GryrNPnfin3CyD7ixEMpol2IqLJiybaKJtMTh4/b9+4JTpUbZgf7daMBtY2kznnaDchKwYAAAAAxbFcp/r2WyyXM+yNL0wn1sk37I0vvObMSC3H8rTpu307/zPVsepf9hh4M+wt6qvu5l9PtRzL0+7tcObJQw37rh04+b7X6FpHbe3lksZPNURENDVE6uOHWGY7XlcxmEPUWRzHvrZuzejcEs3S5pxm8k5r1VE+H9lw/oSusFsje3imtvOQqLrJnHP0jt9mUEr5/u3vFv6xo9KZ+S8GKiLieT7czQiH3KaBW3z7AZ18Dcux2iP02v6gDvnO2qW+SdqQdnADtfeNy9XJ36qmc6OXvErHhssrTKfGXC9N5pwK8yUi56To88PlFd05Fd05FeZLZD9Vx772miw9XlfhW+4uLD9vd5WYTo2xcrN3M8Qytc4PItO2kfOmHNfJcyq6c5rHfUskm+dqCQAAAADA3BS87x7bLHjjgI6+uDpENNSw7/T6+t+Us4xU83pjfcaJfV5zg2eqY9ibXbW6pW27UNDReprWpaYSkSb1aTr9sYGIyKr/ZWuR6yQCy7HaIxkHqjc7X8btcY/0xhVtjaKxqRGikfO2drW6xjlCFr2jWK3ttTk725nazkPZx7f65sNEHa2n1xc9m+r3cDf7qU8maYN6R4JsM4Rv3enaoE3GDimWCKump6enp6fD3RhFYvdjQjf8G5Dxi72Uvy5u47oY6p2QzTYTkndumDw+m7SwvY9qDmV3HsooU0/WVAxScTb7VWk/6s5p249ObDqU3Xkou3NXTPtRlsGO11UM0q7szkPZnYfSUs/1u1LlqcZaVtn/hG37De9fLQ9JWzI7DzlPnk+Uvy7Ot8RVV64lAAAAAADzNXTNKP1G6prVZLzuf7msRx3LsbzCawfMM46adv22anW1z3xj69m2y7rC5zSSh4zcnJI+V0JUKk0NfTXDFYcsfRnbXpCY4Sx5uGm00RZz0Gs+tlQzUp4ryrjccmExrCjmOI6IVPfv30dKLMXrfgwREZ0oTI/n0uO59PjSrkDK58800U4xmzKJMmPzyV/SuzFPaqBYXv5z7L5O9MoEct3soaTMGC3dEbLW/F2u/DYzsUw9dcFkJ9NEu1pd5Jz2HLfJPXYdVVYdwOpl02ijTXSIexoAAAYGSURBVJzWyrrUPNi+IU08v9q7RLYlAAAAAADzY9X/7gSxdDHluaKMy1V/7BDeunrNp7qfOl27tbVPt/3Ja+w3d9t26rNaichi/YK2P19AVv3vvqh/I9dyLI+lFdxedjbrlX7neLKPseHjvaRdF5vEuvE2W4swRDQ2FUBCarnQalyt0VBAh9tPfTKp3Zoo0eEXNcMpkLsGShLpcDjC3QZF8piyT0S0+QN+4APn1127ubJ4arzVtFm+PCjYrOmNRERxmzYMtvdNjGyJTpKsmpC8c0P38fN2+fXG8xG9MoHMN6dG6A7ZJndWiPbL2jDzweZz/Tnn2JdRZdXZOxKI/I4Vk8lc0xtz8FCcn5KRsbm0BAAAAABgJpZjZVX96+vbWR6bWvmnlivpRZxz66z1ugzfI2TqDDVklX1R3/6p77TTgjcO7MvP5mqJ6LW2gVzLsbyWwsYeasiqZeuZO0rTi0q3sLRi/Vqprarsp5ptZrX6OJvtnJDcsGsq52i3c38sdZR2xk9pPdt2ueTnbOx6xsPZEPEe362LPJvhpFm1nq7P2ADFiCQilQqPYvLChojNcpnt5l/UZ5xosVppc2pA5XM1frGXiAZzegddJZOfjSWzEV1fG/PUx2tHL2VKrRMIIrXaZ6u6GYZn3dtrBWS87uhk/q7sjf5K5FoCAAAAADAflmN52lqqbxfvmSzegteqfzmbVvn29qXqDH1spMvG/Pgqd7Ui7vRrbQMfFKSU9wyUuwo7Smuf3j+QSl3XjBnbTqYQG0beZ7WSTD5iP1XX30ienWHxVlhjw+W1lPKYv8859ElL/2v73ef3dzgbIs7wGSKWasYiFBkZGYmU2JvPEHF4mCbaPbI++6m6/gsm+44EmfSSDRR/Goqm2G+MUf5zcUk0QeemRohCF/RsgnSnz5TpTs/R76SEh0PdEgAAAABYYqTyYU9dv63qX1//G78DYEKdFNF8UrYrNQkPYRJftLavurGJ5Fy+MkQkas/MieilT21mtbpGZiCNXfRCq3F7tfSuSd6HSw8R+2mG5fpl7yIFYntrcRynYsLdHkWRWkVs1b/sfoY1m0pR9GyqfHkwXOqbpIQoUYRFr0wgc9/EiPwhG/PU1DtpZi8SYp9lC4CJ2EDrbBtgHXMuXR45P9hocy9prhG2fR4brpvbVs9ybWMTpIt9pkz7ruMPVksAAAAAAIiIDHvjtbVPtw3I58NDDVllJ3TVjayC5Vgel57nvbWyZ52ZDTW82rbtJHvGTcpqXX/r2SESbUmdujbDueqYGa+r6G9MSOuUz4dHzptqeqPKiv2O3FrPtl0u2SK145fP4ZKriP02w3r1GukkBtKVKpLjOLbR1pIjPJeYjPnxVcKzhYcaXpUYIk5ds/pyoXvOg/AgYrny+RsbPt5L+bs8UsGN62Ko19/caUpI3rnBVtPLXkTvKFZfqGXreGMO7oppPzrLNvQN5pxj28fFHHRuJR235xBRhTCXO6qsOplIZqc7f6TbdqlvkohqKrqdtdTqsgTvkuPPsa8kWwIAAAAAMCcdraeJ6ERh+gl32fYW/v1c6trNlTkLS+S2DQqkjgSr/pfvrvv5LWfqkVJ+srpVy5KL7S38ZiJKfaFwfVXbJ5bX2cJm00Q7EfWKV1ZS/q7sPZl0qbnblQUIXXciEj2XmKZ2VthoQ1pncZz3rGmSPZyNjXkPEcs3g9iU7PVF/gfSlUDIgrnp6WmVSnV1MW/WuyaOiAgfAQAAAABAgdDXnZeO0vSiYO7gS0Rdu7nzz/tO4Q4KufnhirPGNfio4nmezaIGAAAAAAAAZcmtrl5/5HcNluCd0XD+RKgmNg817Du9vv4NxefDYiqHw4GUGAAAAAAAQJE0rzfW07va9N2GIJ2w4P1bPa+HICXu2s3lv0uBr6MOL2FsmLt7965Kpbr+dWS4mzR3D8BMjAfgIwAAAAAASEJfFxRImDgdyfO8w+EIa2MAAAAAAOCB5Uo38JgbUJB79+6xraYjMWsaAAAAAABCZ3p6mud5ouXhbgiAG7tTg5QYAAAAAABCa3p6OtxNAPDGEmGe5/8/RoDAu+JgVrUAAAAASUVORK5CYII=" alt="" />

　　我很好奇那个突然冒出来的黄色箭头是什么……所以就去切了一下这道水题……

　　

　　毫无压力地快速敲完……突然萌生了一种想法：试试自底向上线段树！

　　重新看了下zkw大牛的《统计的力量》，发现确实好写，而且灰常好用！

写的时候出现的问题：读入应该是读到[n+1,n+n]这一段，而我读到了[n+i-1,n+n-1]……（也就是说：1~n格是树中节点，后n个格是叶子节点）

 int t[N<<],a[N];
 #define L (o<<1)
 #define R (o<<1|1)
 #define mid (l+r>>1)
 void maintain(int o,int l,int r){
     if (l<r) t[o]=max(t[L],t[R]);
 }
 void build(int o,int l,int r){
     if (l==r) t[o]=a[l];
     else{
         build(L,l,mid);
         build(R,mid+,r);
         maintain(o,l,r);
     }
 }
 void update(int o,int l,int r,int pos,int v){
     if (l==r) t[o]=v;
     else{
         if (pos<=mid) update(L,l,mid,pos,v);
         else update(R,mid+,r,pos,v);
         maintain(o,l,r);
     }
 }
 int ql,qr,ans;
 void query(int o,int l,int r){
     if (ql<=l && qr>=r)    ans=max(ans,t[o]);
     else{
         if (ql<=mid) query(L,l,mid);
         if (qr>mid) query(R,mid+,r);
     }
 }

普通线段树

 int t[N<<],n,m;
 void update(int p,int v){
     for(t[p+=n]=v,p>>=;p;p>>=)
         t[p]=max(t[p+p],t[p+p^]);
 }
 int ans;
 void query(int l,int r){
     for(l=l+n-,r=r+n+;l^r^;l>>=,r>>=){
         if (!(l&)) ans=max(t[l^],ans);
         if ( r&) ans=max(t[r^],ans);
     }
 }

zkw线段树

完整代码：（确实快了好多！而且代码短了好多……）

 //HDOJ 1754
 #include<cmath>
 #include<vector>
 #include<cstdio>
 #include<cstring>
 #include<cstdlib>
 #include<iostream>
 #include<algorithm>
 #define rep(i,n) for(int i=0;i<n;++i)
 #define F(i,j,n) for(int i=j;i<=n;++i)
 #define D(i,j,n) for(int i=j;i>=n;--i)
 #define pb push_back
 #define CC(a,b) memset(a,b,sizeof(a))
 using namespace std;
 int getint(){
     int v=,sign=; char ch=getchar();
     while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
     while(isdigit(ch))  {v=v*+ch-''; ch=getchar();}
     return v*sign;
 }
 const int N=,INF=~0u>>;
 const double eps=1e-;
 /*******************template********************/

 int t[N<<],a[N],cnt;
 #define L (o<<1)
 #define R (o<<1|1)
 #define mid (l+r>>1)
 void maintain(int o,int l,int r){
     if (l<r) t[o]=max(t[L],t[R]);
 }

 void build(int o,int l,int r){
     if (l==r) t[o]=a[l];
     else{
         build(L,l,mid);
         build(R,mid+,r);
         maintain(o,l,r);
     }
 }
 void update(int o,int l,int r,int pos,int v){
     if (l==r) t[o]=v;
     else{
         if (pos<=mid) update(L,l,mid,pos,v);
         else update(R,mid+,r,pos,v);
         maintain(o,l,r);
     }
 }
 int ql,qr,ans;
 void query(int o,int l,int r){
     if (ql<=l && qr>=r)    ans=max(ans,t[o]);
     else{
         if (ql<=mid) query(L,l,mid);
         if (qr>mid) query(R,mid+,r);
     }
 }
 int main(){
 #ifndef ONLINE_JUDGE
     freopen("input.txt","r",stdin);
 //    freopen("output.txt","w",stdout);
 #endif
     int n,m;
     while(scanf("%d%d",&n,&m)!=EOF){
         F(i,,n) a[i]=getint();
         build(,,n);
         char s[];
         F(i,,m){
             scanf("%s",s); ql=getint(); qr=getint();
             if (s[]=='Q') {ans=; query(,,n); printf("%d\n",ans);}
             if (s[]=='U') update(,,n,ql,qr);
         }
     }
     return ;
 }

普通线段树（436MS 3996K）

 //HDOJ 1754
 #include<cmath>
 #include<vector>
 #include<cstdio>
 #include<cstring>
 #include<cstdlib>
 #include<iostream>
 #include<algorithm>
 #define rep(i,n) for(int i=0;i<n;++i)
 #define F(i,j,n) for(int i=j;i<=n;++i)
 #define D(i,j,n) for(int i=j;i>=n;--i)
 #define pb push_back
 #define CC(a,b) memset(a,b,sizeof(a))
 using namespace std;
 int getint(){
     int v=,sign=; char ch=getchar();
     while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
     while(isdigit(ch))  {v=v*+ch-''; ch=getchar();}
     return v*sign;
 }
 const int N=,INF=~0u>>;
 const double eps=1e-;
 /*******************template********************/

 int t[N<<],n,m;
 void update(int p,int v){
     for(t[p+=n]=v,p>>=;p;p>>=)
         t[p]=max(t[p+p],t[p+p^]);
 }
 int ans;
 void query(int l,int r){
     for(l=l+n-,r=r+n+;l^r^;l>>=,r>>=){
         if (!(l&)) ans=max(t[l^],ans);
         if ( r&) ans=max(t[r^],ans);
     }
 }
 int main(){
 #ifndef ONLINE_JUDGE
     freopen("input.txt","r",stdin);
 //    freopen("output.txt","w",stdout);
 #endif
     while(scanf("%d%d",&n,&m)!=EOF){
         CC(t,);
         F(i,,n) t[i+n]=getint();
         D(i,n-,) t[i]=max(t[*i],t[*i+]);//这句就是build建树……
         char s[];
         int x,y;
         F(i,,m){
             scanf("%s",s); x=getint(); y=getint();
             if (s[]=='Q') {ans=; query(x,y); printf("%d\n",ans);}
             if (s[]=='U') update(x,y);
         }
     }
     return ;
 }

zkw线段树（218MS 4296K）