http://acm.hznu.edu.cn/OJ/problem.php?cid=1263&pid=2

http://acm.hznu.edu.cn/OJ/problem.php?id=2581

題意：區(qū)間求and，區(qū)間求or，區(qū)間求xor，求區(qū)間第k小。

題解：

? 如果只有詢問，可以維護(hù)一棵可持久化01樹，從根到某個(gè)節(jié)點(diǎn)的路徑表示此節(jié)點(diǎn)的二進(jìn)制，每個(gè)節(jié)點(diǎn)記錄此節(jié)點(diǎn)的數(shù)字的個(gè)數(shù)。

? 如果加上xor x操作，那么詢問的時(shí)候如果x的數(shù)字這位為1，則走相反的路。

? 如果加上and x操作，會使得所有數(shù)在x二進(jìn)制位0的位全部變?yōu)?/span>0，而加上or x操作，會使得所有x二進(jìn)制為1的位全部變?yōu)?/span>1。所以對于每一位，當(dāng)這樣的合并請求發(fā)生的時(shí)候并且之前沒進(jìn)行過的時(shí)候，直接暴力重構(gòu)數(shù)據(jù)結(jié)構(gòu)即可，這樣總共有log次重構(gòu)。

? 總復(fù)雜度是(nlog2x+mlogx)。

?

總結(jié)

以上是生活随笔為你收集整理的Little Sub and Sequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。