抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

可持久化trie是一种和最大异或和关系非常紧密的算法。 例题1 给你一个数列ai\\{a_i\\}ai​,每次询问给你l,r,xl,r,xl,r,x,要你计算max⁡{a[i]⊕x}(i∈[l,r])\max\{ a[i]\oplus x\}(i \in [l,r])max{a[i]⊕x}(i∈[l,r]) 如何考虑? 从高位往低位贪心! 举个例子: a[i]:100,110,101,01...

传送门 先考虑一下暴力怎么打,对于每个时间,我们开一个vectorvectorvector,对于每一个任务,我们在[Si,Ei][S_i,E_i][Si​,Ei​]的vectorvectorvector里面都pushbackpushbackpushback一遍PiP_iPi​即可。 但是这样的暴力是愚蠢的暴力,考虑优化,我们在SiS_iSi​和Ei+1E_i+1Ei​+1的位置分别打上加入和...

传送门 一开始看到这道题,非常懵逼,不知道怎么做。 然后发现子弹是按照顺序发射的,于是转化一下题目条件,木板[Li,Ri][L_i,R_i][Li​,Ri​]会在接触到第SiS_iSi​个子弹时破掉,于是就转换成求[Li,Ri][L_i,R_i][Li​,Ri​]第SiS_iSi​大的子弹编号是多少。 这就是主席树模板嘛! p.s.如果你懒(像我一样),不想把操作离线下来搞,就可以搞一下线段...

传送门 一眼看上去:这不就是最短路的模板吗? 两眼:边权太大了,怎么开的下? 考虑还是用Dijkstra\rm DijkstraDijkstra解决,每个点开一棵线段树,存储二进制的状态 我们要实现的功能: 1.给二进制数加上2k2^k2k,这可以看成把kkk位后所有连续的111变成0,再把所有连续111后的那一个000变成111 2.比较两个二进制数的大小,先比较高位,再比较低位。 但是用...

传送门 用可持久化线段树实现,rt[i]rt[i]rt[i]表示每个副本线段树的根节点。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <bits/std...

题目 传送门 一个长度为nnn的序列aaa,设其排过序之后为bbb,其中位数定义为b[n/2]b[n/2]b[n/2],其中a,ba,ba,b从000开始标号,除法取下整。 给你一个长度为nnn的序列sss。 回答QQQ个这样的询问:sss的左端点在[a,b][a,b][a,b]之间,右端点在[c,d][c,d][c,d]之间的子序列中,最大的中位数。 其中a<b<c<d...