题解：P17252 异或
lailai0916
·
·
题解
题意简述
给定严格递减的进制序列，末项为 2。
每一层先按当前进制拆位，
再对对应数位递归执行下一层运算，
最后在二进制层做异或。
维护一个可重集，求其中所有无序数对的运算结果之和。
需要输出初始答案与每次修改后答案的异或和。
解题思路
先把一个数完全拆到二进制层。
考虑一个值为 x、外部权值为 e 的递归节点。
若 x=1，就在最终展开中记录权值 e。
若 x>1，选择不超过 x 的最大进制 c。
比 x 大的进制只会产生一个数位，
跳过它们不会改变结果。
把 x 写成 c 进制后，
第 j 位的值递归展开时，外部权值变为 ec^j。
把最终记录的权值集合记为 D(x)。
每次按进制拆位都保持权值总和，因此有：
x=\sum_{e\in D(x)}e
还需要说明 D(x) 中不会出现相同权值。
在一次以 c 为进制的拆分中，
第 j 位产生的所有叶子权值之和小于 ec^{j+1}，
且每个叶子权值至少为 ec^j。
所以不同数位的叶子分别位于互不相交的区间：
[ec^j,ec^{j+1})
同一数位内部继续递归，结论由归纳成立。
因此所有叶子权值两两不同，D(x) 确实是集合。
递归运算最终只会对相同叶子做二进制异或。
某个叶子只在一个数中出现时保留，
在两个数中同时出现时抵消。
于是 x\mathbin{\oplus_1}y 对应
$$
x\mathbin{\oplus_1}y
=x+y-2\sum_{e\in D(x)\cap D(y)}e
$$
设当前可重集大小为 $C$，元素和为 $S$。
再令 $c_e$ 表示包含叶子 $e$ 的元素数量。
一个新元素 $x$ 与当前所有元素的运算结果之和为：
$$
Q(x)=S+Cx-2\sum_{e\in D(x)}c_e e
$$
展开 $x$ 时遍历其所有叶子，
即可同时求出最后一项，并把每个 $c_e$ 增加 $w$。
加入 $w$ 个 $x$ 时，当前数对和增加 $wQ(x)$。
删除操作可以令 $w$ 取负数，使用完全相同的式子。
这是因为任意两个相同元素的运算结果均为零。
计算删除时，旧集合中被删除副本之间的贡献也是零，
不会被重复扣除。
下面分析单个数的展开规模。
设 $F(x)$ 为展开过程中所有进制循环的总迭代次数。
当选取的进制 $c\geq4$ 时，令 $x=pc+r$，则有：
$$
F(x)\leq F(p)+F(r)+2
$$
取势函数 $6\log_2(x+1)-2$ 进行归纳。
当 $r>0$ 时，有：
$$
(p+1)(r+1)\leq pc+r+1=x+1
$$
两个子问题的势函数之和足以覆盖额外的两次迭代。
当 $r=0$ 时，$c\geq4$ 保证
$(pc+1)/(p+1)\geq5/2$，势函数的增量同样足够。
若 $c=2$，展开次数就是二进制位数。
若 $c=3$，每个三进制位至多再展开一次数值 $2$，
仍然只有常数倍的位数。
因此 $F(x)=O(\log x)$。
每个非叶节点用二分寻找进制，复杂度为 $O(\log k)$。
每个叶子只进行常数次哈希表操作。
令值域上界为 $V$，
总时间复杂度为 $O(k+(n+q)\log V\log k)$，
期望空间复杂度为 $O(k+(n+q)\log V)$。
答案可能达到 $10^{38}$ 量级，需要使用 `__int128_t`。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128_t;
const int N=300005;
int b[N];
int k;
ll siz;
i128 sum,ans,same;
unordered_map<int,ll> cnt;
vector<pair<int,int>> stk;
int getbase(int x)
{
int l=1,r=k;
while(l<r)
{
int mid=(l+r)/2;
if(b[mid]<=x)r=mid;
else l=mid+1;
}
return b[l];
}
void modify(int x,ll w)
{
same=0;
stk.clear();
if(x)stk.push_back({x,1});
while(!stk.empty())
{
auto [v,e]=stk.back();
stk.pop_back();
if(v==1)
{
same+=(i128)cnt[e]*e;
cnt[e]+=w;
continue;
}
int c=getbase(v);
while(v)
{
int r=v%c;
if(r)stk.push_back({r,e});
v/=c;
if(v)e*=c;
}
}
ans+=(i128)w*(sum+(i128)siz*x-2*same);
sum+=(i128)w*x;
siz+=w;
}
void print(i128 x)
{
string s;
do
{
s+=char(x%10+'0');
x/=10;
}while(x);
reverse(s.begin(),s.end());
cout<<s;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>k>>q;
for(int i=1;i<=k;i++)cin>>b[i];
cnt.max_load_factor(0.7f);
cnt.reserve((n+q)*4);
stk.reserve(256);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
modify(x,1);
}
i128 res=ans;
while(q--)
{
int op,x;
ll w;
cin>>op>>w>>x;
if(op==2)w=-w;
modify(x,w);
res^=ans;
}
print(res);
cout<<'\n';
return 0;
}
```