P4246
首先注意到两个点应该怎么联通，有可能直接走进去对吧，也有可能是绕一圈走过去，我们考虑整个在求连通性的时候最重要的是哪些点，是左上角，左下角，右上角和右下角，所以我们考虑维护他们之间的连通性。
然后连通性很好合并，所以我我们可以把这个东西搬上线段树维护一大段区间的四个角互相是否可达。
然后绕路的怎么办呢，对于前缀问能不能到达相邻点，再做往后的处理，先考虑绕左边再考虑绕到另一边去，两边连通性都出来了再考虑比较重要的两个点（起点和终点各自的相邻点）是否再能可达。
然后因为可达性的维护很容易，所以这个题实际上也是函数码出来了就基本上写完了。
CF757G
大码量狗屎
首先考虑不强制在线，不作修改应该怎么操作。
实际上这个题就是LCA那个题，可以直接离线掉做。
然后现在强制在线，怎么办呢，套主席树。
然后现在还要相邻的数交换，怎么办呢，考虑交换只会影响到这两个点，后面的取前缀和不关心顺序不变，前面的也不变，所以之际诶交换暴力重构主席树就行了。
不优美，时间复杂度是nlog2n的。
CF543E
考虑不强制在线怎么做，询问以权值排序，然后考虑排个序把点线段树上加进去就行了，像个弱智。
然后强制在线，套个主席树。
然后你看到这个畜生一样的空限。
你考虑优化，首先来个标记永久化，还不够，三个这么大的数组开不下。
然后这个题是怎么解决的呢。。。
你考虑lson和rson的数据范围大概是1<<23级别的，tag的数据范围大概是2e5级别的，我们认为他是1<<18级别的，然后我们发现这三个数可以拼成一个ULL，然后做法就是每个主席树节点有一个ULL，然后空间分成三份交给tag和lson和rson。
然后就卡过去了。
据说这题出题人非常想卡主席树但是还是没卡成，我决定还是。。。
写官方解法，不想拆位吃屎。
P4198
容易发现这玩意就是要求你斜率递增的情况下能取就取拿出来的长度。
首先考虑把所有楼房的斜率存下来，然后考虑合并区间实际上就是在一个区间里面二分出最近的不被拿下的斜率，然后从这个开始往后嗯找找到的最长的长度，如果对于每个都维护一个这个的话应该做一次合并是O(len)的。
的不需要每个都处理好，可以在pushup的时候直接调用query实现问询答案。
标签：连通性,在线,树状,线段,然后,数组,考虑,强制 From： https://www.cnblogs.com/kisara-no-inu/p/17636375.html