题解：P14243 [CCPC 2024 Shandong I] 宇宙旅行
sheepchat
·
·
题解
我说这题真水吧。
题意省流：多次查询 l,r,k，求出对于 i\in [l,r] 将可重集中的所有数异或上 i 后的第 k 小的和。
首先考虑算单点，可以先把这个可重集拍到一棵 trie 上。
我们尝试在 trie 上找到第 k 小。假设我们要异或的数二进制第 i 位为 s_i。
目前我们要判断第 i 位是 1 还是 0，而答案在子树 rt 中。
若 s_i=0，我们发现左子树比右子树的数都小，若 k\ge sz_{ls}，我们向右子树递归，k\gets k-sz_{ls}，答案加上这一层的权，否则向左子树递归。
恭喜你，你会 $O(qV\log V+n\log V)$ 了，虽然没啥用。
我们开始考虑将这个问题扩展到区间查询上。
首先这个 $[l,r]$ 很不利于我们做操作，改成 $[0,r]-[0,l)$。
然后我们不妨考虑这样一件事情，在第 $i$ 位，决策 $rt$ 子树，目标为求第 $k$ 小，目前后面异或上 $s$（忽略前 $i+1$ 位，因为已经决策完了），称这个目标为 $(rt,k,s)$，不难发现这个递归的过程可以用这个三元组描述。
我们可能会想象成 $(rt,k,l,r)$，来完成整体模拟上述递归。
你会发现这个四元组可能会在递归的过程中分裂成两个，就会直接炸掉。
但是，我们发现其中总有一个分裂完的 $(l,r)=(0,2^k-1)$ 的样子的，考虑将所有长这个样的四元组全部的答案预处理一下，你分析一下是 $O(n\log V)$ 的。
然后你就可以在 $O((n+q)\log V)$ 解决这题了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,B=59,N=1e5+5;
struct node{
int ch[2],siz;
vector<int>vec;
}tr[(B+2)*N];
int n,q,cnt=1,fw[129];
void add(int& x,int y){x=(x+y)%mod; }
void add(long long& x,int y){x=(x+y)%mod; }
//void add(int& x,long long y){x=(x+y)%mod; }
void add(long long& x,long long y){x=(x+y)%mod; }
void dfs(int u,int dep){
if(u==0)return;
if(tr[u].ch[0]==0&&tr[u].ch[1]==0){
tr[u].vec.resize(tr[u].siz,0);
return;
}
int ls=tr[u].ch[0],rs=tr[u].ch[1];
dfs(ls,dep-1);dfs(rs,dep-1);
int sl=tr[ls].siz,sr=tr[rs].siz,su;
su=tr[u].siz=sl+sr;
tr[u].vec.resize(su,0);
for(int i=0;i<su;i++){
if(i<sl)add(tr[u].vec[i],tr[ls].vec[i]);
else add(tr[u].vec[i],(fw[dep*2]+tr[rs].vec[i-sl])%mod);
if(i<sr)add(tr[u].vec[i],tr[rs].vec[i]);
else add(tr[u].vec[i],(fw[dep*2]+tr[ls].vec[i-sr])%mod);
}
}
long long work(int rt,long long r,int k,int dep){
if(dep==-1)return 0;
int ls=tr[rt].ch[0],rs=tr[rt].ch[1];
int sl=tr[ls].siz,sr=tr[rs].siz;
if((r>>dep)&1ll){
r^=(1ll<<dep);
long long ans=0;
if(k<sl)add(ans,tr[ls].vec[k]);
else add(ans,(tr[rs].vec[k-sl]+fw[dep*2])%mod);
if(k<sr)add(ans,work(rs,r,k,dep-1));
else add(ans,(work(ls,r,k-sr,dep-1)+1ll*(r%mod+1)*fw[dep])%mod);
// cout<<"Q"<<rt<<" "<<r<<" "<<k<<" "<<dep<<" "<<ans<<'\n';
return ans;
}else{
if(k<sl){return work(ls,r,k,dep-1);}
else return (work(rs,r,k-sl,dep-1)+1ll*(r%mod+1)*fw[dep])%mod;
}
}
long long solve(long long r,int k){
if(r==-1)return 0;
long long ans=work(1,r,k-1,B);
return ans;
}
int main(){
// freopen("cosmic.in","r",stdin);freopen("cosmic.out","w",stdout);
ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
long long x;cin>>x;
int p=1;
for(int i=B;i>=0;i--){
if(tr[p].ch[(x>>i)&1]==0)tr[p].ch[(x>>i)&1]=++cnt;
p=tr[p].ch[(x>>i)&1];
}
tr[p].siz++;
}
fw[0]=1;
for(int i=1;i<=128;i++)fw[i]=fw[i-1]*2%mod;
dfs(1,B);
while(q--){
long long l,r;
int k;
cin>>l>>r>>k;
long long ans=solve(r,k)-solve(l-1,k);
ans=(ans%mod+mod)%mod;
cout<<ans<<"\n";
}
//for(int i=1;i<=cnt;i++){
// cout<<i<<" "<<tr[i].ch[0]<<" "<<tr[i].ch[1]<<"\n";
// }
return 0;
}
```