Android之Init进程
A：
操作2的L范围在1~10W之间，也就是说当序列长度达到10W之后，接下来的操作就只需要存标记就好。
B：
对于操作2，将他之前的操作1都枚举一遍，如果与当前询问的子树有交，则将该x[i]加入set中。关于如何判断有交，操作2的level小于操作1的level并且对应到最底层的两个区间有交集即可。时间复杂度O(n^2lgn)。
C：
记cnt为区间[L,R]的最大匹配长度，cl为未匹配的‘）’数量，cr为未匹配的‘（’数量，则区间的最值可以通过合并两个子区间得到：[L,R].cnt = [L,r].cnt + [l,R].cnt + min([L,r].cr,[l,R].cl)*2。既然可以合并，那么用线段树来解决就可以了。
D：
如果一个人的左右都比他先入座，那么这个人就不能入座，因此合法的方案应该是任何时刻已入座的人的位置是连续的一段区间，并且最后入座的人坐在区间的最左边或最右边。
然后我就这样做了：将已确定位置的人按照时间顺序排序，设前一个人为x，新进来的人为y，（x和y都已确定位置），在x进来之后到y进来之前入座的人的数量cnt，则合法的方案必须能够用这cnt个人把原来以x为端点的线段与y点连接成一条新的线段，并且新的线段要以y为端点。假设目前以x为端点的线段与y点之间有a个空位置要填，则可行方案数为C(cnt,a)，这个意思是从x到y的时间段内选出a个时间点来安排xy之间空位置的入场。
新学的一个求逆元的方法：
inv[i] = ( MOD - MOD / i ) * inv[MOD%i] % MOD
证明：
设t = MOD / i , k = MOD % i
则有 t * i + k == 0 % MOD
有 -t * i == k % MOD
两边同时除以ik得到
-t * inv[k] == inv[i] % MOD
即
inv[i] == -MOD / i * inv[MOD%i]
即
inv[i] == ( MOD - MOD / i) * inv[MOD%i]
证毕
适用于MOD是质数的情况，能够O(n)时间求出1~n对模MOD的逆
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
