连续做的又一道预处理+贪心的题目，一开始因为复杂度的原因一直没有下手，看了官方题解才意识到复杂度是nlogn，因为调和级数求和是logn。。。
贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点，如果这个点等于原来的出发点就直接return -1，因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点（也有可能是他自己），当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理，其次是复杂度的分析没有到位。
错误的点的话是对题意的理解：这里要求覆盖整条线段，而不仅仅是覆盖整点，但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了，原来的算法在这里会失效，因为那个总是多考虑一步，而没有考虑出发点是不是合法的。
首先确定，什么时候是NO，因为把ai全部异或起来一定是整个矩阵全异或，bi同理所以这俩数字应该相等，xor为0，如果不为0一定是不存在的。所以，如果存在，那么a全部xor和b全部xor一定是相等的，记为tmp
否则的话，把b1到bm-1全放到第一行的左边m-1个空位，剩下的右边那个补上一个t使得这一行xor为a1，此时最右边一列的xor为tmp^a1^t=tmp^(b1^bi..^bm-1)==bm，所以这样构造的矩阵一定满足要求！！！
继续阅读“[XOR][思维][构造] codeforces 1016D Vasya And The Matrix”
还是找星星，但是数据量升高了，不能用n^3复杂度的算法了
这里可以用六个预处理的矩阵来表示信息，前四个分别为上下左右到当前位置的连续的星个数，这样就不用每次到一个坐标都从新求了。后两个分别为两个标记矩阵，这里的思想很像之前有个AC自动机替换禁忌词的题目，因为那个题目禁忌词可能互相冲突，互相交错，互相包含，而这个里面的不同的星星也会出现这种情况，所以采用了类似的方法：在左端点标记+1，右端点标记-1，然后再把矩阵从左往右过一遍，h[i][j]=h[i][j]+h[i][j-1]，这样的话，就可以确定出来一个点有没有被星星覆盖到：如果他的h或v大于0就被覆盖了，否则就没有。所有的矩阵预处理都是n^2的复杂度，总共6*n^2大概。
继续阅读“[思维][预处理][区间信息技巧] codeforces 1015E2 Stars Drawing (Hard Edition)”
