P9883 [EC Final 2021] Fenwick Tree 题解
本题首篇题解捏。
解法
显然，我们不可能在同一个位置上进行两次及以上的 update(pos,val) 操作，因为两次 update(pos,val1) 和 update(pos,val2) 操作等价于 update(pos,val1+val2) 操作，然后后者所用操作次数比前者少，所以更优。除此之外，显然我们不可能进行 update(pos,0) 操作，因为这对树状数组各位置的值没有影响。
我们设 $f_i$ 表示在所有 $j + j \& (-j) = i$ 有几个位置的目标状态是非 $0$。显然我们需要从 $f_1$ 计算到 $f_n$，因为位置 $i$ 是否进行 update() 影响到位置 $i + i \& (-i)$。现在分几种情况讨论。
- 位置 $i$ 的目标状态是 $0$，且 $f_i = 0$。此时位置 $i$ 不需要修改。
- 位置 $i$ 的目标状态是 $0$，且 $f_i = 1$。此时有一个位置对位置 $i$ 有影响，所以我们需要进行一次
update(i,val)操作将值抵消掉。 - 位置 $i$ 的目标状态是 $0$，且 $f_i \ge 2$，此时位置 $i$ 不需要修改，因为必定有方案使得这 $f_i$ 个值的和为 $0$。
- 位置 $i$ 的目标状态是非 $0$，且 $f_i = 0$，此时需要进行一次
update(i,val)操作将位置 $i$ 的值变为非 $0$。 - 位置 $i$ 的目标状态是非 $0$，且 $f_i \ge 1$，此时位置 $i$ 不需要修改。
根据上述 $5$ 种情况整合后可得计算答案的方法：
for(int i=1,j,cnt;i<=n;i++)
{
if(st[i-1]=='1')
{
if(f[i]==0) ans++;
if(i+lowbit(i)<=n) f[i+lowbit(i)]++;
}else if(f[i]==1) ans++;
}
代码
#include<bits/stdc++.h>
namespace fast_IO
{
/**
* 快读快写
*/
};
using namespace fast_IO;
int t,n,f[100010],ans;
std::string st;
inline int lowbit(int x)
{
return x&(-x);
}
int main()
{
in>>t;
while(t--)
{
in>>n>>st,ans=0;
for(int i=1;i<=n;i++) f[i]=0;
for(int i=1,j,cnt;i<=n;i++)
{
if(st[i-1]=='1')
{
if(f[i]==0) ans++;
if(i+lowbit(i)<=n) f[i+lowbit(i)]++;
}else if(f[i]==1) ans++;
}
out<<ans<<'\n';
}
fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
return 0;
}
