CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/09/10 14:19]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/10/08 15:00] (当前版本)
jxm2001
@@ 行 24: / 行 24: @@
 但由于区间 $[l,b]$ 可能已经属于某个区间 $[a,b]$，所以需要线段树分裂将其分裂为 $[a,l-1],[l,b]$。
-同样也需要将区间 $[c,d]$ 分裂为 $[c,r],[r+1,d]$。最后将 $[l,b]\cdots [c,r]$ 等区间合并即可，注意打标记维护区间的升序/降序情况。
+同样也需要将区间 $[c,d]$ 分裂为 $[c,r],[r+1,d]$。
+最后将 $[l,b]\cdots [c,r]$ 等区间合并即可，注意打标记维护区间的升序/降序情况。
 初始化时间复杂度 $O(n\log n)$，产生点数 $O(n\log n)$。每次分裂时间复杂度 $O(\log n)$，且增加 $O(\log n)$ 个点。
@@ 行 726: / 行 728: @@
 </hidden>
+==== 习题四 ====
+[[https://www.luogu.com.cn/problem/P3899|洛谷p3899]]
+=== 题意 ===
+给定一棵以 $1$ 为根的树，接下来 $q$ 次询问。每次询问给定 $a,k$，有多少个二元组 $(b,c)$ 满足：
+  - 结点 $a,b,c$ 互异
+  - 结点 $a$ 和结点 $b$ 是结点 $c$ 的祖先
+  - 结点 $a$ 和结点 $b$ 的距离不超过 $k$
+=== 题解 ===
+对每次查询操作，答案分为 $b$ 为 $a$ 祖先和 $a$ 为 $b$ 祖先两种。对于 $b$ 为 $a$ 祖先的情况，易知答案为 $(\text{sz}_a-1)\min(d_a-1,k)$。
+对于 $a$ 为 $b$ 祖先的情况，易知每个 $a$ 的子树中距离 $a$ 不超过 $k$ 的结点的贡献为该结点的子树大小减一。
+于是考虑将每个结点的权值设为该结点的子树大小减一，于是贡献和为所有深度为 $[d_a+1,d_a+k]$ 且 $\text{dfs}$ 序属于 $a$ 的子树的结点的权值和。
+于是问题转化为二维偏序问题，考虑主席树统计答案。时间复杂度 $O((n+q)\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5,MAXM=40;
+struct Node{
+	LL s;
+	int ch[2];
+}node[MAXN*MAXM];
+int root[MAXN],n,node_cnt;
+void update(int &k,int p,int pos,int v,int lef=1,int rig=n){
+	node[k=++node_cnt]=node[p];
+	node[k].s+=v;
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	if(pos<=mid)
+	update(node[k].ch[0],node[p].ch[0],pos,v,lef,mid);
+	else
+	update(node[k].ch[1],node[p].ch[1],pos,v,mid+1,rig);
+}
+LL query(int k1,int k2,int ql,int qr,int lef=1,int rig=n){
+	if(ql<=lef&&rig<=qr)return node[k1].s-node[k2].s;
+	int mid=lef+rig>>1;
+	if(mid>=qr)return query(node[k1].ch[0],node[k2].ch[0],ql,qr,lef,mid);
+	else if(mid<ql)return query(node[k1].ch[1],node[k2].ch[1],ql,qr,mid+1,rig);
+	else return query(node[k1].ch[0],node[k2].ch[0],ql,qr,lef,mid)+query(node[k1].ch[1],node[k2].ch[1],ql,qr,mid+1,rig);
+}
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int dfs_t,dfn[MAXN],sz[MAXN],d[MAXN],inv_dfn[MAXN];
+void dfs(int u,int fa,int dep){
+	dfn[u]=++dfs_t;
+	sz[dfs_t]=1;d[dfs_t]=dep;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u,dep+1);
+		sz[dfn[u]]+=sz[dfn[v]];
+	}
+}
+int main()
+{
+	n=read_int();
+	int q=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);Insert(v,u);
+	}
+	dfs(1,0,1);
+	_rep(i,1,n)
+	update(root[i],root[i-1],d[i],sz[i]-1);
+	while(q--){
+		int p=read_int(),k=read_int(),u=dfn[p];
+		enter(1LL*(sz[u]-1)*min(d[u]-1,k)+query(root[u+sz[u]-1],root[u],d[u],min(d[u]+k,n)));
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题五 ====
+[[https://www.luogu.com.cn/problem/P3293|洛谷p3293]]
+=== 题意 ===
+给定长度为 $n$ 的序列 $a$ 和 $q$ 个询问。每次询问给定 $b,x,l,r$，输出 $\max_{l\le i\le r}(b\oplus(a_i+x))$。
+=== 题解 ===
+考虑按高位到低位贪心枚举。假设当前枚举到第 $4$ 为，答案 $\text{ans}=c_1c_2c_3???,b=b_1b_2b_3b_4??$。
+优先考虑是否可以使 $\text{ans}=c_1c_2c_31??$，如果 $b_4=1$，则 $\text{ans}\oplus b\in[d_1d_2d_3000,d_1d_2d_3011]$。
+如果 $b_4=0$，则 $\text{ans}\oplus b\in[d_1d_2d_3100,d_1d_2d_3111]$。而 $a=\text{ans}\oplus b-x$，于是主席树查询即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXM=17,MAXV=1e5;
+int root[MAXN],node_cnt;
+struct Node{
+	int ch[2],sz;
+}node[MAXN*40];
+void update(int &k,int p,int pos,int lef=0,int rig=MAXV){
+	node[k=++node_cnt]=node[p];
+	node[k].sz++;
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	update(node[k].ch[0],node[p].ch[0],pos,lef,mid);
+	else
+	update(node[k].ch[1],node[p].ch[1],pos,mid+1,rig);
+}
+int query(int k1,int k2,int ql,int qr,int lef=0,int rig=MAXV){
+	if(lef>qr||rig<ql)return 0;
+	if(ql<=lef&&rig<=qr)return node[k1].sz-node[k2].sz;
+	int mid=lef+rig>>1;
+	return query(node[k1].ch[0],node[k2].ch[0],ql,qr,lef,mid)+query(node[k1].ch[1],node[k2].ch[1],ql,qr,mid+1,rig);
+}
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n)
+	update(root[i],root[i-1],read_int());
+	while(q--){
+		int b=read_int(),x=read_int(),l=read_int(),r=read_int();
+		int ans=0;
+		for(int i=MAXM;~i;i--){
+			int ql=((ans^b)>>(i+1))<<(i+1);
+			if(b&(1<<i)){
+				if(query(root[r],root[l-1],ql-x,ql+(1<<i)-1-x))
+				ans|=1<<i;
+			}
+			else{
+				if(query(root[r],root[l-1],ql+(1<<i)-x,ql+(1<<(i+1))-1-x))
+				ans|=1<<i;
+			}
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具