网站上360 旋转的图是怎么做的/怎么做网站关键词优化

偏序问题：

一维直接sort；

二维的话可以用树状数组：登录—专业IT笔试面试备考平台_牛客网

离散化，先按照第一维从小到大排序，再倒着枚举树状数组，如果发现当前数不是最大的，即query(a[i].y)+i!=n，那么当前的贡献值就为1；

三维的话，可以用树状数组+cdq分治：【模板】三维偏序（陌上花开） - 洛谷

cdq分治大体上就是先向下二分，向上合并第二维处理，分段排序。sort处理一维，cdq分治处理一维，树状数组处理一维。分段排序，保证了两个区间都是单调不递减的，如果后面区间的第二维大于第一维，就把第一维的当前数的个数加到树状数组中，此时第一、二维都已有序，所以最后只要ans+=query(s[i].c)，此时第三维也有序，依次求出贡献再相加即可。

trie树：

将每个字符串的每一位作为一个节点放到一棵树上，主要思想是利用字符串的公共前缀节约存储空间。可以进行插入和查找。

01字典树：可以处理单点异或最大值问题。主要利用了贪心的思想，在查询的时候，优先寻找与当前位相反的数，因为只有这样才能产生贡献。

可持久化字典树：最大异或和 - 洛谷

可持久化字典树解决的问题是一个区间异或最大值得问题。

这个题首先将所求的结果，转化为s[i-1]^s[n]^x的形式，由于对于每一个x来说，s[n]^x都是定值，所以求s[i-1]和它们异或的最大值。可持久化字典树的思想是，对于当前版本遍历，可以遍历到先前和当前的版本。再插入操作的时候，一边向下建立自己当前版本所想要建立的数，一边引申到上一版本中，和上一版本建立联系。查询的时候，从高位到低位遍历，贪心的选择与当前位相反的数，如果没有的话，就只能在当前遍历到的版本，向下遍历，没有贡献。

无论是上个星期看的莫队还是这个星期看的cdq分治和trie树，始终都是把一个比较大的字符串也好，一个比较大的数据也好，我感觉做的事情都是维护它们的贡献，然后将这些贡献加起来以得到答案。