题解 P5592 【美德的讲坛】

[同时发表在博客里哦](https://foreverlasting1202.github.io/2019/10/14/%E7%BE%8E%E5%BE%B7%E7%9A%84%E8%AE%B2%E5%9D%9B/) 一道用$Trie$和$STL$瞎搞的题。 <!--more--> 先$orz\ hy$大佬。 还是太菜了，考场上这题都不会。。。而且当时想的做法也假了。退役稳了。 这道题，首先要考虑到分组这回事。 找到一个$2^{\omega}$，使得$2^{\omega}\leq x<2^{\omega+1}$，于是我们可以按$\frac{x}{2^{\omega}}$分组。明显的是，同组之内的异或和都会小于$x$，那么不同组呢？ 观察可发现，只有$\frac{a}{2^{\omega}}\ xor\ \frac{b}{2^{\omega}}==1$的两组之间才有可能异或起来小于$x$。证明嘛，挺显然的，注意到$x$不是$2$的幂次就容易观察出来了。 有了这个性质，我们只要想办法算相邻的两组就好了。算的过程也不复杂，你用$01Trie$树维护一下子树大小，然后在两棵$Trie$上同时$dfs$，讨论当前这一位$x$的值，便可以得到答案。至于这个讨论怎么来的，你可以像官方题解说的考虑二分图匹配过程，也可以考虑一下贪心，这里的讨论大概是这样的： ```cpp int solve(res a,res b,res dep){ if(!a||!b)return 0; if(dep==-1)return 0; res a0=son[a][0],a1=son[a][1],b0=son[b][0],b1=son[b][1]; if((x>>dep)&1)return solve(a0,b1,dep-1)+solve(a1,b0,dep-1); if((sum[a0]<sum[b1])==(sum[a1]<sum[b0]))return min(sum[a],sum[b]); if(sum[a0]<sum[b1])return min(solve(a1,b1,dep-1),min(sum[b1]-sum[a0],sum[a1]-sum[b0]))+sum[a0]+sum[b0]; return min(solve(a0,b0,dep-1),min(sum[a0]-sum[b1],sum[b0]-sum[a1]))+sum[a1]+sum[b1]; } ``` 接下来就是修改。 我并没有看懂官方题解说的 _类似记忆华的过程_。 我的想法是利用$multiset$强行维护$\frac{a}{w^\omega}$的位置和值，然后每次大力讨论这次修改与原来值的关系，再用个$multiset$维护一下每个位置和它相邻位置的答案$ans[i]$，每次暴力删除再加入。至于$Trie$树，本来就是可以删除的。修改$ans[i]$每次再调用一遍相邻两个的$solve$，重新算一遍就好了。复杂度还是$O(nlog^2a_i)$（假设$n,q$同阶）。跑起来挺快的，写起来就有点长了，去掉调试还有$6.5KB$。 还要注意一下特判$x=0$的情况，这有点坑。