P4145——線段樹點修改&&模闆題

連結

題意：對一個數列進行以下兩種操作：

給$[l,r]$中的每個數開平方(下取整)

詢問$[l,r]$中各個數的和

顯然，區間開平方不滿足區間可加性，是以對區間中每個數開平方不能通過标記完成，隻能使用暴力的單點修改。因為1e12的數開方6次就變成了1，是以需要修改的次數實際上很少。同時維護一個區間最大值maxv，如果maxv大于1才需要進行開平方操作。

看讨論區還有分塊、樹狀數組+并查集等做法，orz.

個性簽名：時間會解決一切