CF1957
flower1
·
·
个人记录
CF1957
D
Description
给定序列 a_n，求满足以下条件的三元组 (x,y,z) 的数量：
其中 f(l,r) 表示 a_l\oplus a_{l+1}\oplus\dots\oplus a_{r-1}\oplus a_{r}。
#### Solution
化简原式： $f(x,z) \oplus a_y>f(x,z)$。
将区间异或转化为前缀异或，定义 $s_x$ 为前 $x$ 个数的异或和。
转化为 $s_{x-1} \oplus s_z \oplus a_y > s_{x-1} \oplus s_z$。
考虑 $a \oplus b > a$ 什么时候成立，我们只关注 $b$ 的最高位 $j$，若 $a$ 的第 $j$ 位为 $0$ 则不等式成立。
我们枚举 $a_y$，对于所有 $x\in [1,y],z \in [y,n]$，求有多少个 $s_{x-1} \oplus s_z$ 的第 $j$ 位为 $0$ ，这可以预处理前缀和后缀和。
#### Code
```
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=35;
int T,n,a[N],s[N],pr[N][M][2],sf[N][M][2],ans;
int read(){
int k=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
k=k*10+ch-'0',ch=getchar();
return k;
}
signed main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++)
a[i]=read(),s[i]=s[i-1]^a[i];
for(int i=0;i<n;i++){
for(int j=0;j<=30;j++){
pr[i][j][0]=pr[i-1][j][0];
pr[i][j][1]=pr[i-1][j][1];
if(s[i]&(1<<j))
pr[i][j][1]++;
else
pr[i][j][0]++;
}
}
for(int j=0;j<=30;j++)
sf[n+1][j][0]=0,sf[n+1][j][1]=0;
for(int i=n;i>=1;i--){
for(int j=0;j<=30;j++){
sf[i][j][0]=sf[i+1][j][0];
sf[i][j][1]=sf[i+1][j][1];
if(s[i]&(1<<j))
sf[i][j][1]++;
else
sf[i][j][0]++;
}
}
ans=0;
for(int i=1;i<=n;i++){
int t=0;
while(a[i]>1){
a[i]=(a[i]>>1);
t++;
}
ans+=pr[i-1][t][0]*sf[i][t][0]+pr[i-1][t][1]*sf[i][t][1];
}
printf("%lld\n",ans);
}
return 0;
}
```
## E
神秘组合数学题，未完待续。
## F
#### Description
给定一棵树，点有点权，每次询问给出 $u_1,v_1,u_2,v_2,k$，请你找到至多 $k$ 个数，满足其在 $u_1,v_1$ 路径上出现次数和在 $u_2,v_2$ 路径上出现次数不同。
$n,q \le 10^5$，$k \le 10$。
#### Solution
对于一棵树上的路径，我们可以通过主席树来差分求出一条路径上每个数的出现次数。
现在的问题形如给定两棵线段树，快速找到 $k$ 个权值不同的叶子节点。
如果我们能快速判断两棵子树是否相等，只在子树不同时递归，时间复杂度就是 $O(\sum \log k)$。
考虑使用哈希，用线段树维护当前区间的哈希值即可完成本题。
为了方便，代码中使用了加减哈希。
#### Code
```
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=2e5+5,M=1e5;
struct node{
int ls,rs,sum;
}tr[N<<5];
struct ask{
int x,y,t,ft;
};
int n,q,mx,a[N],cnt,ans[N];
int idx,lg[N],pos[N],st[N][20];
int ha[N],len,fa[N],rt[N];
vector<int>e[N];
int read(){
int k=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
k=k*10+ch-'0',ch=getchar();
return k;
}
void dfs1(int x,int y){
pos[x]=++idx,st[idx][0]=x,fa[x]=y;
for(int i:e[x]){
if(i==y)
continue;
dfs1(i,x);
st[++idx][0]=x;
}
}
int qmax(int x,int y){
return (pos[x]<pos[y]?x:y);
}
void init(){
for(int i=2;i<=(n<<1);i++)
lg[i]=lg[i>>1]+1;
for(int j=1;j<=18;j++)
for(int i=1;i+(1<<j)-1<(n<<1);i++)
st[i][j]=qmax(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int lca(int x,int y){
x=pos[x],y=pos[y];
if(x>y) swap(x,y);
int k=lg[y-x+1];
return qmax(st[x][k],st[y-(1<<k)+1][k]);
}
void pushup(int k){
tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;
}
void modify(int &k,int p,int l,int r,int x){
k=++len;
tr[k]=tr[p];
if(l==r){
tr[k].sum+=ha[l];
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(tr[k].ls,tr[p].ls,l,mid,x);
if(mid+1<=x) modify(tr[k].rs,tr[p].rs,mid+1,r,x);
pushup(k);
}
int qsum(ask a){
return tr[a.x].sum+tr[a.y].sum-tr[a.t].sum-tr[a.ft].sum;
}
ask qls(ask a){
return {tr[a.x].ls,tr[a.y].ls,tr[a.t].ls,tr[a.ft].ls};
}
ask qrs(ask a){
return {tr[a.x].rs,tr[a.y].rs,tr[a.t].rs,tr[a.ft].rs};
}
void solve(ask k,ask p,int l,int r){
if(cnt==mx) return;
if(l==r){
ans[++cnt]=l;
return;
}
int mid=(l+r)>>1;
if(qsum(qls(k))!=qsum(qls(p)))
solve(qls(k),qls(p),l,mid);
if(qsum(qrs(k))!=qsum(qrs(p)))
solve(qrs(k),qrs(p),mid+1,r);
}
void dfs2(int x){
modify(rt[x],rt[fa[x]],1,M,a[x]);
for(int i:e[x]){
if(i==fa[x])
continue;
dfs2(i);
}
}
signed main(){
mt19937 myrand(time(nullptr));
int u,v,u1,u2,v1,v2;
for(int i=1;i<=M;i++)
ha[i]=myrand();
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<n;i++){
u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
init();
dfs2(1);
q=read();
for(int i=1;i<=q;i++){
u1=read(),v1=read(),u2=read(),v2=read(),mx=read();
cnt=0;
solve({rt[u1],rt[v1],rt[lca(u1,v1)],rt[fa[lca(u1,v1)]]},{rt[u2],rt[v2],rt[lca(u2,v2)],rt[fa[lca(u2,v2)]]},1,M);
printf("%llu ",cnt);
for(int j=1;j<=cnt;j++)
printf("%llu ",ans[j]);
printf("\n");
}
return 0;
}
```