专栏文章

CF1957

fflower1
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1cl6r
此快照首次捕获于
2025/12/02 11:45
3 个月前
此快照最后确认于
2025/12/02 11:45
3 个月前
查看原文

CF1957

D

Description

给定序列 ana_n，求满足以下条件的三元组 (x,y,z)(x,y,z) 的数量：
  • 1≤x≤y≤z≤n1\le x\le y\le z\le n.
  • f(x,y)⊕f(y,z)>f(x,z)f(x,y)\oplus f(y,z)>f(x,z).
其中 f(l,r)f(l,r) 表示 al⊕al+1⊕⋯⊕ar−1⊕ara_l\oplus a_{l+1}\oplus\dots\oplus a_{r-1}\oplus a_{r}。
n≤105n\le 10^5。

Solution

化简原式： f(x,z)⊕ay>f(x,z)f(x,z) \oplus a_y>f(x,z)。
将区间异或转化为前缀异或，定义 sxs_x 为前 xx 个数的异或和。
转化为 sx−1⊕sz⊕ay>sx−1⊕szs_{x-1} \oplus s_z \oplus a_y > s_{x-1} \oplus s_z。
考虑 a⊕b>aa \oplus b > a 什么时候成立，我们只关注 bb 的最高位 jj，若 aa 的第 jj 位为 00 则不等式成立。
我们枚举 aya_y，对于所有 x∈[1,y],z∈[y,n]x\in [1,y],z \in [y,n]，求有多少个 sx−1⊕szs_{x-1} \oplus s_z 的第 jj 位为 00 ，这可以预处理前缀和后缀和。

Code

CPP
#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

给定一棵树，点有点权，每次询问给出 u1,v1,u2,v2,ku_1,v_1,u_2,v_2,k，请你找到至多 kk 个数，满足其在 u1,v1u_1,v_1 路径上出现次数和在 u2,v2u_2,v_2 路径上出现次数不同。
n,q≤105n,q \le 10^5，k≤10k \le 10。

Solution

对于一棵树上的路径，我们可以通过主席树来差分求出一条路径上每个数的出现次数。
现在的问题形如给定两棵线段树，快速找到 kk 个权值不同的叶子节点。
如果我们能快速判断两棵子树是否相等，只在子树不同时递归，时间复杂度就是 O(∑log⁡k)O(\sum \log k)。
考虑使用哈希，用线段树维护当前区间的哈希值即可完成本题。
为了方便，代码中使用了加减哈希。

Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...