Codeforces 400E Inna and Binary Logic 口胡题解 发表于 2020-02-10 | 更新于 2019-12-01 | 阅读次数: 17 本文字数: 17 字 | 阅读时长 ≈ 1 分钟 题意简述给定一个序列aa,其长度为nn,(ai<=1e5,n<=1e5)(ai<=1e5,n<=1e5)。然后有这样一个生成矩阵SS,SS的第ii行有n−i+1n−i+1个元素。第一行的元素就是aa,对于后面几行,满足:S[i][j]=S[i−1][j] and S[i−1][j+1]S[i][j]=S[i−1][j] and S[i−1][j+1],其中andand表示位运算&,即按位取且。 支持两种操作: 修改aa某一个位置的值 求矩阵SS中所有元素和 思路按位拆开,对于每一位,我们发现:如果有一段连续的11,长度为LL,那么推下去就会形成一个三角形,其中有L(L+1)/2L(L+1)/2个元素,而且只影响局部(记得乘上位权)。然后对于修改,只要维护一下左/右连续的1,更新一下答案即珂。 但是我写挂了,一直挂着。。。。。。。。。。。。。所以不贴代码,大家参考别的博客吧。