Codeforces 400E Inna and Binary Logic 口胡题解

发表于 2020-02-10 | 更新于 2019-12-01 | 阅读次数：

本文字数： 17 字 | 阅读时长 ≈ 1 分钟

题意简述

给定一个序列 $a$ ，其长度为 $n$ , $(a_i<=1e5,n<=1e5)$ 。然后有这样一个生成矩阵 $S$ ， $S$ 的第 $i$ 行有 $n-i+1$ 个元素。第一行的元素就是 $a$ ，对于后面几行，满足： $S[i][j]=S[i-1][j]\ and \ S[i-1][j+1]$ ，其中 $and$ 表示位运算&，即按位取且。

支持两种操作：

修改 $a$ 某一个位置的值
求矩阵 $S$ 中所有元素和

思路

按位拆开，对于每一位，我们发现：如果有一段连续的 $1$ ，长度为 $L$ ，那么推下去就会形成一个三角形，其中有 $L(L+1)/2$ 个元素，而且只影响局部（记得乘上位权）。然后对于修改，只要维护一下左/右连续的1，更新一下答案即珂。

但是我写挂了，一直挂着。。。。。。。。。。。。。所以不贴代码，大家参考别的博客吧。