http://codeforces.com/problemset/problem/400/E
Inna is fed up with jokes about female logic. So she started using binary logic instead.
Inna has an array of n elements a1[1], a1[2], ..., a1[n]. Girl likes to train in her binary logic, so she does an exercise consisting of nstages: on the first stage Inna writes out all numbers from array a1, on the i-th (i ≥ 2) stage girl writes all elements of array ai, which consists of n - i + 1 integers; the k-th integer of array ai is defined as follows: ai[k] = ai - 1[k] AND ai - 1[k + 1]. Here AND is bit-wise binary logical operation.
Dima decided to check Inna's skill. He asks Inna to change array, perform the exercise and say the sum of all 
Help Inna to answer the questions!
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 105) — size of array a1 and number of Dima's questions. Next line contains nintegers a1[1], a1[2], ..., a1[n] (0 ≤ ai ≤ 105) — initial array elements.
Each of next m lines contains two integers — Dima's question description. Each question consists of two integers pi, vi(1 ≤ pi ≤ n; 0 ≤ vi ≤ 105). For this question Inna should make a1[pi] equals vi, and then perform the exercise. Please, note that changes are saved from question to question.
Output
For each question print Inna's answer on a single line.
题意：a[]数组n个数，第1行n个数，第二行n-1个数分别是第1行每两个相邻的数AND之后的值，第3~n行依次是上一行每两个相邻的数AND之后的值。求这n行所有的数的总和。带修改。
思路：
如果直接暴力AND，连不修改时的总和都无法在时间内求出。
拆开来一位一位的看，对于第i位，假如有8个数分别是11101101，因为每次合并都是两个相邻的，x&0=0，0是分界线，11101101可以分开看作111，11，1三组每组内部两两合并，每组的sum就是一个等差数列求和了。我们要找的就是所有的连续1。
初始sum就是上面所述，那么怎么修改呢？
假如我们修改了p位置，还是一位一位的看，p位置的第i位如果不变，就没影响，如果0->1或1->0，那么影响到的就是（只看第i位）p位置左右连续1的情况，假如原来p是0，p-1及其左边连续L个1，p+1及其右边连续R个1，现在p变成1的话，sum增加(L+R+1)(L+R)/2-(L+1)L/2-(R+1)R/2=(L+1)(R+1)，如果是p由1变0，那么sum减少刚刚那个式子。
我们需要维护L[],R[]，表示每个位置向左/右有多少个连续的1，每次的操作就是单点查询+区间修改。
我用了树状数组，多了一层差分的操作，使得很绕，写了一堆bug，最后面向数据找bug，A掉了，没有数据的话调bug的难度非常大。以后除非是很简单的单点查询+区间修改可以用BIT，别的复杂一点的还是老老实实用segment tree吧，那一层差分实在是绕。
#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+1000
#define ll long long
#define lowbit(x) (x&-x)
int n,m,a[maxn],l[18][maxn],r[18][maxn];
ll ans;
int c1[18][maxn],c2[18][maxn],d1[18][maxn],d2[18][maxn];
void add1(int i,int x,int d)
{
if(x<=0||x>n)return;
while(x<=n)
{
c1[i][x]+=d;
x+=lowbit(x);
}
}
int sum1(int i,int x)
{
if(x<=0||x>n)return 0;
int ret=0;
while(x>0)
{
ret+=c1[i][x];
x-=lowbit(x);
}
return ret;
}
void add2(int i,int x,int d)
{
if(x<=0||x>n)return;
while(x<=n)
{
c2[i][x]+=d;
x+=lowbit(x);
}
}
int sum2(int i,int x)
{
if(x<=0||x>n)return 0;
int ret=0;
while(x>0)
{
ret+=c2[i][x];
x-=lowbit(x);
}
return ret;
}
void init()
{
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<18;i++)
{
int t=(1<<i);
for(int j=1;j<=n;j++)
{
if(a[j]&t)l[i][j]=l[i][j-1]+1;
else l[i][j]=0,ans+=(ll)(1+l[i][j-1])*l[i][j-1]/2*t;
d1[i][j]=l[i][j]-l[i][j-1];
}
ans+=(ll)(l[i][n]+1)*l[i][n]/2*t;
for(int j=n;j>=1;j--)
{
if(a[j]&t)r[i][j]=r[i][j+1]+1;
else r[i][j]=0;
}
for(int j=1;j<=n;j++)d2[i][j]=r[i][j]-r[i][j-1];
}
}
void BIT_init()
{
for(int i=0;i<18;i++)
{
for(int j=1;j<=n;j++)
{
add1(i,j,d1[i][j]);
add2(i,j,d2[i][j]);
}
}
}
void solve()
{
int p,v;
while(m--)
{
scanf("%d%d",&p,&v);
for(int i=0;i<18;i++)
{
int t=(1<<i);
if((a[p]&t)==(v&t))continue;
if(v&t)
{
int sum1p1=sum1(i,p-1),sum2p2=sum2(i,p+1);
ans+=(ll)(sum1p1+1)*(sum2p2+1)*t;
add1(i,p,1+sum1p1);add1(i,p+1+sum2p2,-1-sum1p1);
add2(i,p-sum1p1,1+sum2p2);add2(i,p+1,-1-sum2p2);
}
else
{
int sum1p=sum1(i,p),sum2p=sum2(i,p);
ans-=(ll)(sum1(i,p-1)+1)*(sum2(i,p+1)+1)*t;
add1(i,p,-sum1p);add1(i,p+sum2p,sum1p);
add2(i,p-sum1p+1,-sum2p);add2(i,p+1,sum2p);
}
}
a[p]=v;
cout<<ans<<"\n";
}
}
void debug()
{
}
int main()
{
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
init();
BIT_init();
//debug();
solve();
return 0;
}
京公网安备 11010502036488号