「CF400E」Inna and Binary Logic-简单数据结构

Inna 有一个一个长度为 $n$ 的数列 $a_1 [1],a_1 [2],\dots,a_1 [n]$。

她会进行如下操作,分为 $n$ 个阶段:
在第一阶段,Inna 从数组 $a_1$中写出所有数字,在第 $i$ 个 $(i \ge 2)$ 阶段 Inna 会写出数组的所有元素 $a_i$ ,由 $n - i + 1$ 个整数组成; 数组 $a_i$ 的第 $k$ 个数定义如下:$a_{i} [k] = a_{i-1} [k] \mathrm{AND} a_{i-1} [k + 1]$ 。 这里 $\mathrm{AND}$ 是二进制的逐位与运算。

Dima 决定检验 Inna 的技能。 他要求 Inna 改变阵列,进行练习并说出她在当前练习中写出的所有元素的总和,即:

$$
\sum_{i=1}^n \sum_{j=1}^{n-i+1} a_i[j]
$$

请帮助Inna回答问题!

链接

Codeforces

题解

每位贡献独立,方便合并,一看就要分位考虑嘛。

我们分位考虑后,就只剩下只包含0/1,每次把一个位置 0->1 或者 1->0 ,然后重新计算这一位的贡献。

事实上,我们在一位的情况下,我们只要计算出多少长度在 $[1,n]$ 的区间包含至少 $1$ 个 $0$。

我们考虑用唯一性确定这个事情(用最先出现的 $0$ 计算贡献),就是左端点从上一个 $0$ 到这个 $0$ 的区间,右端点在这个 $0$ 以右的区间。

set 维护每个0出现的位置,每次修改计算下贡献就好了。

时间复杂度是 $O(n \log n \log V)$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 210000,logn = 21;

int n,m,ANS = 0;
int num[MAXN];
set<int> S[logn];// 维护0出现的位置

int getpre(int pos,int x){// 小于 pos 的第一个 x
auto it = S[x].lower_bound(pos);
return *(--it);
}
int getnex(int pos,int x){// 大于 pos 的第一个 x
auto it = S[x].upper_bound(pos);
return *it;
}
int calc(int now,int last,int x){
return (now-last) * (n-now+1) * (1LL<<x);
}

void update(int p,int v){
for(int i = 0;i<logn;i++){
int tmp = (v&(1<<i))!=0;
if(tmp != (int)(S[i].count(p))) continue;
int last = getpre(p,i),nex = getnex(p,i);
if(!tmp){
ANS += calc(nex,last,i);
ANS -= calc(nex,p,i);ANS -= calc(p,last,i);
S[i].insert(p);
}
else{
ANS -= calc(nex,last,i);
ANS += calc(nex,p,i);ANS += calc(p,last,i);
S[i].erase(p);
}
}
}

void init(){
scanf("%lld %lld",&n,&m);
for(int x = 0;x<logn;x++)
for(int i = 1;i<=n;i++) S[x].insert(i);
for(int i = 0;i<logn;i++) S[i].insert(0),S[i].insert(n+1);
for(int i = 1;i<=n;i++){
scanf("%lld",&num[i]);
update(i,num[i]);
}
}

void solve(){
int v,p;
for(int i = 1;i<=m;i++){
scanf("%lld %lld",&p,&v);
update(p,v);
printf("%lld\n",ANS);
}
}

signed main(){
init();
solve();
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×